二叉排序树.doc

二叉排序树1二叉排序树定义二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。（2）左右子树也都是二叉排序树，如图6-2所示。2二叉排序树的查找过程由其定义可见，二叉排序树的查找过程为：（1）若查找树为空，查找失败。（2）查找树非空，将给定值key与查找树的根结点关键码比较。（3）若相等，查找成功，结束查找过程，否则： 当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。 当给值key大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。3二叉排序树插入操作和构造一棵二叉排序树向二叉排序树中插入一个结点的过程：设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，该插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。对于关键码序列为：63，90，70，55，67，42，98，83，10，45，58，则构造一棵二叉排序树的过程如图6-3所示。4二叉排序树删除操作从二叉排序树中删除一个结点之后，要求其仍能保持二叉排序树的特性。设待删结点为*p（p为指向待删结点的指针），其双亲结点为*f，删除可以分三种情况，如图6-4所示。（1）*p结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针，如图6-4（a）所示。（2）*p结点只有右子树或只有左子树，此时，只需将或替换*f结点的*p子树即可，如图6-4（b）、（c）所示。（3）*p结点既有左子树又有右子树，可按中序遍历保持有序地进行调整，如图6-4（d）、（e）所示。设删除*p结点前，中序遍历序列为： P为F的左子女时有：，Pi子树，P，Pj，S子树，Pk，Sk子树，P2，S2子树，P1，S1子树，F，。 P为F的右子女时有：，F，Pi子树，P，Pj，S子树，Pk，Sk子树，P2，S2子树，P1，S1子树，。则删除*p结点后，中序遍历序列应为： P为F的左子女时有：，Pi子树，Pj，S子树，Pk，Sk子树，P2，S2子树，P1，S1子树，F，。 P为F的右子女时有：，F，Pi子树，Pj，S子树，Pk，Sk子树，P2，S2子树，P1，S1子树，。有两种调整方法： 直接令Pi为*f相应的子树，以Pr为Pi中序遍历的最后一个结点Pk的右子树。 令*p结点的直接前驱Pr或直接后继（对Pi子树中序遍历的最后一个结点Pk）替换*p结点，再按（2）的方法删去Pr或Pk。【算法分析】对给定序列建立二叉排序树，若左右子树均匀分布，则其查找过程类似于有序表的折半查找。但若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率和顺序查找一样。因此，对均匀的二叉排序树进行插入或删除结点后，应进行调整，使其依然保持均匀。3.2.5 二叉排序树在这一部分我们要掌握的是二叉排序树的概念、查找、插入和删除操作。在以下的知识点中，二叉排序树的删除相对于其他知识点要复杂一些，但只要掌握了规则，题目还是很容易解决的。下面我们先分别给出各部分的介绍及算法实现，再对一些典型题目进行解析。（1）二叉排序树二叉排序树是一种常用的动态查找表，下面首先给出它的非递归形式。二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值。任一非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。二叉排序树也可以用递归的形式定义，即二叉排序树是一棵树，它或者为空，或者具有如下性质：若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值。若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。它的左右子树都是二叉排序树。例如，由关键字值序列（62,15,68,46,65,12,57,79,35）构成的一棵二叉排序树如图3-38所示。如果对上述二叉排序树进行中序遍历可以得到一个关键字有序序列（12,15,35,46,57,62,65,68,79），这是二叉排序树的一个重要特征，也正是由此将其称为二叉排序树。 （2）二叉排序树的查找二叉排序树的结构定义中可看到：一棵非空二叉排序树中根结点的关键字值大于其左子树上所有结点的关键字值，而小于其右子树上所有结点的关键字值。因此在二叉排序树中查找一个关键字值为k的结点的基本思想是：用给定值k与根结点关键字值比较，如果k小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查找，依此方法，查找下去，至直查找成功或查找失败为止。二叉排序树查找的过程描述如下：若二叉树为空树，则查找失败；将给定值k与根结点的关键字值比较，若相等，则查找成功；若根结点的关键字值小于给定值k，则在左子树中继续搜索；否则，在右子树中继续查找。假定二叉排序树的链式存储结构的类型定义如下：1 typedef struct linklist 2 keytype key; 3 anytype otherelem; 4 struct linklist*lchild； 5 struct linklist*rchild; 6 Bin_Sort_Tree_Linklist,*Bin_Sort_Tree； 二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：7 Bin_Sort_Tree_Linklist*bt_search(Bin_Sort_Tree bt,keytype k) 8 在根指针为bt的二叉排序树上查找一个关键字值为k的结点， 9 若查找成功返回指向该结点的指针，否则返回空指针 10 if(bt=NULL)(bt-key=k)return bt; 11 else if(kkey)return bt_search(bt-lchild,k); 12 在左子树中搜索 13 else return bt_search(bt-rchild,k);/在右子树中搜索 14 这个过程也可以用非递归算法实现，算法描述如下：15 Bin_Sort_Tree_Linklist*bt_search1(Bin_Sort_Tree bt,keytype k) 16 17 p=bt;指针p指向根结点，搜索从根结点开始 18 while(p!=NULL & p-key!=k) 19 20 if(kkey)p=p-lchild; 21 else p=p-rchild; 22 23 return(p); 24 3）二叉排序树的插入在一棵二叉排序树中插入一个结点可以用一个递归的过程实现。若二叉排序树为空，则新结点作为二叉排序树的根结点。否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。下面是二叉排序树插入操作的递归算法。1 void bt_insert1(Bin_Sort_Tree*bt,Bin_Sort_Tree_Linklist*pn) 2 在以bt为根的二叉排序树上插入一个由指针pn指向的新的结点 3 if(*bt=NULL)*bt=pn; 4 else if(*bt-keypn-key)bt_insert 1(&(*bt-lchild),pn); 5 else if(*bt-keykey)bt_insert1(&(*bt-rchild),pn); 6 这个算法也可以用非递归的形式实现，如下所示：7 void bt_insert 2(Bin_Sort_Tree*bt, 8 Bin_Sort_Tree_Linklist*pn) 9 10 p=bt; 11 while(p!=NULL & p-key!=pn-key) 12 13 q=p; 14 if(p-keypn-key)p=p-lchild; 15 else p=p-rchild; 16 17 if(p=NULL) 18 if(q-keypn-key)q-lchild=pn; 19 else q-rchild=pn-key; 20 21 利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想为：由一棵空二叉树开始，经过一系列的插入操作生成一棵二叉排序树。例如，由结点关键字序列（62,15,68,46,65,12,57,79,35）构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排序树中，在插入每个结点时都是从根结点开始搜索插入位置，找到插入位置后，将新结点作为叶子结点插入，经过9次的插入操作，建成由这9个结点组成的二叉排序树。创建二叉排序树的算法如下：22 Bin_Sort_Tree_Linklist*bt_bulid(Bin_Sort_Tree a,int n) 23 在数组a的a1an 24 单元中存放着将要构成二叉排序树的n个结点内容 25 bt=NULL; 26 for(i=1;ikey=ai.key; 31 p-otherelem=ai.otherelem; 32 p-lchile=NULL; 33 p-rchile=NULL; 34 bt_insert1(&bt,p); 35 36 return(bt); 37 （4）二叉排序树的删除下面分四种情况讨论一下如何确保从二叉树中删除一个结点后，不会影响二叉排序树的性质：若要删除的结点p为叶子结点，可以直接进行删除。若要删除结点p有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。若要删除结点p有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位置，与步骤类似。若要删除结点p的左右子树均非空，则在其左子树中找到最右结点r来代替被删的结点(即将r所指结点的右指针置成p所指结点的右子树的根，然后用p所指结点的左子树的根结点代替被删的p所指结点)。可以按下述方法来查找到左子树中的最大元素值的结点：首先移动到子树的根，然后沿着各节点的右孩子指针移动，直到右孩子指针为0为止，此时找到的结点即为左子树中的最大元素值的结点。下面是二叉排序树删除算法的实现：38 void delnode(btree*b,int x) 39 40 btree*p,*q,*r,*t; 41 p=b; 42 q=NULL; 43 while(p!=NULL & p-data!=x) 44 if(xdata) 45 46 q=p; 47 p=p-left; 48 49 else 50 51 q=p; 52 p=p-right; 53 54 if(p=NULL)pintf(未发现数据域为%d的结点n,x); 55 else if(p-left=NULL) 56 57 if(q=NULL)t=p-right; 58 else if(q-left=p)q-left=p-right; 59 else q-right=p-right; 60 61 else /*被删结点有左子树*/ 62 /*查找被删结点左子树中的最右结点，即刚好小于x的结点*/ 63 64 r=p-left; 65 while(r-right!=NULL) 66 r=r-right; 67 /*被删结点的右子树作为r的右子树*/ 68 r-right=p-right; 69 /*被删结点的左子树根代替被删结点*/ 70 if(q=NULL)t=p-left; /*被删结点是根结点*/ 71 else if(q-left=p)q-left=p-left; 72 else q-right=p-left; 73 74 【习题及解析】【例3-34】 二叉树为二叉排序树的（）条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。A.充分不必要 B.必要不充分 C.充分必要 D.既不充分也不必要【分析】 本题考查二叉排序树的定义。由二叉排序树的定义可知，在二叉排序树中，任一非终端结点的关键字的值大于其左子树中所有结点的关键字的值（当然也大于其左孩子的值），小于右子树中所有结点的关键字的值（当然也小于其右孩子的值）。分析至此，我们知道该题的选项中至少应该包括必要条件，故A、D可以排除。下面我们看是否充分，也即满足题干要求的二叉树是否一定是二叉排序树。我们可以用反证法，举出一个例子证明满足题干要求的二叉树不一定是二叉排序树。图3-39所示的二叉树满足题干的要求，54，46，但显然这不是一棵二叉排序树，其中序遍历序列为4,6,5，并非一个单增或单减的序列。故正确答案中不应包含充分条件，排除C。所以本题应该选B。【解答】 B。 【例3-35】 设数据集合d=1,12,5,8,3,10,7,13,9，试完成下列各题：依次取d中各数据，构造一棵二叉排序树bt。如何依据此二叉树bt得到d的一个有序序列。画出在二叉树bt中删除12后的树结构。【分析】 本题考查的是有关二叉排序树的基本概念。其中考查二叉排序树的生成和插入；考查如何根据二叉排序树得到有序序列，即二叉排序树中序遍历；考查二叉排序树的删除，且是删除结点中被删结点左右子树都非空的情形。依照前面介绍的二叉排序树的删除结点的规则，删除结