小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

数据结构与算法：二叉排序树_二叉排序树的求解结果怎么算

作者：小蓝xlanll | 2024-04-13 22:06:56

踩

二叉排序树的求解结果怎么算

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

在这里插入图片描述

也就是说，若我们现在需要对集合{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的左子树（见⑨）。

在这里插入图片描述

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

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

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

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

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

二叉排序树查找操作

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

/* 二叉树的二叉链表结点结构定义 /

/ 结点结构 /

typedef  struct BiTNode

{

/ 结点数据 /

int data;

/ 左右孩子指针 /

struct BiTNode lchild, rchild;

} BiTNode, BiTree;”

1
2
3
4
5
6
7
8
9

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

/* 递归查找二叉排序树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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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，如下图所示。

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

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;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

在这里插入图片描述

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

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]);

}

1
2
3
4
5
6
7

二叉排序树删除操作

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

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

我们仔细观察一下，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，如下图所示。

在这里插入图片描述

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

叶子结点；
仅有左或右子树的结点；
左右子树都有的结点，我们来看代码，下面这个算法是递归方式对二叉排序树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);

}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这段代码和前面的二叉排序树查找几乎完全相同，唯一的区别就在于第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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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

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

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

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

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

总结

总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为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次比较才可以得到结果，二者差异很大。

在这里插入图片描述

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为，那么查找的时间复杂也就为O(logn)，近似于折半查找，事实上，上图的左图也不够平衡，明显的左重右轻。

不平衡的最坏情况就是像上图右图的斜树，查找时间复杂度为O(n)，这等同于顺序查找。

因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。这样我们就引申出另一个问题，如何让二叉排序树平衡的问题。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/418773