二叉排序树(BST)构造与应用

约定不等于承诺〃 2022-07-29 09:29 198阅读 0赞

**二叉排序树(BST)构造与应用**

本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。

本博文作为学习资料整理。源代码是VC++ 6.0上可执行程序，我挪到了VS2010中执行。

在VS2010中新建C++ Win32 控制台应用程序项目，创建结果截图：

![Center][]

二叉排序树(BST)：又称二叉查找树，其定义为：二叉排序树或者是空树，或者是满足以下性质的二叉树。  
(1) 若它的左子树非空，则左子树上所有记录的关键字均小于根记录的值。  
(2) 若它的右子树非空，则右子树上所有记录的关键字均大于根记录的值。  
(3) 左、右子树本身又各是一棵二叉排序树。  
按中序遍历BST所得到的中序序列是一个递增有序序列。  
二叉排序树的类型定义：

typedef struct BSTNode
     {
       KeyType key;     //数据域
       BSTNode *lchild;
       BSTNode *rchild;
     }

**1.二叉排序树的插入操作**  
(1)如果二叉排序树T为空，则创建一个关键字为k的结点，将其作为根结点。  
(2)否则将k和根结点的关键字进行比较，如果相等则返回，如果k小于根结点的关键字则插入根结点的左子树中，否则插入根结点的右子树中。  
二叉排序树的插入算法：

int InsertBST(BSTNode *p, KeyType k)
      {
         if(p==NULL)
         {
           p=(BSTNode*)malloc(sizeof(BSTNode));
           p->key=k;
           p->lchild=p->rchild=NULL;
           return 1;
         }
         else if(k==p->key)
           return 0;
         else if(k<p->key)
           return InsertBST(p->lchild, k);
         else
           return InsertBST(p->rchild, k);
      }

二叉排序树的生成算法：

BSTNode *CreateBST(KeyType A[], int n)
      {
        BSTNode *bt=NULL;
        int i=0;
        while(i<n)
        {
          InsertBST(bt, A[i]);
          i++;
        }
        return bt;
      }

示例：输入\{50,16,56,52,8\}生成二叉排序树

![SouthEast][]

**2.二叉排序树的查找操作**  
首先将需要查找的值与根结点比较，如果相等则查找成功，算法终止；如果比根结点小则左子树中查找，如果比根结点大则到右子树查找。  
二叉排序树的查找算法的递归形式

BSTree SearchBST(BSTree t, int k)
       {
         if(t==null || k==t->key)
           return t;
         else if(k<t->key)
           return SearchBST(t->lchild, k);
         else
           return SearchBST(t->rchild, k);
       }

二叉排序树的查找算法的非递归形式

BSTree SearchBST2(BSTree t, int k)
       {
         BSTree p=t;
         while(p!=null && p->key!=k)
         {
           if(k<p->key)
             p=p->lchild;
           else
             p=p->rchild;
         }
         return p;
       }

查找过程演示图：

![SouthEast 1][]

**3.二叉排序树的删除操作**

删除二叉排序树的某一个结点的步骤如下：  
1)查找待删除的结点  
查找结点时，令\*p指向其访问到的结点，\*f指向其双亲结点。若树中找不到被删结点时返回NULL，否则被删除结点是\*p，返回\*p。  
2)删除结点  
假设要删除二叉排序树中的一个结点\*p，其双亲结点为\*f，则删除结点\*p时，需考虑以下3种情况：  
(1)\*p为叶子结点。  
在这种情况下，可以将\*p结点直接删除。  
p为左子树：  
f->lchild=NULL;  
free(p);  
p为右子树:  
f->rclild=NULl;

free(p);

操作示意图如下：

![SouthEast 2][]

(2)\*p只有左子树，或只有右子树。  
对于这种情况，可以直接将\*p的左子树或右子树与其双亲结点\*f相连，然后删除\*p。  
p为f的左孩子，p的左子树非空：  
f->lchild=p->lchild;  
free(p);  
p为f的左孩子，p的右子树非空：  
f->lchild=p->rchild;  
free(p);  
p为f的右孩子，p的左子树非空：  
f->rchild=p->lchild;  
free(p);  
p为f的右孩子，p的右子树非空：  
f->rchild=p->rchild;

free(p);

操作示意图如下：

![SouthEast 3][]

(3)\*p有左右子树。  
方法一：设\*s为\*p结点在中序序列中的直接前驱，将\*p的左子树改为\*f的左子树，将\*p的右子树改为\*s的右子树。  
f->lchild=p->lchild;  
s->rchild=p->rchild;

free(p);

操作示意图如下：

![SouthEast 4][]

方法二：用\*p结点在中序序列中的直接前驱(或后继)\*s代替\*p，然后再从二叉排序树中将\*s删除。这时如果\*s为\*p的直接前驱，则\*s只有左子树(或者没有孩子)，则删除\*s可以按照删除\*p的其余两种情况处理。如果\*s为\*p的直接后继，则\*s只有右子树(或者没有孩子)，删除\*s同理可以按照删除\*p的其余两种情况处理。

# 附录  #

#  A.二叉排序树的构造算法： #

注:判定一棵二叉树是二叉排序树可以采用中序遍历算法将树上的顶点输出，如果得到的中序 序列是有序的，则说明这棵二叉树是二叉排序树，否则不是二叉排序树。

#include<stdio.h>
      #include<stdlib.h>
      #define MAX 100
      typedef struct tnode
      {
        int data;
        struct tnode *lchild, *rchild;
      }TNODE;
    
      void create();
      void insert(int m);   //插入二叉排序树的结点
      void inOrder(TNODE *ptr);  //中序遍历
    
      TNODE *root=NULL;
    
      void inOrder(TNODE *ptr)
      {
        if(ptr!=NULL)
        {
          inOrder(ptr->lchild);
          printf("%d ", ptr->data);
          inOrder(ptr->rchild);
        }
      }
    
      void create()
      {
        int n, i;
        int k[MAX];
        printf("Please input the node number:\n");
        scanf("%d", &n);
        for(i=0; i<n; i++)
          scanf("%d",&k[i]);
        for(i=0; i<n; i++)
          insert(k[i]);
      }
    
      void insert(int m)
      {
        TNODE *p1, *p2;
        if(root==NULL)
        {
          root=(TNODE *)malloc(sizeof(TNODE));
          root->data=m;
          root->lchild=root->rchild=NULL;
        }
        else
        {
          p1=root;
          while(m!=p1->data)
          {
            if((m<p1->data) && (p1->lchild!=NULL))
              p1=p1->lchild;
            else if((m>p1->data) && (p1->rchild!=NULL))
              p1=p1->rchild;
            else if((m<p1->data) && (p1->lchild==NULL))
            {
              p2=(TNODE *)malloc(sizeof(TNODE));
              p2->data=m;
              p2->lchild=p2->rchild=NULL;
              p1->lchild=p2;
              return;
            }
            else if((m>p1->data) && (p1->rchild==NULL))
            {
              p2=(TNODE *)malloc(sizeof(TNODE));
              p2->data=m;
              p2->lchild=p2->rchild=NULL;
              p1->rchild=p2;
              return;
            }
          }
        }
      }
    
      int main()
      {
        create();
        printf("\n");
        inOrder(root);
        printf("\n");
        return 0;
      }

Ctrl+F5运行SortTree.cpp输出结果如下：

![Center 1][]

#  B.求出二叉排序树T中小于x的最大元素和大于x的最小元素 #

在二叉排序树中，一个小于树中某个结点的最大元素，是在中序序列中这个结点的直接前驱；大于这个  
结点的最小元素，是在中序序列中这个结点的直接后继。  
其程序如下：

#include<stdio.h>
     #include<stdlib.h>
     #define MAX 100
     typedef struct tnode
     {
       int data;
       struct tnode *lchild, *rchild;
     }TNODE;
    
     int last=0;
     void create();
     void insert(int m);   //插入二叉排序树的结点
     void findMaxMin(int aim, TNODE *ptr);
    
     TNODE *root=NULL;
    
     void findMaxMin(int aim, TNODE *ptr)
     {
       if(ptr!=NULL)
       {
         findMaxMin(aim, ptr->lchild);
         if(last<aim && ptr->data>=aim)       //找到小于aim的最大元素
           printf("a=%d\n",last);
         if(last<=aim && ptr->data>aim)       //找到大于aim的最小元素
           printf("b=%d\n",ptr->data);
         last=ptr->data;
         findMaxMin(aim, ptr->rchild);
       }
     }
    
     void create()
     {
       int n, i;
       int k[MAX];
       printf("Please input the node number:\n");
       scanf("%d", &n);
       for(i=0; i<n; i++)
         scanf("%d",&k[i]);
       for(i=0; i<n; i++)
         insert(k[i]);
     }
    
     void insert(int m)
     {
       TNODE *p1, *p2;
       if(root==NULL)
       {
         root=(TNODE *)malloc(sizeof(TNODE));
         root->data=m;
         root->lchild=root->rchild=NULL;
       }
       else
       {
         p1=root;
         while(m!=p1->data)
         {
           if((m<p1->data) && (p1->lchild!=NULL))
             p1=p1->lchild;
           else if((m>p1->data) && (p1->rchild!=NULL))
             p1=p1->rchild;
           else if((m<p1->data) && (p1->lchild==NULL))
           {
             p2=(TNODE *)malloc(sizeof(TNODE));
             p2->data=m;
             p2->lchild=p2->rchild=NULL;
             p1->lchild=p2;
             return;
           }
           else if((m>p1->data) && (p1->rchild==NULL))
           {
             p2=(TNODE *)malloc(sizeof(TNODE));
             p2->data=m;
             p2->lchild=p2->rchild=NULL;
             p1->rchild=p2;
             return;
           }
         }
       }
     }
    
     int main()
     {
       int toBeFind;
       create();
       printf("\n");
       printf("Input the record to be finded! \n");
       scanf("%d", &toBeFind);
       findMaxMin(toBeFind, root);
       printf("\n");
       return 0;
     }

Ctrl+F5运行SortTree1.cpp输出结果如下：

![Center 2][]

[Center]: /images/20220728/19ffc9bf20f94825a5bda079f33369ab.png
[SouthEast]: /images/20220728/230e947ebd87402d93865b25a500819c.png
[SouthEast 1]: /images/20220728/ded2bb2f403c4804aecfc2585f5e7c87.png
[SouthEast 2]: /images/20220728/97d660429e664b149071dddbede97ebd.png
[SouthEast 3]: /images/20220728/acc6335425d347999a8e3335745e87d5.png
[SouthEast 4]: /images/20220728/ffad019a7efd4ae28dfa26daa0af6358.png
[Center 1]: /images/20220728/95dc6d547f1741ea9cf9ef88a995d7e8.png
[Center 2]: /images/20220728/56d7e9d6840b42a98fa9366ccb5396c0.png