数据结构_第9章_查找2-二叉树和平衡二叉树

《数据结构_第9章_查找2-二叉树和平衡二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章查找数据结构讲义-二叉树和平衡二叉树特点：一、二叉排序树的定义二、二叉排序树的插入与删除三、二叉排序树的查找分析四、平衡二叉树五、B-树和B+树9.2动态查找表表结构在查找过程中动态生成。要求：对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key的记录。典型的动态表———二叉排序树一、二叉排序树的定义（a）（b）练：下列2种图形中，哪个不是二叉排序树？----或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。讨论：对(a)中

2、序遍历后的结果是什么？二、二叉排序树的插入与删除将数据元素构造成二叉排序树的优点：①查找过程与顺序结构有序表中的折半查找相似，查找效率高；②中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；③如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！——这种既查找又插入的过程称为动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。4524531290如果待查找的关键字序列输入顺序为：（24，53，45，45，1

3、2，24，90），2453451290查找成功，返回查找成功，返回讨论1：二叉排序树的插入和查找操作则生成二叉排序树的过程为：例：输入待查找的关键字序列=（45，24，53，45，12，24，90）则生成的二叉排序树形态不同：查找成功，返回查找成功，返回二叉排序树的查找&插入算法如何实现？查找算法静态查找算法动态查找算法（插入）二叉排序树的静态查找思想若二叉排序树为空，则查找失败.否则，先拿根结点值与待查值进行比较，若相等，则查找成功.若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤.二叉排序树查找的算法实现1)递归函数NODE*search(t,x)

4、NODE*t;charx;{if(t==NULL)return(NULL);else{if(t->data==x)return(t);if(x<(t->data)return(search(t->lchild,x));elsereturn(search(t->lchild,x));}}2)非递归函数NODE*search(NODE*t,charx){NODE*p;p=t;while(p!=NULL){if(p->data==x)return(p);if(xdata)p=p->lchild;elsep=p->rchlid;}printf(“找不到值为%x的结点!”,x)

5、;return(NULL);}二叉排序树的动态查找算法查找算法：若二叉排序树为空，则返回插入位置，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤。（P228算法9.5（b））插入算法：若二叉排序树为空，则被查结点为新的根节点；否则，作为一个新的叶子结点插入在由查找返回的位置上。（P228算法9.6）二叉排序树的建立对于已给定一待排序的数据序列,通常采用逐步插入结点的方法来构造二叉排序树,即只要反复调用二叉排序树的插入算法即可，算法描述为：BiTree*Creat(intn)//建立含有n个结点的

6、二叉排序树{BiTree*BST=NULL;for(inti=1;i<=n;i++){scanf(“%d”,&x);//输入关键字序列InsertBST(BST,x);}return(BST);}二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：p为叶子结点，只需修改p双亲f的指针。p只有左子树或右子树，只需用p的孩子代替p。p左、右子树均非空。沿p左子树的根C的右子树分支找到S，S的右子树为空。法1：令*p的左子树为*f的左子树，*p的右子树为*s的右子树；法2：令*s代替*p将S的左子树成为S的双亲Q的右子树，用S取代p。若C无右子树，用C取代p。FCCLSSLQL

7、PPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法1:例：请从下面的二叉排序树中删除结点P。SSL1036241812156342181215删除101)二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。比较的关键字次数＝此结点的层次数;最多的比较次数＝树的深度（或高度），即log2n+12)一棵二叉排序树的平均查找长度为：三、二叉排序树的查找分析其中：ni是每层结点个数；Ci是结点所在层次数；m为树深。最坏情况：即插入的n个元素从一开始就有序，