数据结构与算法-二叉排序树

作者: Joker_King | 来源:发表于2020-05-14 14:15 被阅读0次

数据结构与算法 - 查找
思维导图之数据结构+算法
数据结构与算法 - 树形结构
查找
最新完整数据结构与算法
数据结构与算法
算法与数据结构（1），List
数据结构与算法-目录
算法与数据结构（3），并发结构
算法与数据结构（2），Map

假设我们的数据集开始只有一个数{62}，然后现在需要将88插入数据集，于是数据集成了{62,88}，还保持着从小到大有序。再查找有没有58，没有则插入，可此时要想在线性表的顺序存储中有序，就得移动62和88的位置，如图8-6-2左图，可不可以不移动呢？嗯，当然是可以，那就是二叉树结构。当我们用二叉树的方式时，首先我们将第一个数62定为根结点，88因为比62大，因此让它做62的右子树，58因比62小，所以成为它的左子树。此时58的插入并没有影响到62与88的关系，如下图右图所示。

image-20200514112750982

也就是说，若我们现在需要对集合{62,88,58,47,35,73,51,99,37,93}做查找，在我们打算创建此集合时就考虑用二叉树结构，而且是排好序的二叉树来创建。如下图所示，62、88、58创建好后，下一个数47因比58小，是它的左子树（见③），35是47的左子树（见④），73比62大，但却比88小，是88的左子树（见⑤），51比62小、比58小、比47大，是47的右子树（见⑥），99比62、88都大，是88的右子树（见⑦），37比62、58、47都小，但却比35大，是35的右子树（见⑧），93则因比62、88大是99的左子树（见⑨）。

image-20200514115148146

这样我们就得到了一棵二叉树，并且当我们对它进行中序遍历时，就可以得到一个有序的序列{35,37,47,51,58,62,73,88,93,99}，所以我们通常称它为二叉排序树。

二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。

从二叉排序树的定义也可以知道，它前提是二叉树，然后它采用了递归的定义方法，再者，它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。

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

二叉排序树查找操作

首先我们提供一个二叉树的结构。

/* 二叉树的二叉链表结点结构定义 */
/* 结点结构 */
typedef  struct BiTNode                 
{
    /* 结点数据 */
    int data;                           
    /* 左右孩子指针 */
    struct BiTNode *lchild, *rchild;    
} BiTNode, *BiTree;”

然后我们来看看二叉排序树的查找是如何实现的。

/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并
   返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点
   并返回FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
    /* 查找不成功 */
    if (!T)                                        
    {
        *p = f;
        return FALSE;
    }
    /* 查找成功 */
    else if (key == T->data)                       
    {
       *p = T;
       return TRUE;
    }
    else if (key < T->data)
        /* 在左子树继续查找 */
        return SearchBST(T->lchild, key, T, p);    
    else
        /* 在右子树继续查找 */
        return SearchBST(T->rchild, key, T, p);    
}

1．SearchBST函数是一个可递归运行的函数，函数调用时的语句为SearchBST(T,93,NULL,p)，参数T是一个二叉链表，其中数据如上图所示，key代表要查找的关键字，目前我们打算查找93，二叉树f指向T的双亲，当T指向根结点时，f的初值就为NULL，它在递归时有用，最后的参数p是为了查找成功后可以得到查找到的结点位置。

2．第3～7行，是用来判断当前二叉树是否到叶子结点，显然图8-6-3告诉我们当前T指向根结点62的位置，T不为空，第5～6行不执行。

3．第8～12行是查找到相匹配的关键字时执行语句，显然93≠62，第10～11行不执行。

4．第13～14行是当要查找关键字小于当前结点值时执行语句，由于93>62，第14行不执行。

5．第15～16行是当要查找关键字大于当前结点值时执行语句，由于93>62，所以递归调用SearchBST(T->rchild,key,T,p)。此时T指向了62的右孩子88，如下图所示。

image-20200514115604580

6．此时第二层SearchBST，因93比88大，所以执行第16行，再次递归调用SearchBST(T->rchild,key,T,p)。此时T指向了88的右孩子99，如下图所示。

image-20200514115637094

7．第三层的SearchBST，因93比99小，所以执行第14行，递归调用SearchBST(T->lchild,key,T,p)。此时T指向了99的左孩子93，如下图所示。

image-20200514115706071

8．第四层SearchBST，因key等于T->data，所以执行第10～11行，此时指针p指向93所在的结点，并返回True到第三层、第二层、第一层，最终函数返回True。

二叉排序树插入操作

有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已，来看代码。

/* 当二叉排序树T中不存在关键字等于key的数据元素时， */
/* 插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key)
{
    BiTree p, s;
    /* 查找不成功 */
    if (!SearchBST(*T, key, NULL, &p))    
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if (!p)
            /* 插入s为新的根结点 */
            *T = s;                       
        else if (key < p->data)
            /* 插入s为左孩子 */
            p->lchild = s;                
        else
            /* 插入s为右孩子 */
            p->rchild = s;                
        return TRUE;
    }
    else
        /* 树中已有关键字相同的结点，不再插入 */
        return FALSE;                     
}

这段代码非常简单。如果你调用函数是“In-sertBST(&T,93);”，那么结果就是FALSE，如果是“InsertBST(&T,95);”，那么一定就是在93的结点增加一个右孩子95，并且返回True。如下图所示。

image-20200514134540119

有了二叉排序树的插入代码，我们要实现二叉排序树的构建就非常容易了。下面的代码就可以创建一棵二叉树。

int i;
int a[10] = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 };
BiTree T = NULL;
for (i = 0; i < 10; i++)
{
    InsertBST(&T, a[i]);
}

二叉排序树删除操作

俗话说“请神容易送神难”，我们已经介绍了二叉排序树的查找与插入算法，但是对于二叉排序树的删除，就不是那么容易，我们不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况。

如果需要查找并删除如37、51、73、93这些在二叉排序树中是叶子的结点，那是很容易的，毕竟删除它们对整棵树来说，其他结点的结构并未受到影响，如下图所示。

image-20200514134813427

对于要删除的结点只有左子树或只有右子树的情况，相对也比较好解决。那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。比如下图，就是先删除35和99结点，再删除58结点的变化图，最终，整个结构还是一个二叉排序树。

image-20200514135018198

但是对于要删除的结点既有左子树又有右子树的情况怎么办呢？比如下图中的47结点若要删除了，它的两儿子以及子孙们怎么办呢？

image-20200514135049281

我们仔细观察一下，47的两个子树中能否找出一个结点可以代替47呢？果然有，37或者48都可以代替47，此时在删除47后，整个二叉排序树并没有发生什么本质的改变。

为什么是37和48？对的，它们正好是二叉排序树中比它小或比它大的最接近47的两个数。也就是说，如果我们对这棵二叉排序树进行中序遍历，得到的序列{29,35,36,37,47,48,49,50,51,56,58,62,73,88,93,99}，它们正好是47的前驱和后继。

因此，比较好的办法就是，找到需要删除的结点p的直接前驱（或直接后继）s，用s来替换结点p，然后再删除此结点s，如下图所示。

image-20200514135732698

根据我们对删除结点三种情况的分析：

叶子结点；
仅有左或右子树的结点；
左右子树都有的结点，我们来看代码，下面这个算法是递归方式对二叉排序树T查找key，查找到时删除。

/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE */
Status DeleteBST(BiTree *T, int key)
{
    /* 不存在关键字等于key的数据元素 */
    if (!*T)                      
        return FALSE;
    else
    {
        /* 找到关键字等于key的数据元素 */
        if (key == (*T)->data)    
            return Delete(T);
        else if (key < (*T)->data)
            return DeleteBST(&(*T)->lchild, key);
        else
            return DeleteBST(&(*T)->rchild, key);
    }
}

这段代码和前面的二叉排序树查找几乎完全相同，唯一的区别就在于第8行，此时执行的是Delete方法，对当前结点进行删除操作。我们来看Delete的代码。

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
Status Delete(BiTree *p)
{
    BiTree q, s;
    /* 右子树空则只需重接它的左子树 */
    if ((*p)->rchild == NULL)         
    {
        q = *p; 
        *p = (*p)->lchild; 
        free(q);
    }
    /* 只需重接它的右子树 */
    else if ((*p)->lchild == NULL)    
    {
        q = *p; 
        *p = (*p)->rchild; 
        free(q);
    }
    /* 左右子树均不空 */
    else                              
    {
        q = *p; s = (*p)->lchild;
        /* 转左，然后向右到尽头(找待删结点的前驱) */
        while (s->rchild)             
        {
            q = s; s = s->rchild;
        }
        /* s指向被删结点的直接前驱 */
        (*p)->data = s->data;         
        if (q != *p)
            /* 重接q的右子树 */
            q->rchild = s->lchild;    
        else
            /* 重接q的左子树 */
            q->lchild = s->lchild;    
        free(s);
    }
    return TRUE;
}

1．程序开始执行，代码第4～7行目的是为了删除没有右子树只有左子树的结点。此时只需将此结点的左孩子替换它自己，然后释放此结点内存，就等于删除了。

2．代码第8～11行是同样的道理处理只有右子树没有左子树的结点删除问题。

3．第12～25行处理复杂的左右子树均存在的问题。

4．第14行，将要删除的结点p赋值给临时的变量q，再将p的左孩子p->lchild赋值给临时的变量s。此时q指向47结点，s指向35结点，如下图所示。

image-20200514140624139

5．第15～18行，循环找到左子树的右结点，直到右侧尽头。就当前例子来说就是让q指向35，而s指向了37这个再没有右子树的结点，如下图所示。

image-20200514140722889

7．第20～23行，如果p和q指向不同，则将s->lchild赋值给q->rchild，否则就是将s->lchild赋值给q->lchild。显然这个例子p不等于q，将s->lchild指向的36赋值给q->rchild，也就是让q->rchild指向36结点，如下图所示。

image-20200514140837341

8．第24行，free(s)，就非常好理解了，将37结点删除，如下图所示。

image-20200514140947255

从这段代码也可以看出，我们其实是在找删除结点的前驱结点替换的方法，对于用后继结点来替换，方法上是一样的。

总结

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

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