首页 > 代码库 > 二叉排序树的建立、先序/中序/后序遍历、查找

二叉排序树的建立、先序/中序/后序遍历、查找

2024-10-05 12:58:39   215人阅读

一、定义与性质

 

定义 
　　二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树.

性质
　　（1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
　　（2） 二叉排序树中，各结点关键字是惟一的。
  注意：实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的"小于"改为"大于等于"，或将BST性质(2)里的"大于"改为"小于等于"，甚至可同时修改这两个性质。
　　（3） 按中序遍历该树所得到的中序序列是一个递增有序序列。

 

二、插入与删除

       插入与删除操作是二叉排序树中最常用也是最重要的两个操作。

       插入过程是：
　　(a)若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；
　　(b)若二叉排序树T不为空，则将key和根的关键字比较：
         　　(i)若二者相等，则说明树中已有此关键字key，无须插入。
         　　(ii)若key<T→key，则将key插入根的左子树中。
         　　(iii)若key>T→key，则将它插入根的右子树中。
　　子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。

     删除过程：

     

(1) 进行查找
      　查找时，令p指向当前访问到的结点，parent指向其双亲(其初值为NULL)。若树中找不到被删结点则返回，否则被删结点是*p。
(2) 删去*p。
      　删*p时，应将*p的子树(若有)仍连接在树上且保持BST性质不变。按*p的孩子数目分三种情况进行处理。

         删除*p结点的三种情况
         a.*p是叶子(即它的孩子数为0)
      　无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。

   

         b.*p只有一个孩子*child
      　只需将*child和*p的双亲直接连接后，即可删去*p。
            注意：*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态。

 

            c.*p有两个孩子
      　先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。

 

三、代码清单

 

[cpp] view plain copy
 
  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #define maxSize 20    
  4. #define maxWidth 20    
  5.   
  6. typedef int KeyType; //假定关键字类型为整数  
  7. typedef struct node { //结点类型  
  8.     KeyType key; //关键字项  
  9.     struct node *lchild,*rchild;//左右孩子指针  
  10. } BSTNode,BSTree;  
  11. //typedef BSTNode *BSTree; //BSTree是二叉排序树的类型  
  12.   
  13. //先序遍历    
  14. void preOrder(BSTree *BT)    
  15. {    
  16.     if(BT!= NULL)    
  17.     {    
  18.         printf("%d-",BT->key);    
  19.         preOrder(BT->lchild);    
  20.         preOrder(BT->rchild);    
  21.   
  22.     }    
  23. }    
  24.   
  25. //中序遍历    
  26. void inOrder(BSTree *BT)    
  27. {    
  28.     if(BT!= NULL)    
  29.     {    
  30.         inOrder(BT->lchild);    
  31.         printf("%d-",BT->key);    
  32.         inOrder(BT->rchild);    
  33.     }    
  34. }    
  35.   
  36. //后序遍历    
  37. void postOrder(BSTree *BT)    
  38. {    
  39.     if(BT!= NULL)    
  40.     {    
  41.         postOrder(BT->lchild);    
  42.         postOrder(BT->rchild);    
  43.         printf("%d-",BT->key);    
  44.     }    
  45. }   
  46.   
  47. //层次法打印二叉排序树  
  48. /* 以先序遍历的方式打印二叉排序树 */    
  49. void dispTree(BSTree *BT)    
  50. {    
  51.     BSTree *stack[maxSize],*p;    
  52.     int level[maxSize][2],top,n,i,width=4;    
  53.     if(BT!=NULL)    
  54.     {    
  55.         printf("Display a tree by hollow means.\n");    
  56.         top=1;    
  57.         stack[top]=BT;//push root point to stack.    
  58.         level[top][0]=width;    
  59.           
  60.     while(top>0)    
  61.         {    
  62.             p=stack[top];    
  63.             n=level[top][0];    
  64.             for(i=1;i<=n;i++)    
  65.                 printf(" ");    
  66.             printf("%d",p->key);    
  67.             for(i=n+1;i<maxWidth;i+=2)    
  68.                 printf("--");    
  69.             printf("\n");    
  70.             top--;    
  71.               
  72.       if(p->rchild!=NULL) //右子树先入栈，后出栈   
  73.             {    
  74.                 top++;    
  75.                 stack[top]=p->rchild;    
  76.                 level[top][0]=n+width;    
  77.                 level[top][1]=2;    
  78.             }    
  79.               
  80.       if(p->lchild!=NULL)  //左子树后入栈，先出栈  
  81.             {    
  82.                 top++;    
  83.                 stack[top]=p->lchild;    
  84.                 level[top][0]=n+width;    
  85.                 level[top][1]=1;    
  86.             }  //if  
  87.         }  //while  
  88.     }  //if  
  89. } //dispTree()   
  90.   
  91. /* 向二叉排序树中加入一个结点  
  92. 要改变指针,需要传递指针的指针*/  
  93. /* return 0表示插入成功, return -1表示插入失败 */   
  94. int InsertNode(BSTree **tree, KeyType key)  
  95. {  
  96.     BSTNode *p= NULL, *parent = NULL;  
  97.     BSTNode *pNewNode = (BSTNode *)malloc(sizeof(BSTNode));  
  98.     if (pNewNode==NULL)  
  99.     {  
  100.         return -1;  
  101.     }  
  102.       
  103.   /* 新建结点赋值,特别是左右子结点指针要赋值为NULL，叶子节点 */  
  104.   /* 二叉排序树新插入的结点都是叶子节点 */   
  105.     pNewNode->key = key;  
  106.     pNewNode->lchild = NULL;  
  107.     pNewNode->rchild = NULL;  
  108.       
  109.   /* 二叉排序树是空树 */  
  110.     if (*tree==NULL)  
  111.     {  
  112.         *tree = pNewNode;  
  113.         return 0;  
  114.     }  
  115.     else  
  116.     {  
  117.   
  118.         p = *tree;  
  119.         /* 寻找插入位置 */  
  120.         while (NULL != p) /* 待插入的结点以叶子节点方式插入 */  
  121.         {  
  122.             /* key值已在二叉排序树中 */  
  123.             if (p->key == key)  
  124.             {  
  125.                 return 0;  
  126.             }  
  127.             else  
  128.             {  
  129.                 parent = p;  
  130.                 p = (p->key < key) ? p->rchild : p->lchild; //key是待插入结点   
  131.             }  
  132.         } //while，结束时NULL == p,此时已经到了叶子节点位置   
  133.         if (parent->key < key)  
  134.         {  
  135.             parent->rchild = pNewNode;  
  136.         }  
  137.         else  
  138.         {  
  139.             parent->lchild = pNewNode;  
  140.         } //else   
  141.         return 0;  
  142.     } //else  
  143. } //InsertNode   
  144.   
  145. //删除节点  
  146.  /* 通过值查找并删除一个结点 */  
  147.  int delNode(BSTree **tree, KeyType key)  
  148.  {  
  149.      BSTNode *p = NULL, *q = NULL, *parent = NULL, *child = NULL;  
  150.      p = *tree;  
  151.      /* parent为NULL表示根结点的父亲为NULL */  
  152.      while (NULL != p)  
  153.      {  
  154.          if (p->key == key) //此时找到待删除的结点p   
  155.          {  
  156.              break;  
  157.          }  
  158.          else  
  159.          { parent = p;  
  160.            p = (p->key < key) ? p->rchild : p->lchild;  
  161.          }  
  162.      } //while   
  163.      /* p为NULL时， 表示没有找到结点值为key的结点 */  
  164.      if (NULL == p) /* 到达叶子节点仍未查找到要删除的结点 */   
  165.      {  
  166.          return -1;  
  167.      }  
  168.      /* p, q现在都是保存了待删结点指针 */  
  169.      q = p; //此时p->key == key   
  170.        
  171.      /* 待删结点有两个儿子结点，进行一下转化 */  
  172.      if (NULL != p->lchild && NULL != p->rchild)  
  173.      {  
  174.     //找中序后继，先右拐，然后左走到底  
  175.          parent = p;  
  176.          p = p->rchild; /* 进入右子树 */  
  177.          while (NULL != p->lchild)  
  178.          {  
  179.              parent = p;  
  180.              p = p->lchild;  
  181.          }  
  182.          /* p中保存了待删结点右子树中最左下的结点指针， parent中就保存了该结点父亲指针 */  
  183.          child = p->rchild;  
  184.      }  
  185.      else if(NULL == p -> lchild)  
  186.           child = p -> rchild;  
  187.      else  
  188.          child = p -> lchild;   
  189.        
  190.      /* parent保存待删结点的父亲结点指针， child保存了待删结点的儿子结点 
  191.       
  192. //实际删除的是待删节点的直接后继，下面是删除直接后继的过程，（待删结点至多只有一个儿子， 有两个会转化为0个或1个右结点） 
  193.      */  
  194.      // 待删结点是根结点,且只有一个儿子  
  195.      if (NULL == parent)  
  196.      {  
  197.           if(p->lchild!=NULL) *tree = p->lchild;  
  198.           else *tree = p->rchild;  
  199.      }  
  200.      else  
  201.      {  
  202.          /*待删结点是父亲结点的左儿子*/  
  203.          if (parent->lchild == p)  
  204.          {  
  205.              parent->lchild = child;  
  206.          }  
  207.          else  
  208.          {  
  209.              parent->rchild = child;  
  210.          }  
  211.     //将实际删除的节点的key值赋给原先要删除的节点  
  212.          if (p != q)  
  213.          {  
  214.              q->key = p->key;  
  215.          }  
  216.      }  
  217.      free(p);  
  218.      return 0;  
  219.  } //delNode  
  220.   
  221. //二叉排序树查找  
  222. BSTNode* SearchBST(BSTree *T,KeyType key)  
  223. { //在二叉排序树T上查找关键字为key的结点,成功时返回该结点位置,否则返回NUll  
  224.     if(T==NULL) //递归的终结条件  
  225.         return NULL; //T为空,查找失败;  
  226.     if(key==T->key)  
  227.         //成功,返回找到的结点位置  
  228.     {  
  229.         printf("Got it!");  
  230.         return T;  
  231.     }  
  232.   
  233.     if(key<T->key)  
  234.         return SearchBST(T->lchild,key);  
  235.     else  
  236.         return SearchBST(T->rchild,key);//继续在右子树中查找  
  237. } //SearchBST  
  238.   
  239. int main()  
  240. {  
  241.     int n;    
  242.     BSTree *B=NULL;  
  243.     printf("Input number to initialize a BSTree:");  
  244.     while(1)  
  245.     {  
  246.         scanf("%d",&n);  
  247.         if(n==0) break; //遇到0时停止输入,0并不入树   
  248.         InsertNode(&B, n);  
  249.     }     
  250.     dispTree(B);   
  251.     printf("PreOrder：");  
  252.     preOrder(B);  
  253.     printf("\n");  
  254.     printf("Search a node:");  
  255.     scanf("%d",&n);  
  256.     SearchBST(B,n);  
  257.     printf("\n");  
  258.     printf("Delete a node:");  
  259.     scanf("%d",&n);  
  260.     delNode(&B,n);  
  261.     dispTree(B);   
  262.     printf("PreOrder：");  
  263.     preOrder(B);  
  264.     printf("\n");  
  265.     system("pause");  
  266.     return 1;  
  267. }  



四、程序运行结果

 


技术分享

 

出处：http://blog.csdn.NET/silangquan/article/details/8065243

二叉排序树的建立、先序/中序/后序遍历、查找


联系
我们