本节内容 1.二叉排序树的定义 2.二叉排序树的查找操作 3.二叉排序树的插入操作 4.二叉排序树的删除操作 5.二叉排序树的总结 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 本节内容 1.二叉排序树的定义 2.二叉排序树的查找操作 3.二叉排序树的插入操作 4.二叉排序树的删除操作 5.二叉排序树的总结

二叉排序树的定义 二叉排序树的定义 二叉排序树是一种典型的动态查找表 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的定义 二叉排序树的定义 二叉排序树是一种典型的动态查找表 动态查找表：表结构在查找过程中动态生成的表，对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key的记录。 二叉排序树的定义： 一棵空树或者具有如下性质的非空二叉树 1.左子树的所有结点均小于根的值 2.右子树的所有结点均大于根的值 3.它的左右子树也分别为二叉排序树

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的定义 二叉排序树的定义

二叉排序树的查找操作 二叉排序树的查找操作 算法： /* 二叉树的二叉链表结点结构定义 */ 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的查找操作 二叉排序树的查找操作 算法： /* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode /* 结点结构 */ { int data; /* 结点数据 */ struct BiTNode *lchild, *rchild; /* 左右孩子指针 */ } BiTNode, *BiTree;

二叉排序树的查找操作 二叉排序树的查找操作 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的查找操作 二叉排序树的查找操作 算法： Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) { if (!T) /* 查找不成功 */ *p = f; return FALSE; } else if (key==T->data) /* 查找成功 */ *p = T; return TRUE; else if (key<T->data) return SearchBST(T->lchild, key, T, p);/* 在左子树中继续查找 */ else return SearchBST(T->rchild, key, T, p);/*在右子树中继续查找 */

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的查找操作 二叉排序树的查找操作 演示

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的查找操作 二叉排序树的查找操作 演示

二叉排序树的插入操作 二叉排序树的插入操作 算法： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 Status InsertBST(BiTree *T, int key) { BiTree p,s; if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */ s = (BiTree)malloc(sizeof(BiTNode)); s->data = key; s->lchild = s->rchild = NULL; if (!p) *T = s; /* 插入s为新的根结点 */ else if (key<p->data) p->lchild = s; /* 插入s为左孩子 */ else p->rchild = s; /* 插入s为右孩子 */ return TRUE; } return FALSE; /* 树中已有关键字相同的结点，不再插入 */

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的插入操作 二叉排序树的插入操作 演示：

二叉排序树的删除操作 二叉排序树的删除操作 算法： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 /* 从二叉排序树中删除结点p，并重接它的左或右子树。 */ Status Delete(BiTree *p) { BiTree q,s; if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */ q=*p; *p=(*p)->lchild; free(q); } else if((*p)->lchild==NULL) /* 只需重接它的右子树 */ q=*p; *p=(*p)->rchild; free(q);

二叉排序树的删除操作 二叉排序树的删除操作 算法： 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 else /* 左右子树均不空 */ { q=*p; s=(*p)->lchild; while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */ q=s; s=s->rchild; } (*p)->data=s->data; /* s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */ if(q!=*p) q->rchild=s->lchild; /* 重接q的右子树 */ else q->lchild=s->lchild; /* 重接q的左子树 */ free(s); return TRUE;

昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的删除操作 二叉排序树的删除操作 演示：

二叉排序树的总结 二叉排序树的总结 1.线性表查找可以将线性表构造成二叉排序树进行查找 昆山爱达人信息技术有限公司 www.bcdaren.com QQ:254830010 二叉排序树的总结 二叉排序树的总结 1.线性表查找可以将线性表构造成二叉排序树进行查找 2.中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算） 3.如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需要移动元素。 4.二叉排序树的查找效率取决于二叉排序树的形状，如果二叉排序树比较平衡，其深度和完全二叉树相同则近似折半查找。