本篇文章将介绍二叉排序树的查找算法。

@[toc]

何为二叉排序树查找？

上篇文章我们学习了折半查找，虽然折半查找算法将查找效率提高了，但是折半查找要求序列有序，所以当表插入、删除操作频繁的时候，为了维护表的有序性，就需要移动大量的元素，此时用折半查找显然事倍功半了。

那么有没有一种办法能够让查找效率依然高，而且可以很容易地实现插入、删除呢？基于此，我们可以改用动态查找表，这种表结构是在查找过程中动态生成的。动态查找表根据用途不同，可以分为：

1. 二叉排序树
2. 平衡二叉树
3. 红黑树
4. B-树
5. B+树
6. 键树

本篇文章重点介绍二叉排序树。

二叉排序树又称为二叉搜索树、二叉查找树，其定义如下：

二叉排序树或是空树，或是满足如下性质的二叉树：

1. 若其左子树非空，则左子树上所有结点的值均小于根结点的值
2. 若其右子树非空，则右子树上所有结点的值均大于等于根结点的值
3. 其左右子树本身又是一棵二叉排序树

如下图为一棵二叉排序树：

对其进行中序遍历，其遍历序列为：3 12 24 37 45 53 61 78 90 100，

会发现，其中序遍历结果是一个递增有序的序列。

由此得出二叉排序树的性质：

中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

查找算法实现

我们先来分析一下二叉排序树的查找过程，比如下面的一棵二叉排序树：

若是待查找的元素值为105，该如何查找呢？

首先让其与根结点比较，105 < 122，此时说明待查找元素值在其左子树上；

然后让其与左子树的根结点比较，105 > 99，此时说明待查找元素值在当前根结点的右子树上；

再让其与右子树的根结点比较，105 < 110，此时说明待查找元素值在当前根结点的左子树上；

最后让其与左子树的根结点比较，105 = 105，查找成功。

若是排序树中没有需要查找的元素，比如我要查找的元素值为103，那么在与105进行比较后，发现待查找元素应该在元素值为105的结点的左子树上，而其左子树为空，此时说明查找失败。

掌握了二叉排序树的查找原理后，就可以具体实现该算法了，在这之前，先定义出二叉排序树的存储结构：

typedef struct{
   
   
    int key;
    //还可定义其它数据信息
}ElemType;

typedef struct BSTNode{
   
   
    ElemType data;    //数据域
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

结合刚才的查找过程分析，我们可以总结出如下内容：

• 若二叉排序树为空，则查找失败
• 若二叉排序树不为空，将给定值key与根结点的关键字T->data.key进行比较：
• 1. 若key = T->data.key，则查找成功
• 1. 若key < T->data.key，则进一步查找左子树
• 1. 若key > T->data.key，则进一步查找右子树

分析过后，算法实现极其简单，代码如下：

BSTree SearchBST(BSTree t,int key){
   
   
    if(t == NULL || key == t->data.key){
   
   
        return t;
    }else if(key < t->data.key){
   
   
        return SearchBST(t->lchild,key);    //在左子树上继续查找
    }else{
   
   
        return SearchBST(t->rchild,key);    //在右子树上继续查找        
    }
}

查找效率分析

如下图：

这是一棵二叉排序树，若待查找元素值为50，则只需比较一次；

若待查找元素值为30，则需比较两次；

若待查找元素值为40，则需比较三次；

由此发现，查找元素值的比较次数与其所在排序树中的层数有关，第n层的结点元素值就需要比较n次才能查找到。

而二叉排序树的查找效率还受树的形态影响，比如序列：45，24，53，12，37，93。

最好情况是如下分布：

根据二叉树性质，树的深度为：「log₂n」 + 1。

其算法的时间复杂度为：O(log₂n)。

但若是如下分布：

其查找效率就与顺序查找效率相同，时间复杂度为：O(n)。

这时候我们就面临着一个问题，该如何提高形态不均衡的二叉排序树的查找效率？

我们需要做的就是对那些不均衡分布的二叉排序树做"平衡化"处理，尽量让二叉树的形态均衡。

二叉排序树的插入操作

在学习如何对二叉排序树进行"平衡化"处理之前，我们得先来学习一下二叉排序树的一些其它操作，比如：插入、删除、生成。

先来看看如何插入，比如下图的一棵二叉排序树：

若要在该排序树中插入元素值40，前提是插入后仍然要保持二叉排序树的性质，该如何实现呢？

首先让其与根结点比较，40 < 45，所以该元素应该插入到根结点的左子树上；

然后让其与左子树的根结点比较，40 > 12，所以该元素应该插入到该根结点的右子树上；

再让其与右子树的根结点比较，40 > 37，所以该元素应该插入到该根结点的右子树上；

因为该根结点无右子树，所以元素值40直接插入到该位置即可。

所以，总结出插入算法的思想如下：

• 若二叉排序树为空，则插入结点作为根结点插入到空树中
• 否则，继续在其左、右子树上查找
  1. 若树中已有，则不再插入
  2. 若树中没有
     查找直到某个叶子结点的左子树或右子树为空为止，则插入
     结点应为该叶子结点的左孩子或右孩子

算法思想掌握后，算法实现就非常简单了，代码如下：

int SearchBST(BiTree T,int key,BiTree f,BiTree p){
   
   
    //如果 T 指针为空，说明查找失败，令 p 指针指向查找过程中最后一个叶子结点
    if (!T){
   
   
        p = f;
        return 0;
    }
    //如果相等，令 p 指针指向该关键字
    else if(key == T->data){
   
   
        p = T;
        return 1;
    }
    //如果 key 值比 T 根结点的值小，则查找其左子树；反之，查找其右子树
    else if(key < T->data){
   
   
        return SearchBST(T->lchild,key,T,p);
    }else{
   
   
        return SearchBST(T->rchild,key,T,p);
    }
}
//插入函数
int InsertBST(BiTree T,ElemType e){
   
   
    BiTree p = NULL;
    //如果查找不成功，需做插入操作
    if (!SearchBST(T, e,NULL,p)) {
   
   
        //初始化插入结点
        BiTree s = (BiTree) malloc(sizeof(BSTNode));
        s->data = e;
        s->lchild = s->rchild = NULL;
        //如果 p 为NULL，说明该二叉排序树为空树，此时插入的结点为整棵树的根结点
        if (!p) {
   
   
            T = s;
        }
        //如果 p 不为 NULL，则 p 指向的为查找失败的最后一个叶子结点，只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子
        else if(e < p->data){
   
   
            p->lchild = s;
        }else{
   
   
            p->rchild = s;
        }
        return 1;
    }
    //如果查找成功，插入失败
    return 0;
}

这个算法其实很简单，大家细细品味一下应该都能理解吧，不能理解的话也不要紧，我来大致地分析一下。

首先呢，在插入之前，我们得先在原二叉排序树上查找一下待插入的元素值是否存在，所以我们得改进一下查找算法。

改进后的查找算法需要传递四个参数，前两个不介绍，是原先就需要的参数，我们增加了两个参数：一个BiTree类型的变量f；一个BiTree类型的变量p。

这两个变量是来辅助查找的，首先我们要判断当前二叉排序树的根结点是否为空，若为空，则结束查找，变量p指向的是查找过程中的最后一个结点，现在让它指向变量f就行了，因为变量f指向的就是查找过程中的最后一个结点，到后面你就明白了。

若根结点不为空，则需要判断待插入元素值是否等于当前结点的元素值，若相等，则查找成功，查找就结束了。

若不相等，则分为两种情况：

1. 待插入元素值小于当前结点元素值，则应该继续在当前结点的左子树查找，递归调用自身。注意这里的参数传递，第一个参数当然是传递当前结点的左孩子了；第二个参数是待插入元素值；第三个参数应该是查找过程中的最后一个结点，因为当前结点不为空，我们需要去查找其左子树，所以这个查找过程中的最后一个结点应该就是当前结点，所以把t传入；第四个参数直接把p传入即可
2. 待插入元素值大于当前结点元素值，则应该继续在当前结点的右子树查找，递归调用自身

此时不断递归，直到查找结束，我们就要来实现插入算法了。

插入算法也分几种情况，通过查找算法，若待插入元素值已经存在，则不执行if语句块，直接返回插入失败即可。

若插入元素值不存在，则同样需要进行查找，查找算法一定会在某个叶子结点结束，此时的叶子结点即为查找过程中的最后一个结点。

然后初始化一个新结点，对其数据域、孩子域赋值，继续分类讨论，若变量p为空，则说明二叉排序树为空，新结点直接作为根结点。

若变量p不为空，则需要让待插入结点与查找过程中的最后一个结点，即：结点p的元素值比较，若小于结点p的元素值，则作为其左孩子；反之，作为其右孩子。

不理解的同学要全神贯注地思考一下，应该是不难的。

二叉排序树的生成操作

掌握了插入操作，生成操作就非常简单了，直接调用插入算法将序列插入即可。

二叉排序树的删除操作

若要从二叉排序树中删除一个结点，不能把以该结点为根的子树都删掉，而应该只删除该结点，并且还要保证删除结点后的二叉排序树仍然满足二叉排序树的性质。

而删除结点又分为几种情况，比如下面的一棵二叉排序树：

若我们要删除的结点是叶子结点，非常简单，直接删除该结点即可，并将其双亲对应的孩子域置为NULL即可。

若我们要删除的结点只有左子树或者只有右子树，这种情况也比较简单，直接用其左子树或者右子树替换它即可。

比如我们要删除元素值40，那么直接删除该结点，并让其左孩子替换它即可，如图：

若我们要删除的结点既有左子树又有右子树，这种情况比较麻烦，需要在中序遍历中找到待删除元素的前驱，让其前驱结点替换它，然后删除前驱结点即可。

比如我们要删除的元素值为50，则其前驱为40，我们就让结点40代替它，然后删除该结点即可，如图：

当然我们也可以用待删除结点的后继替换，然后删除后继结点即可。

算法实现如下：

//删除函数
int DeleteBST(BiTree *p)
{
   
   
    BiTree q, s;
    //结点p为叶子结点，直接删除即可
    if(!(*p)->lchild && !(*p)->rchild){
   
   
        *p = NULL;
    }
    //结点p左子树为空，用其右孩子代替自身
    else if(!(*p)->lchild){
   
    
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
     //结点p右子树为空，用其左孩子代替自身
    else if(!(*p)->rchild){
   
   
        q = *p;
        //这里不是指针 *p 指向左子树，而是将左子树存储的结点的地址赋值给指针变量 p
        *p = (*p)->lchild;
        free(q);
    }
    //结点p左右孩子均不为空
    else{
   
   
        q = *p;
        s = (*p)->lchild;
        //遍历，找到结点 p 的直接前驱
        while(s->rchild)
        {
   
   
            q = s;
            s = s->rchild;
        }
        //改变结点 p 的值
        (*p)->data = s->data;
        //判断结点 p 的左子树 s 是否有右子树，分为两种情况讨论
        if( q != *p ){
   
   
            q->rchild = s->lchild;//若有，则在删除直接前驱结点的同时，令前驱的左孩子结点改为 q 指向结点的孩子结点
        }else{
   
   
            q->lchild = s->lchild;//否则，直接将左子树上移即可
        }
        free(s);
    }
    return 1;
}

该算法有一定的难度，大家理解删除结点的思想即可，如果你感兴趣的话，可以自己钻研一下。