(5)--第七章第三节二叉排序树-二叉排序树的创建.pdf

01【二叉排序树的创建】

目录02【二叉排序树的创建算法思想】

CONTENTS03【二叉排序树的创建算法实现】

04【二叉排序树的创建过程】

01二叉排序树的定义

01定义

二叉排序树是一种动态树表。其特点是，树的结

构通常不是一次生成的，而是在查找过程中，当树中

不存在关键字等于给定值的结点的时候再迚行插入。

新插入结点一定是一个新添加的叶子结点，并且是查

找不成功时查找路径上访问的最后一个结点的左孩子

或右孩子结点。

02二叉排序树创建的算

法思想

二、二叉排序树创建的算法思想:

插入结点

在二叉排序树上查

找元素

算法结束

二叉排序树创建的算法思想:

t

p

sx

fp

p

sx

03二叉排序树的查找算

法实现

•例：给定关键字序列

{53，45，12，24，90，45，80}，

建立二叉排序树。

–提示：从空二叉树开始，依次插入关键字。

53

4590

1280

24

中序遍历该二叉排序树得到：

122445538090

结论：

一个无序序列可以通过构造一棵二叉排序树而变成一

个有序序列，构造树的过程即为对无序序列迚行排序的过程。

从刚才的插入过程还可以看到，每次插入的新结点都

是二叉排序树上新的叶子结点，则在迚行插入操作时候，不

必移动其他结点，仅需改动某个结点的指针，由空变为非空

即可。这就相当于在一个有序序列上插入一个记录而不需要

移动其他记录。

这表明，二叉排序树既拥有类似于折半查找的特性，

又采用了链表作为存储结构，因此是动态查找表的一种适宜

表示。

谢谢