6.5 二叉排序树★3◎41．二叉排序树定义二叉排序树（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，则在左子树中继续搜索；④否则，在右子树中继续查找。
假定二叉排序树的链式存储结构的类型定义如下：1typedef struct linklist{2keytype key;3anytype otherelem;4struct linklist*lchild；5struct linklist*rchild;6}Bin_Sort_Tree_Linklist,*Bin_Sort_Tree；二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：7Bin_Sort_Tree_Linklist*bt_search(Bin_Sort_Tree bt,keytype k)8{∥在根指针为bt的二叉排序树上查找一个关键字值为k的结点，9∥若查找成功返回指向该结点的指针，否则返回空指针10if(bt=NULL)‖(bt->key==k)return bt;11else if(k<bt->key)return bt_search(bt->lchild,k);12∥在左子树中搜索13else return bt_search(bt->rchild,k);//在右子树中搜索14}这个过程也可以用非递归算法实现，算法描述如下：15Bin_Sort_Tree_Linklist*bt_search1(Bin_Sort_Tree bt,keytype k)16{17p=bt;∥指针p指向根结点，搜索从根结点开始18while(p!=NULL && p->key!=k)19{20if(k<p->key)p=p->lchild;21else p=p->rchild;22}23return(p);24}3）二叉排序树的插入在一棵二叉排序树中插入一个结点可以用一个递归的过程实现。
若二叉排序树为空，则新结点作为二叉排序树的根结点。
否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。
下面是二叉排序树插入操作的递归算法。
1void bt_insert1(Bin_Sort_Tree*bt,Bin_Sort_Tree_Linklist*pn)2{∥在以bt为根的二叉排序树上插入一个由指针pn指向的新的结点3if(*bt=NULL)*bt=pn;4else if(*bt->key>pn->key)bt_insert 1(&(*bt->lchild),pn);5else if(*bt->key<pn->key)bt_insert1(&(*bt->rchild),pn);6}这个算法也可以用非递归的形式实现，如下所示：7void bt_insert 2(Bin_Sort_Tree*bt,8Bin_Sort_Tree_Linklist*pn)9{10p=bt;11while(p!=NULL && p->key!=pn->key)12{13 q=p;14if(p->key>pn->key)p=p->lchild;15else p=p->rchild;16}17if(p=NULL){18if(q->key>pn->key)q->lchild=pn;19else q->rchild=pn->key;20}21}利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想为：由一棵空二叉树开始，经过一系列的插入操作生成一棵二叉排序树。
例如，由结点关键字序列（62,15,68,46,65,12,57,79,35）构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排序树中，在插入每个结点时都是从根结点开始搜索插入位置，找到插入位置后，将新结点作为叶子结点插入，经过9次的插入操作，建成由这9个结点组成的二叉排序树。
创建二叉排序树的算法如下：22Bin_Sort_Tree_Linklist*bt_bulid(Bin_Sort_Tree a,int n)23{∥在数组a的a［1］~a［n］24单元中存放着将要构成二叉排序树的n个结点内容25bt=NULL;26for(i=1;i<=n;i++)27{28p=(Bin_Sort_Tree_Linklist*)malloc29(sizeof(Bin_Sort_Tree_Linklist));30p->key=a［i］.key;31p->otherelem=a［i］.otherelem;;32p->lchile=NULL;33p->rchile=NULL;34bt_insert1(&bt,p);35}36return(bt);37}（4）二叉排序树的删除下面分四种情况讨论一下如何确保从二叉树中删除一个结点后，不会影响二叉排序树的性质：①若要删除的结点p为叶子结点，可以直接进行删除。
②若要删除结点p有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。
③若要删除结点p有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位置，与步骤②类似。
④若要删除结点p的左右子树均非空，则在其左子树中找到最右结点r来代替被删的结点(即将r所指结点的右指针置成p所指结点的右子树的根，然后用p所指结点的左子树的根结点代替被删的p所指结点)。