【笔记】二叉排序树

  二叉排序树也称为二叉查找树。二叉排序树的查找是一种常用的动态查找方法。

1.二叉排序树的定义

  二叉排序树或者是一棵空二叉树，或者二叉树具有下列性质：

1. 如果二叉树的左子树不为空，则左子树上的每一个结点的值均小于其对应根结点的值。
2. 如果二叉树的右子树不为空，则右子树上的每一个结点的值均大于其对应根结点的值。
3. 该二叉树的左子树和右子树也满足性质1和性质2，即左子树和右子树也是一棵二叉排序树。

• 类型定义

typedef int KeyType;
typedef struct      /*元素的定义*/
{
    KeyType key;
}DataType;
typedef struct Node /*二叉排序树的类型定义*/
{
    DataType data;
    struct Node *lchild,*rchild;
}BiTreeNode,*BiTree;

---

2.二叉排序树的查找

  二叉排序树中每个结点的值都大于其所有左子树结点的值，而小于其所有右子树中结点的值，如果要查找与二叉树中某个关键字相等的结点，可以从根结点开始，与给定的关键字比较，如果相等，则查找成功；如果关键字小于根结点的值，则在其左子树中查找；如果给定的关键字大于根结点的值，则在其右子树中查找。

  在二叉排序树的查找过程中，查找某个结点的过程正好是走了从根结点到要查找结点的路径，其比较次数正好是路径长度+1，这类似于折半查找，与折半查找不同的是由n个结点构成的判定树是唯一的，而由n个结点构成的二叉排序树则不唯一。

BiTree BSTSearch(BiTree T,DataType x)
/*二叉排序树的查找，如果找到元素x，则返回指向结点的指针，否则返回NULL*/
{
    BiTreeNode *p;
    if(T!=NULL)                     /*如果二叉排序树不为空*/
    {
        p=T;
        while(p!=NULL)
        {
            if(p->data.key==x.key)  /*如果找到，则返回指向该结点的指针*/
                return p;
            else if(x.key<p->data.key)  /*如果关键字小于p指向的结点的值，则在左子树中查找*/
                p=p->lchild;
            else
                p=p->rchild;    /*如果关键字大于p指向的结点的值，则在右子树中查找*/
        }
    }
    return NULL;
}

• 二叉排序树的插入

  二叉排序树的结构不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值结点时再进行插入。新插入的即诶但那一定是一个新添加的叶子结点，并且是查找不成功时查找路径*问的最后一个结点的左孩子结点或右孩子结点。因此二叉排序树的插入操作过程其实就是二叉排序树的建立过程。
  算法实现过程中，需要设置一个指向下一个要访问结点的双亲结点指针parent，记下前驱结点的位置，以便在查找失败时进行插入操作。若在二叉树中查找x结束后返回NULL，说明查找失败，需要将x插入二叉排序树；若parent−>data.key<x.key，则需要将parent的左指针指向x，使x成为parent的左孩子结点；若parent−>data.key>x.key，则需要将parent的右指针指向x，使x成为parent的右孩子结点；若二叉排序树为空树，则使x称为根结点。

  因此构造二叉排序树的过程就是对一个无序的序列排序的过程，且每次插入结点都是叶子结点，在二叉排序树中的插入操作过程中，不需要移动结点，仅需要移动结点指针，实现较为容易。

int BSTInsert(BiTree *T,DataType x)
/*二叉排序树的插入操作，如果树中不存在元素x，则将x插入到正确的位置并返回1，否则返回0*/
{
    BiTreeNode *p,*cur,*parent=NULL;
    cur=*T;
    while(cur!=NULL)
    {
        if(cur->data.key==x.key)    /*如果二叉树中存在元素为x的结点，则返回0*/
            return 0;
        parent=cur;             /*parent指向cur的前驱结点*/
        if(x.key<cur->data.key)     /*如果关键字小于p指向的结点的值，则在左子树中查找*/
            cur=cur->lchild;
        else
            cur=cur->rchild;            /*如果关键字大于p指向的结点的值，则在右子树中查找*/
    }
    p=(BiTreeNode*)malloc(sizeof(BiTreeNode));  /*生成结点*/
    if(!p)
        exit(-1);
    p->data=x;
    p->lchild=NULL;
    p->rchild=NULL;
    if(!parent)                     /*如果二叉树为空，则第一结点成为根结点*/
        *T=p;
    else if(x.key<parent->data.key)     /*如果关键字小于parent指向的结点，则将x成为parent的左孩子*/
        parent->lchild=p;
    else                            /*如果关键字大于parent指向的结点，则将x成为parent的右孩子*/
        parent->rchild=p;
    return 1;   
}

4.二叉排序树的删除

  对于二叉树来说，删除树中的一个结点其实是删除有序序列的一个记录，只要在删除某个结点之后依旧保持二叉树的特性即可。
  假设要删除的结点由指针s指示，指针p指向s的双亲结点，设s为f的左孩子结点。删除一个结点分为如下3种情况讨论：

1. 如果s指向的结点为叶子结点，其左子树和右子树为空，删除叶子不会影响到树的结构特性，因此只需要修改p的指针即可。
2. 如果s指向的结点只有左子树或只有右子树，在删除了结点*s后，只需要将s的左子树sL或右子树sR作为f的左孩子，即p−>lchild=s−>child或p−>lchild=s−>rchild。
3. 若s存在左子树和右子树，在删除结点T之前，二叉排序树的中序序列为{…QLQ…XLXYLYTTRP…}，因此在删除了结点S之后，使该二叉树仍然保持原来的性质不变的调整方法有两种：一种是使结点T的左子树作为结点P的左子树，结点T的右子树作为结点Y的右子树；另一种是使结点T的直接前驱取代结点T，并删除T的直接前驱结点Y，然后令结点Y原来的左子树作为结点X的右子树。

int BSTDelete(BiTree *T,DataType x)
/*在二叉排序树T中存在值为x的数据元素时，删除该数据元素结点，并返回1，否则返回0 */
{ 
    if(!*T)                         /*如果不存在值为x的数据元素，则返回0*/
        return 0;
    else
    {
        if(x.key==(*T)->data.key)           /*如果找到值为x的数据元素，则删除该结点*/
            DeleteNode(T);
        else if((*T)->data.key>x.key)   /*如果当前元素值大于x的值，则在该结点的左子树中查找并删除之*/
            BSTDelete(&(*T)->lchild,x);
        else                        /*如果当前元素值小于x的值，则在该结点的右子树中查找并删除之*/
            BSTDelete(&(*T)->rchild,x);
        return 1;
    }
}


void DeleteNode(BiTree *s)
/*从二叉排序树中删除结点s，并使该二叉排序树性质不变*/
{ 
    BiTree q,x,y;
    if(!(*s)->rchild)       /*如果s的右子树为空，则使s的左子树成为被删结点双亲结点的左子树*/
    {
        q=*s;
        *s=(*s)->lchild;
        free(q);
    }
    else if(!(*s)->lchild)  /*如果s的左子树为空，则使s的右子树成为被删结点双亲结点的左子树*/
    {
        q=*s;
        *s=(*s)->rchild;
        free(q);
    }
    else                    
    /*如果s的左、右子树都存在，则使s的直接前驱结点代替s，并使其直接前驱结点的左子树成为其双亲结点的右子树结点*/
    {
        x=*s;
        y=(*s)->lchild;
        while(y->rchild)    /*查找s的直接前驱结点，y为s的直接前驱结点，x为y的双亲结点*/
        {
            x=y;
            y=y->rchild;
        }
        (*s)->data=y->data;         /*结点s被y取代*/
        if(x!=*s)               /*如果结点s的左孩子结点不存在右子树*/
            x->rchild=y->lchild; /*使y的左子树成为x的右子树*/
        else                    /*如果结点s的左孩子结点存在右子树*/
            x->lchild=y->lchild;    /*使y的左子树成为x的左子树*/
        free(y);
    }
}

  通过调用Delete(T)来完成删除当前结点的操作，而函数BSTDelete(&(*T)->lchild,x)和BSTDelete(&*T->rchild,x)则是实现在删除结点后，利用参数T->lchild和T->rchild完成连接左子树和右子树，使二叉排序树性质保持不变。

5.二叉排序树应用举例

  利用二叉树的插入算法创建一棵二叉排序树，然后输入一个元素，查找该元素是否存在，最后输出这棵树的中序序列。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
void DeleteNode(BiTree *s);
int BSTDelete(BiTree *T,DataType x);
void InOrderTraverse(BiTree T);
BiTree BSTSearch(BiTree T,DataType x);
int BSTInsert(BiTree *T,DataType x);
void main()
{
    BiTree T=NULL,p;
    DataType table[]={55,43,66,88,18,80,33,21,72};
    int n=sizeof(table)/sizeof(table[0]);
    DataType x={80},s={18};
    int i;
    for(i=0;i<n;i++)
        BSTInsert(&T,table[i]);
    printf("关键字序列为：");
    for(i=0;i<n;i++)
        printf("%4d",table[i]);
    printf("\n");
    printf("中序遍历二叉排序树得到的序列为：\n");
    InOrderTraverse(T);
    p=BSTSearch(T,x);
    if(p!=NULL)
        printf("\n二叉排序树查找:元素关键字%d查找成功.\n",x);
    else
        printf("\n二叉排序树查找:没有找到元素%d.\n",x);
    BSTDelete(&T,s);
    printf("删除元素%d后，中序遍历二叉排序树得到的序列为：\n",s.key);
    InOrderTraverse(T);
    printf("\n");
}
void InOrderTraverse(BiTree T)
/*中序遍历二叉排序树的递归实现*/
{
    if(T)                               /*如果二叉排序树不为空*/
    {
        InOrderTraverse(T->lchild);     /*中序遍历左子树*/
        printf("%4d",T->data);          /*访问根结点*/
        InOrderTraverse(T->rchild);         /*中序遍历右子树*/
    }
}

• 测试结果