8.3.1 二叉排序树（1）在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论二叉排序树

二叉排序树是一种重要的动态查找表

上一节介绍过，动态查找表的特点是4种操作

除了查询类的操作，还有插入和删除操作

也就是查找表本身是在变化的

是在查找过程中动态生成的

可以理解为初始的时候呢

查找表是一个空表，那么对于一个包含给定值key的记录

如果表中存在关键字是key的记录

则查找成功返回

否则，在查找表中插入关键字等于key的记录

当然，如果需要也可以从查找表中删除

因为查找表中有频繁的插入和删除

我们所建立的查找表

应该能适应在查找表中频繁的插入和删除

建立二叉排序树，就是为了满足这样的要求

先看二叉排序树的定义

或者是一棵空树；或者是具有下列性质的二叉树

（1）若它的左子树不空

则左子树上所有结点的值均小于根结点的值

（2）若它的右子树不空

则右子树上所有结点的值均大于根结点的值

它的左、右子树也分别是二叉排序树

注意下第3点，这是一个递归定义

必须三条都满足，才能说是一棵二叉排序树

通过示例看一下二叉排序树

示例中给出了两颗二叉排序树

一棵的关键字为整型，一棵的关键字为字符串

字符串是按字典序去比较字符串的大小

我们以关键字为整数的二叉排序树为例

整棵二叉排序树的根，存储关键字为45的记录

左子树中4个结点的关键字都比它小

右子树中5个结点的关键字都比它大

满足1，2两条定义。考察45的左子树

以12为根的这棵二叉树

结点12的左子树有一个结点

关键字比12小，右子树有两个结点

关键字比12大，12的左子树以3为根

3的左右子树为空，空树是二叉排序树

那么以3为根的子树是二叉排序树

12右子树的根为37，37右子树为空

左子树24比37小，那么37为根的子树是二叉排序树

12的左右子树都是二叉排序树

并且12这棵子树满足二叉排序树1,2条定义

那么12为根这棵子树是二叉排序树

同理可以说明45的右子树是二叉排序树

从而得知整棵树是一棵二叉排序树

下面结合这个例子，来讨论一下在二叉排序树中如何查找

二叉排序树的查找是从根开始

首先把给定值和根进行比较，有三种情况

如果给定值等于根的关键字，那么查找成功，返回

如果给定值小于根，根据二叉排序树的性质

应该到根的左子树中继续查找，如果给定值大于根

应该到根的右子树中继续查找

以查找给定值24为例，首先和45比较

小于，到左子树中继续查找

同样和左子树的根比较，和12比较

大于根，到12的右子树中查处

和37比较，小于37，到37的左子树中查找

24为根的，和给定值相等，那么查找成功，返回

通过例子，我们可以注意到，24查找成功

也就是等于关键字24所在的层数

其它结点的情况也是这样，这一点和判定树相同

基于这一点，可以计算这棵二叉排序树

查找成功的平均查找长度

假设等概率的话，比较1次成功的结点有1个

2次的有2个，3次的有3个

4次的有2个，24和61，5次的有1个

6次的有1个78，比较次数乘结点个数求和

再除10，可以求得查找成功的平均查找长度ASL成功是3.3

同样，可以考虑查找失败的平均查找长度

绿色方框中，表示的就是查找失败的情形

查找表中有10个结点10个关键字

那么查找失败的情形有11种

比如说最左边绿色方框中

是代表给定值小于最小关键字3失败的情形

37的右子树方框中

是代表关给定值大于37小于45失败的情形

就整数来说的话，就是查找38到44这些给定值时失败

其它方框中的情形类似，也是假设等概率

查找两次就失败的情形，有1种

查找3次失败的情形有4种

查找4次失败的情形有3种，5次失败的有1种

6次失败的有2种，加起来除11

得到查找失败的平均查找长度是43÷11，不到4次

看一下查找算法的实现

二叉排序树的存储结构采用二叉链表

查找函数SearchBST用一个递归来实现的

函数的返回值是一个BiTree指针

约定查找成功返回指向成功记录结点的指针

查找失败则返回空

函数有两个参数，一个是指向二叉排序树根的指针T

另外一个是要查找的给定值key

调用函数的目的是，在T所指的这棵二叉树中

查找是否有记录结点的关键字等于给定值key

如果T是空指针，说明要查找的是空树

那么查找失败，返回T，也就是返回NULL

或者是给定值和根结点的关键字相等

说明查找成功，也是返回指向根结点的指针T

不是这两种情况，需要继续查找

如果给定值小于根结点的关键字

我们递归SearchBST(T->lchild, key)

到T的左子树T->lchild中继续进行查，递归返回后

把递归的结果返回

如果不小于，递归到右子树中继续查找

SearchBST从形式上来看，包含两个递归

不过两个递归在if-else语句中

只会产生一个递归调用，本质上是一个单递归

单递归的函数，很容易转化为循环实现

请同学们课后用循环的方式实现这个算法

二叉排序树作为一种动态的查找表

应该方便于插入和删除

二叉排序树采用的是二叉链表的存储结构

链式存储结构在插入删除上面比较方便

先看一下，二叉排序树的插入

在二叉排序树中新插入的结点一定是一个新添加的叶子

并且是查找不成功的时候

查找路径上访问的最后一个结点的左孩子或右孩子

看图示，如果给定值是20，查找20的路径

先和45比，小于45，和12比，大于12

和37比，小于37，最后和24比，小于24

到24的左子树中继续查找，发现左子树为空

知道查找失败，24是查找失败路径上访问的最后一个结点

如果插入20，可以把20添加作为24的左孩子

插入后仍然是一棵二叉排序树

同理，给定值是95的话，查找失败

它应该添加作为90的右孩子

在二叉链表中添加一个叶子结点是非常方便的

只需要把它双亲查找路径上访问的最后一个结点

的左指针或右指针指向新添加的叶子结点就可以了

在具体实践上，有一个细节要关注一下

需要修改一下刚才介绍查找的过程

前面查找过程中，查找成功的时候

返回指向成功记录结点的指针

查找不成功的时候，返回的是空指针

这里修改一下查找过程，查找不成功的时候

为了插入新结点时方便，返回一个指针

让这个指针指向查找路径上最后一个访问结点

修改过的查找函数SearchBST

返回值是状态，查找成功

函数返回True，失败返回False

参数有4个，一个是指向二叉排序树根结点的指针T

一个是要查找的给定值key

另外一个也是指向链表结点的指针f

指针f的作用很重要

f始终指向这层递归时根结点T的双亲

初始递归调用的时候，T指向整棵树的根

此时的根没有双亲，所以初始时f是空指针

同学应该注意到，T为空时我们知道查找失败

而f始终指向T的双亲，那么失败的时候

f指向的就是查找路径上最后访问的结点

最后是一个是引用的指针p，当查找成功时

p被指向成功记录结点，如果查找失败

p指向查找路径上访问的最后一个结点

p是引用，可以把指针带回调用函数

看一下函数的指令

如果要查找的树T是空树，查找失败

p赋值f，p指向查找失败路径上最后一个结点

然后return false，查找失败返回

同学们注意，P可能带回一个空指针

原因就是初始的时候，二叉排序树本来就是一棵空树

立刻就失败了，此时T的双亲f是空指针

不是空树，和根结点比较，相等返回

否则，如果给定值小于根结点的关键字

递归调用，到T的左子树中继续查找

注意下传递的参数，T->lchild是指向左子树根结点的指针

给定值key原样传递

T传给下一层递归的形参f,对T->lchild来说

T是它的双亲，引用 p原样传递

递归返回后，把递归的返回值reTurn

如果给定值大于根结点的关键字

递归，到右子树中去查找

下面看一下插入的函数

返回值是函数执行的状态

有两个参数，一个是指向二叉排序树根的指针T

这是要插入的对象，T被声明为一个引用

主要是是初始空树的时候

插入的记录将成为二叉排序树的根

另外一个是要插入的记录e

首先，调用刚才的查找函数

在二叉排序树中查找e.key，如果查找成功

就不需要插入，插入函数执行失败

直接到最后的else处，返回false

如果查找是失败的

实参p带回的是查找路径上最后一结点的指针

首先，申请链表结点，用s指向它

把记录e赋值给data，左右指针置空

为插入做准备

如果p为空，此时的二叉排序树是空树

T=s，新插入的结点成为二叉排序树的根

二叉排序树非空，用e.key和p所指结点的关键字比较

根据小或大，用p的左指针或右指针指向s

随后返回True，表示记录插入是成功了

下面从空树开始，了解一下二叉排序树通过插入记录

逐渐形成的过程

初始时是如图1所示的空树，第1个插入的是45

插入以后，包含45的结点作为二叉排序树的根结点

随后24插入，作为45的左孩子

53插入作为45的右孩子

第3个记录也是45，查找成功，这个45是不插入的

下一12插入作为24的左孩子，24不插入

最后90插入作为53的右孩子，最后结果如图6所示

这里有两个问题，要稍微注意一下

一是二叉排序树的形态和插入的次序有关

我们计算过二叉排序树的ASL

知道形态不同查找效率是不一样的

二是，如果对二叉排序树进行中序遍历

其访问序列是关键字的有序序列

可以说，一个无序的插入序列

通过这样一个构造二叉排序树的过程

变成了一个有序序列，构造的过程，可以看做排序的过程

好，同学们

这节课就到这儿，下次课再见