二叉排序树简介 

    二叉排序树（Binary Sort Tree，简称BST），又称二叉查找树，是红黑树、AVL树等的基础。它或是一棵空树，或者是具有下列性质的一棵二叉树：

   1、若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

   2、若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

   3、它的左右子树也分别为二叉排序树。

   下面的一棵树即为二叉排序树：

    很明显，对二叉排序树进行中序遍历，便可得到一个有序序列，该有序序列中的各元素按照从小到大的顺序排列，因此一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。

二叉排序树相关操作

    二叉排序树通常有查找、插入、删除等操作。查找操作很简单，无非就是递归查找，有点类似二叉树遍历的过程。插入操作也不难，一般是先在二叉排序树pTree中查找，看是否存在有等于给定值的元素，如果查找不到，则将给定值插入到该二叉排序树中，但是要保证插入后的树依然是二叉排序树。这样，新节点插入的位置便是唯一的，而且新插入的节点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子。正是由于其在查找过程中插入节点的特性，二叉排序树是一种动态树。

    在给出各操作实现的具体代码前，要详细看下二叉排序树的删除操作，删除操作相比于二叉排序树的其他操作要难些，但也只是相对于其本身的其他操作而已，真正理解了也就很容易了。闲话少说，下面就来具体分析二叉排序树的删除操作。

    我们假设在二叉排序树中要被删除的节点为p（即p指向的节点，下同），其父节点为f，当然节点p可能是节点f的的左孩子或右孩子，但在下面各种情况的分析中，你会发现，无论是左孩子还是右孩子，都不影响删除操作的通用性。很明显，删除操作要分为如下3种情况：

    1、若待删节点p为叶子节点，则删除p后，并不会破坏整棵树的结构，因此只需令p=NULL即可。

    2、若待删节点p只有左子树或右子树，则只需将左子树或右子树重接到p的父节点上即可，即执行如下操作：p=p->lchild或p=p->rchild。

    3、若待删节点p既有左子树又有右子树，显然就不如上面两种情况那么简单了。我们要使节点p被删除后，二叉排序树的结构不变，就需要对它的子树做一些操作，而且只需操作一个子树即可，操作左子树和操作右子树的思路相似，我们这里以操作左子树为例来实现节点p的删除操作，并结合下图做具体分析（图中三角形代表节点的左子树或右子树）。

    我们这里将图a展开为更详细的图b进行分析，则在删除节点p前，中序遍历该二叉排序树的结果为：...CL C...QL Q SL S P PR F ...，删除节点p后，我们要保持其他元素在该序列中的先后顺序不变，观察图b，我们可以采取如下两种做法：

    1）将节点p的左子树直接接到其父节点f上，作为f的左子树，将节点p的右子树接到节点s上，作为s的右子树（这里s为p的前驱节点，即p在有序序列中紧接在s的前面），而后删除节点p。采用这种方法删除节点p后，得到的二叉排序树的形状如下图中的图c所示：

    采取该方法删除节点的实现代码如下：

[cpp] view
plaincopy

1. /* 
2. 采用第一种算法从二叉排序树中删除指针p所指向的节点, 
3. 并在保持二叉排序树有序的情况下，将其左右子树重接到该二叉排序树中. 
4. 该函数主要用来被后面的删除函数调用 
5. */  
6. void delete_Node1(BSTree &p)  
7. {   
8.     BSTree q,s;  
9.     if(!p->lchild)     
10.     {   //如果左子树为空，则只需重接其右子树  
11.         //这里包含了左右子树均为空的情况  
12.         q = p;  
13.         p = p->rchild ;  
14.         free(q);  
15.     }  
16.     else if(!p->rchild)  
17.     {   //如果右子树为空，则只需重接其左子树  
18.         q = p;  
19.         p = p->lchild;  
20.         free(q);  
21.     }  
22.     else  
23.     {   //如果左右子树都不为空，我们采取第一种方法来重接左右子树，  
24.         //我们这里采取修改左子树的方法，也可以修改右子树，方法类似  
25.         s = p->lchild;       //取待删节点的左节点  
26.   
27.         //一直向右，最终s为待删节点的前驱节点  
28.         //如果将各节点元素按从小到大顺序排列成一个序列，  
29.         //则某节点的前驱节点即为序列中该节点的前面一个节点  
30.         while(s->rchild)  
31.             s = s->rchild;  
32.         s->rchild = p->rchild;    //将p的右子树接为s的右子树  
33.         q = p;  
34.         p = p->lchild;       //将p的左子树直接接到其父节点的左子树上  
35.         free(q);  
36.     }  
37. }  

    2）将节点s的右子树重接到其父节点上，作为其父节点的右子树，而后用s替换掉带删节点p。采取这种方法删除节点p后，得到的二叉排序树的形状如上图中的图d所示。采用该方法删除节点的实现代码如下：

[cpp] view
plaincopy

1. /* 
2. 采用第二种算法从二叉排序树中删除指针p所指向的节点, 
3. 并在保持二叉排序树有序的情况下，将其左右子树重接到该二叉排序树中. 
4. 该函数主要用来被后面的删除函数调用 
5. */  
6. void delete_Node2(BSTree &p)  
7. {  
8.     BSTree q,s;       
9.     if(!p->lchild)     
10.     {   //如果左子树为空，则只需重接其右子树  
11.         //这里包含了左右子树均为空的情况  
12.         q = p;  
13.         p = p->rchild ;  
14.         free(q);  
15.     }  
16.     else if(!p->rchild)  
17.     {   //如果右子树为空，则只需重接其左子树  
18.         q = p;  
19.         p = p->lchild;  
20.         free(q);  
21.     }  
22.     else  
23.     {   //如果左右子树都不为空，我们采取第二种方法来重接左右子树，  
24.         //我们这里采取修改左子树的方法，也可以修改右子树，方法类似  
25.         q = p;  
26.         s = p->lchild;       //取待删节点的左节点  
27.         while(s->rchild)       
28.         {   //一直向右，最终s为待删节点的前驱节点。  
29.             //如果将各节点元素按从小到大顺序排列成一个序列，  
30.             //则某节点的前驱节点即为序列中该节点的前面一个节点  
31.             q = s;  
32.             s = s->rchild;  
33.         }  
34.         //用s来替换待删节点p  
35.         p->data = s->data;    
36.         //根据情况，将s的左子树重接到q上  
37.         if(p != q)  
38.             q->rchild = s->lchild;  
39.         else  
40.             q->lchild =s->lchild;  
41.         free(s);  
42.     }  
43. }  

完整源码

    上面重点分析了删除节点的思路和过程，下面给出二叉排序树各种操作实现的完整C代码（含测试代码并加有详细注释）：

[cpp] view
plaincopy

1. /********************************* 
2. 二叉排序树的相关操作实现 
3. Author:兰亭风雨  Date：2014-02-23 
4. Email:zyb_maodun@163.com 
5. **********************************/  
6. #include<stdio.h>  
7. #include<stdlib.h>  
8.   
9. typedef struct Node  
10. {  
11.     int data;  
12.     struct Node *lchild;