二叉排序树（查询、插入、删除）

“二叉排序树，又称为二叉查找树。它或者是一颗空树，或者具有下列性质的二叉树。

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

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

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

构造一颗二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。” 

通俗的讲，二叉排序树的本质就是一颗二叉树，只是关键字的排序比较有规律，能够利用二叉树的递归特性进行很方便的操作。在对于二叉排序树的基本操作中，包括：根据数据集构建二叉排序树（没有要查找的关键字，就插入）、查找、删除。其中，删除操作时最麻烦的，插入和查找的思路很像，下面详解。

1、二叉排序树的查找操作

首先定义一个二叉树的结构。

[cpp] view plain copy
 
  1. /* 二叉排序树的节点结构定义 */  
  2. typedef struct BiTNode  
  3. {  
  4.     int data;  
  5.     struct BiTNode *lchild, *rchild;  
  6. } BiTNode, *BiTree;  

查找操作思路：

    先查找其根节点，如果根节点的数据与key值相等，则返回该根节点，并且返回TRUE；

    否则， 如果key值大于根节点，则查询其右子树；

                如果小于根节点，则查询其左子树。

代码如下：

[cpp] view plain copy
 
  1. int SearchBST( BiTree T, int key, BiTree f, BiTree *p )  
  2. {  
  3.     /* 递归查找二叉排序树T中是否存在key */  
  4.     /* 指针f指向T的双亲，其初始调用值为NULL */  
  5.     /* 若查找成功，则指针p指向该数据元素节点，并返回TRUE */  
  6.     /* 否则指针p指向查找路径上访问的最后一个节点并返回FALSE */  
  7.     if( !T )  
  8.     {     
  9.         *p = f;     //这是f唯一被用到的位置。  
  10.         return FALSE;     
  11.     }  
  12.     else  
  13.     {  
  14.         if( key == T->data )  
  15.         {   *p = T;     return TRUE; }  
  16.         else if( key > T->data )  
  17.             return SearchBST( T->rchild, key, T, p );        /* 在右子树继续查找 */  
  18.         else      
  19.             return SearchBST( T->lchild, key, T, p );        /* 在左子树继续查找 */  
  20.         }  
  21. }  
  22.   
  23. int SearchBST2( BiTree T, int key, BiTree f, BiTree *p )  
  24. {  
  25.     /*非递归*/  
  26.     BiTree s;  
  27.     if( !T )  
  28.     {   *p = f;     return FALSE;   }  
  29.     else  
  30.     {  
  31.         while( T )  
  32.         {  
  33.             if( key == T->data )  
  34.             {   *p = T;     return TRUE;    }  
  35.             if( key > T->data )  
  36.             {   s = T;  T = T->rchild;       }  
  37.             else  
  38.             {   s = T;  T = T->lchild;       }  
  39.         }  
  40.         *p = s;  
  41.         return FALSE;  
  42.     }  
  43. }  


2、二叉排序树的插入操作

代码如下：

[cpp] view plain copy
 
  1. int InsertBST1( BiTree *T, int key )  
  2. {  
  3.     /* 当二叉排序树T中不存在关键字等于key的数据元素时 */  
  4.     /* 插入key并返回TRUE，否则返回FALSE */  
  5.     /* 调用查找函数SearchBST，非递归 */  
  6.     BiTree p, s;  
  7.     if( !SearchBST2( *T, key, NULL, &p ) )  
  8.     {  
  9.         s = (BiTree)malloc(sizeof(BiTNode));  
  10.         s->data = key;  
  11.         s->lchild = s->rchild = NULL;  
  12.         if( !p )  
  13.             *T = s;             /* 插入s为根节点，此前树为空树 */  
  14.         else if( key > p->data )  
  15.             p->rchild = s;       /* 插入s为右孩子 */  
  16.         else  
  17.             p->lchild = s;       /* 插入s为左孩子 */  
  18.         return TRUE;  
  19.     }  
  20.     return FALSE;  
  21. }  
  22.   
  23. int InsertBST2( BiTree *T, int key )  
  24. {  
  25.     /* 当二叉排序树T中不存在关键字等于key的数据元素时 */  
  26.     /* 插入key并返回TRUE，否则返回FALSE */  
  27.     /* 未调用查找函数，递归插入 */  
  28.     if( !(*T) )                                 /* 树为空， */  
  29.     {  
  30.         (*T) = (BiTree)malloc(sizeof(BiTNode)); /* 这个位置要留心，要重新分配空间，*T为空，说明未曾分配空间 */  
  31.         (*T)->data = key;  
  32.         (*T)->lchild = (*T)->rchild = NULL;  
  33.         return TRUE;  
  34.     }  
  35.     if( key == (*T)->data )  
  36.         return FALSE;  
  37.     if( key > (*T)->data )          
  38.         return InsertBST2( &((*T)->rchild), key );       /* 插入右孩子 */  
  39.     else  
  40.         return InsertBST2( &((*T)->lchild), key );       /* 插入左孩子 */  
  41. }  

3、二叉树的删除操作（相对复杂一些）

    删除节点有三种情况分析：

        a. 叶子节点；(直接删除即可)




 b. 仅有左或右子树的节点；（上移子树即可）

 c. 左右子树都有的节点。( 用删除节点的直接前驱或者直接后继来替换当前节点，调整直接前驱或者直接后继的位置)

代码如下：

[cpp] view plain copy
 
  1. int DeleteBST(BiTree *T, int key)  
  2. {  
  3.     /* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素节点 */  
  4.     /* 并返回TRUE；否则返回FALSE */  
  5.     if( !(*T))  
  6.         return FALSE;   /* 不存在关键字等于key的数据元素 */  
  7.     else  
  8.     {  
  9.         if( key == (*T)->data )  
  10.             Delete(T);  
  11.         else if( key < (*T)->data)  
  12.             return DeleteBST(&(*T)->lchild, key);  
  13.         else  
  14.             return DeleteBST(&(*T)->rchild, key);  
  15.     }  
  16. }  
  17.   
  18. int Delete(BiTree *p)  
  19. {  
  20.     /* 从二叉排序树中删除节点p， 并重接它的左或右子树 */  
  21.     BiTree q, s;  
  22.     if(  !(*p)->lchild && !(*p)->rchild ) /* p为叶子节点 */  
  23.         *p = NULL;  
  24.     else if( !(*p)->lchild ) /* 左子树为空，重接右子树 */  
  25.     {  
  26.         q = *p;   
  27.         *p = (*p)->rchild;  
  28.         free(q);  
  29.     }  
  30.     else if( !(*p)->rchild ) /* 右子树为空，重接左子树 */  
  31.     {  
  32.         q = *p;  
  33.         *p = (*p)->lchild;         
  34.         free(q);  
  35.     }  
  36.     else                        /* 左右子树均不为空 */  
  37.     {  
  38.         q = *p;  
  39.         s = (*p)->lchild;  
  40.         while(s->rchild)     /* 转左，然后向右走到尽头*/  
  41.         {  
  42.             q = s;  
  43.             s = s->rchild;  
  44.         }  
  45.         (*p)->data = s->data;  
  46.         if( q != *p )               /* 判断是否执行上述while循环 */  
  47.             q->rchild = s->lchild;    /* 执行上述while循环，重接右子树 */   
  48.         else  
  49.             q->lchild = s->lchild;    /* 未执行上述while循环，重接左子树 */  
  50.         free(s);  
  51.     }  
  52.     return TRUE;  
  53. }  

总结：二叉树以链式方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需要修改链接指针节课。插入删除的时间性能比较好。而丢与二拆排序树的查找，走的就是从根节点到要查找的节点的路径，其比较次数等于给定值的节点在二叉排序树的层数。极端情况，最少为1次，即根节点就是要找的节点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。

例如{62,88,58,47,35,73,51,99,37,93}这样的数组，我们可以构建一颗正常的二叉排序树。但是如果数组元素的次序是从小到大有序，如{35,37,47,51,58,62,73,88，93,99}，则二拆排序树就成了极端的单支树，注意它依然是一颗二叉排序树。同样是查找节点99，左图只需要两次比较，而右图就需要10次比较才可以得到结果，而这差异很大。


也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同。

这样就延续到了另一篇博客中要讲解的平衡二叉树。

附加：完整代码

[cpp] view plain copy
 
  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #define TRUE 1  
  4. #define FALSE 0  
  5.   
  6. /* 二叉排序树的节点结构定义 */  
  7. typedef struct BiTNode  
  8. {  
  9.     int data;  
  10.     struct BiTNode *lchild, *rchild;  
  11. } BiTNode, *BiTree;  
  12.   
  13.   
  14. int SearchBST( BiTree T, int key, BiTree f, BiTree *p )  
  15. {  
  16.     /* 递归查找二叉排序树T中是否存在key */  
  17.     /* 指针f指向T的双亲，其初始调用值为NULL */  
  18.     /* 若查找成功，则指针p指向该数据元素节点，并返回TRUE */  
  19.     /* 否则指针p指向查找路径上访问的最后一个节点并返回FALSE */  
  20.     if( !T )  
  21.     {     
  22.         *p = f;     //这是f唯一被用到的位置。  
  23.         return FALSE;     
  24.     }  
  25.     else  
  26.     {  
  27.         if( key == T->data )  
  28.         {   *p = T;     return TRUE; }  
  29.         else if( key > T->data )  
  30.             return SearchBST( T->rchild, key, T, p );        /* 在右子树继续查找 */  
  31.         else      
  32.             return SearchBST( T->lchild, key, T, p );        /* 在左子树继续查找 */  
  33.         }  
  34. }  
  35.   
  36. int SearchBST2( BiTree T, int key, BiTree f, BiTree *p )  
  37. {  
  38.     /*非递归*/  
  39.     BiTree s;  
  40.     if( !T )  
  41.     {   *p = f;     return FALSE;   }  
  42.     else  
  43.     {  
  44.         while( T )  
  45.         {  
  46.             if( key == T->data )  
  47.             {   *p = T;     return TRUE;    }  
  48.             if( key > T->data )  
  49.             {   s = T;  T = T->rchild;       }  
  50.             else  
  51.             {   s = T;  T = T->lchild;       }  
  52.         }  
  53.         *p = s;  
  54.         return FALSE;  
  55.     }  
  56. }  
  57.   
  58.   
  59. int InsertBST1( BiTree *T, int key )  
  60. {  
  61.     /* 当二叉排序树T中不存在关键字等于key的数据元素时 */  
  62.     /* 插入key并返回TRUE，否则返回FALSE */  
  63.     /* 调用查找函数SearchBST，非递归 */  
  64.     BiTree p, s;  
  65.     if( !SearchBST2( *T, key, NULL, &p ) )  
  66.     {  
  67.         s = (BiTree)malloc(sizeof(BiTNode));  
  68.         s->data = key;  
  69.         s->lchild = s->rchild = NULL;  
  70.         if( !p )  
  71.             *T = s;             /* 插入s为根节点，此前树为空树 */  
  72.         else if( key > p->data )  
  73.             p->rchild = s;       /* 插入s为右孩子 */  
  74.         else  
  75.             p->lchild = s;       /* 插入s为左孩子 */  
  76.         return TRUE;  
  77.     }  
  78.     return FALSE;  
  79. }  
  80.   
  81. int InsertBST2( BiTree *T, int key )  
  82. {  
  83.     /* 当二叉排序树T中不存在关键字等于key的数据元素时 */  
  84.     /* 插入key并返回TRUE，否则返回FALSE */  
  85.     /* 未调用查找函数，递归插入 */  
  86.     if( !(*T) )                                 /* 树为空， */  
  87.     {  
  88.         (*T) = (BiTree)malloc(sizeof(BiTNode)); /* 这个位置要留心，要重新分配空间，*T为空，说明未曾分配空间 */  
  89.         (*T)->data = key;  
  90.         (*T)->lchild = (*T)->rchild = NULL;  
  91.         return TRUE;  
  92.     }  
  93.     if( key == (*T)->data )  
  94.         return FALSE;  
  95.     if( key > (*T)->data )          
  96.         return InsertBST2( &((*T)->rchild), key );       /* 插入右孩子 */  
  97.     else  
  98.         return InsertBST2( &((*T)->lchild), key );       /* 插入左孩子 */  
  99. }  
  100.   
  101.   
  102. void order(BiTree t)//中序输出    
  103. {    
  104.     if(t == NULL)    
  105.         return ;    
  106.     order(t->lchild);    
  107.     printf("%d ", t->data);    
  108.     order(t->rchild);    
  109. }   
  110.   
  111.   
  112.   
  113. int DeleteBST(BiTree *T, int key)  
  114. {  
  115.     /* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素节点 */  
  116.     /* 并返回TRUE；否则返回FALSE */  
  117.     if( !(*T))  
  118.         return FALSE;   /* 不存在关键字等于key的数据元素 */  
  119.     else  
  120.     {  
  121.         if( key == (*T)->data )  
  122.             Delete(T);  
  123.         else if( key < (*T)->data)  
  124.             return DeleteBST(&(*T)->lchild, key);  
  125.         else  
  126.             return DeleteBST(&(*T)->rchild, key);  
  127.     }  
  128. }  
  129.   
  130. int Delete(BiTree *p)  
  131. {  
  132.     /* 从二叉排序树中删除节点p， 并重接它的左或右子树 */  
  133.     BiTree q, s;  
  134.     if(  !(*p)->lchild && !(*p)->rchild ) /* p为叶子节点 */  
  135.         *p = NULL;  
  136.     else if( !(*p)->lchild ) /* 左子树为空，重接右子树 */  
  137.     {  
  138.         q = *p;   
  139.         *p = (*p)->rchild;  
  140.         free(q);  
  141.     }  
  142.     else if( !(*p)->rchild ) /* 右子树为空，重接左子树 */  
  143.     {  
  144.         q = *p;  
  145.         *p = (*p)->lchild;       /* 不太理解 */  
  146.         free(q);  
  147.     }  
  148.     else                        /* 左右子树均不为空 */  
  149.     {  
  150.         q = *p;  
  151.         s = (*p)->lchild;  
  152.         while(s->rchild)     /* 转左，然后向右走到尽头*/  
  153.         {  
  154.             q = s;  
  155.             s = s->rchild;  
  156.         }  
  157.         (*p)->data = s->data;  
  158.         if( q != *p )               /* 判断是否执行上述while循环 */  
  159.             q->rchild = s->lchild;    /* 执行上述while循环，重接右子树 */   
  160.         else  
  161.             q->lchild = s->lchild;    /* 未执行上述while循环，重接左子树 */  
  162.         free(s);  
  163.     }  
  164.     return TRUE;  
  165. }  
  166. void main()  
  167. {  
  168.     int i;  
  169.     int a[10] = {62,88,58,47,35,73,51,99,37,93};  
  170.     BiTree T = NULL;  
  171.     for( i = 0; i < 10; i++ )  
  172.         InsertBST1(&T, a[i]);  
  173.     printf("中序遍历二叉排序树： ");  
  174.     order(T);  
  175.     printf(" ");  
  176.     printf("删除58后，中序遍历二叉排序树： ");  
  177.     DeleteBST(&T,58);  
  178.     order(T);  
  179.     printf(" ");  
  180. }  



 原文：http://blog.csdn.net/wangyunyun00/article/details/23708055

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Ph-one/p/7908758.html