数据结构讲义九：二叉排序树讲解.ppt

动态查找;二叉排序树;二叉排序树示例;二叉排序树的查找算法;int Bstree::Search(KeyType K)?{?int flag=0;???BstNode*q=root;???while((q!=NULL)(flag==0))???{?if(q-key==K)?{?cout查找成功，找到：q-keyendl;?????????????????????flag=1;???????????????????}?????else if(Kq-key)q=q-lch;??????????elseq=q-rch;????}????if(flag==0)cout查找失败，无此结点! \n;????return flag;?} 函数 Search 中，参数 root 为根结点指针， K 为欲查找的关键字值，这里假定它是整数。函数执行完后，如果查找成功，输出所找到结点的关键字值，并且指针 q 指向所找到的结点， p 指向它的父结点；如果查找失败， q ＝ NULL ， p 为 q 的父结点指针。 ;二叉排序树查找非递归算法;二叉排序树上结点的插入 ;插入算法;12;记录的关键码序列为：63，90，70，55，67，42，98，83，则构造一棵二叉排序树的过程如下：;二叉排序树上结点的删除 ;;③若*p既有左子树，又有右子树。则：;二叉排序树上删除10或40或45或55;void Delete(BSTree bst, keytype X) //在二叉排序树bst上，删除其关键字为X的结点。 {BSTree f,p=bst; while (p p-key!=X) //查找值为X的结点 if (p-keyX) {f=p; p=p-lchild;} else {f=p; p=p-rchild;} if (p==null) {printf(“无关键字为X的结点\n”); exit(0);} if {p-lchild==null} //被删结点无左子树 if (f-lchild==p) f-lchild=p-rchild;//将被删结点的右子树接到其双亲上 else f-rchild=p-rchild; else //被删结点有左子树 {q=p; s=p-lchild; //s指向被删结点左子树的根 while (s-rchild !=null) //查左子树中最右下的结点（中序最后结点） {q=s; s=s-rchild;} p-key=s-key; //结点值用其左子树最右下的结点的值代替 if (q==p) p-lchild=s-lchild;//被删结点左子树的根结点无右子女 else q-rchild=s-lchild; //s是被删结点左子树中序最后一个结点 free(s); } }//算法结束 ;最佳二叉排序树 ;平衡二叉树 ;平衡的二叉树示例;不平衡的二叉树示例;平衡二叉树的类型定义;构造平衡二叉树 ;失去平衡的四种情况 ;失去平衡的四种情况 ;二叉平衡树插入结点 ( 结点旁的数字为其平衡因子 ) ;示例;示例;示例;LL型调整操作示意图;LL型调整的两个例子;RR型调整操作示意图;RR型调整的两个例子;LR型调整操作示意图;LR型调整的三个例子;LR型调整的三个例子;RL型调整操作示意图;RL型调整的三个例子;RL型调整的三个例子;AVL树上结点的插入 ;AVL树查找分析 ;B-树;前面讨论的查找方法适用于组织规模较小、内存中能容纳的数据，是内查找方法 B-树是一种平衡、有序、多路、动态的查找树，它是磁盘文件系统中索引技术常用的一种数据结构形式，如磁盘管理系统中的目录管理以及数据文件中的索引机构大多采用B-树;B-树的定义 ;B-树示例;B-树的查找 ;查找算法;B-树查找分析;B-树查找长度分析;附：S=N+1的推导;B-树的插入 ;插入结点后的分裂;B-树上插入结点;插入结点示例;插入结点示例;B-树的删除 ;B-树的删除;B树删除操作示例;B+树;一棵3阶B+树