当前课程知识点：数据结构 > 第7章 查找 > 7.3 二叉排序树 > 讲解（上）
这一节，我们来学习二叉排序树，Binary Sort Tree，简称BST
我们先来看看二叉排序树的定义
对于任何一棵非空的二叉排序树，具有以下的性质
所有结点的关键字不同
在任何结点当中，不能出现相同的关键字
根的左子树上全部结点，都要小于该结点
注意，是左子树上的全部结点
而不仅仅是左子树的根，也就是根的左孩子
左子树上所有结点，都要小于根
与之对称的，根的右子树上
所有结点都要大于根
同时
左右子树也都是BST，也都是二叉排序树
从这个定义
我们可以看出，二叉排序树
它实际上也用到了递归
所以，我们后面在介绍查找算法的时候，也用到了递归的形式
这里给出了5棵二叉排序树
我们先来看第一棵
根的右子树上的2、3，都是大于1的，2的右子树
3是大于2的
第二棵，1的右子树上的3和2，都是大于1的，3的左子树
2小于3，剩下的也都是类似的
它们都是二叉排序树
我们再来看右边的这个图
事实上
我们前面讲的折半查找，所对应的判定树
它也是一棵二叉排序树
比如，整个序列当中，最中间的那个结点
56
它作为树的根
它的右子树上的5个结点，都是大于56的
很明显
因为56的右子树上这5个结点，在序列当中，都是位于56的右边的
我们已经知道，能采用折半查找
整个序列是有序的
56右边的东西，一定是大于56的
同样，80的左子树
64、75都是小于80
80的右子树
88和92都是大于80
56的左子树也都是类似的
每一个结点
左子树全都小于该结点
右子树全都大于该结点
这就是二叉排序树
现在来看
二叉排序树的第一类操作，查找
我们在二叉排序树当中，查找给定的关键字
这个过程，跟前面折半查找
对应的判定树的查找过程，是类似的
我们可以采用递归的形式来实现
因为二叉排序树
它的定义本身，就是递归的
这个结构体
是二叉排序树，对应的C语言定义
从代码层面来看
它跟前面讲的以链式存储的二叉树，是类似的
也就是二叉链表
每个结点包含自身信息和左右孩子
我们在
以二叉链表存储的二叉排序树
T当中，找关键字等于k的这个结点
如果找到了
把这个结点的指针，放到p里面
第三个参数f又是什么意思呢
我们后面，会讲到二叉排序树的插入
事实上
如果一个结点，在二叉排序树当中不存在
我们要把这个结点，插入到二叉排序树当中
那应该插入到最后一次比较的那个结点
它的左孩子或右孩子上
为了记录下最后一次比较的这个结点
我们必须用一个变量来存放它
待会，我们也能看到，实际上f这个参数
它始终是T这个参数的父结点
我们现在来写一下，这个算法
它的4个参数
第一个参数k，以没什么好说的
这个就是我们要找的关键字
比如13
85
第二个参数T，是我们当前
要找的这棵树它的根
因为，我们后面会用到递归
f作为第三个参数
它是T的父结点
第四个参数p
它就是指向要找的那个结点
当然，如果k存在
p是指向k那个结点的指针
如果k不存在
这时候
p实际上，它是指向最后一次
比较的那个元素
最后比较的结点
我们要把这4个参数搞清楚
这里之所以引入第三个参数f
完全是为了后面方便编写插入算法
现在，我们来看完整的算法过程
如果当前树的根T是等于空的
这时候，直接将f赋值给p
待会我们会看到
这个赋值语句，它的意义
然后，return一个0
很明显，这个函数的返回值
是
k不存在的时候
我们返回0
如果k存在，我们返回1
所以，用返回值来代表查找是否成功
else if
如果T非空
而且，T指向的结点
它的关键字等于给定的关键字
那么，这时候，直接将T赋给p
当前树的根赋给p，那p就指向当前查找的那棵树的根，说明找到了关键字k
这时候，return一个1
第二个else
如果关键字小于T的根，那说明
k如果存在，一定位于T的左子树上
所以，我们开始递归
k没有变化
第二个参数有变化
我们当前
查找的树是T，现在，递归查找它的左子树
别忘了，第三个参数f，始终是T的父结点
现在，我们准备找T的左子树了
你应该
把左子树的父结点，也就是当前的根，作为第三个参数
p是没有变化的
else，那是对称的情况
如果k是大于树的根的
如果存在，它一定位于右子树上
所以，我们递归地查找右子树
第二个参数，变成了T的右子树
其他参数没有变化
现在，我们来分析一下这个查找的过程
假设，k是等于13的
13在这棵树当中是存在的
我们来看一下，这几个参数的变化
我们记录下
后三个参数T、f、p
第一次的时候，这三个参数是多少呢
换句话说
你怎样去调用这里的函数searchBST呢
我们最开始的时候
整棵树的根，肯定是56
我就这样写了
表示T这个参数指向56，f和p呢
它们的初值都是空
第一次调用的时候，这两个实参
都传入空
现在，我们执行这里的(第7行)
注意，k是等于13的
13是小于T指向的那个56
所以，我们应该执行第7行，这时候准备递归了，k没有变化
我们不写了，T(56)的左子树是19
当前的T是56
别忘了，这里的第三个参数，是要传给f的
那么，f变成了19的父结点56
p呢
没有变化，还是空
好
现在，再进入第1行，T是19
13依然是小于19的
依然要执行
第7行
这时候，19的左子树传给T
也就是5
然后
T当前是19(传给f)
p依然是空
然后，再进入第1行
T是指向5的
然后，应该执行第9行
因为这时候，k是大于T指向的那个5
那么
执行第9行，将5的右子树13传给T
T当前是5(传给f)，p依然是空
最后一次递归，T是指向13的
这时候，应该去执行第5行
因为这时候，关键字13等于T指向的13，执行第5行
那么，将p修改成T，也就是，p指向13
这时候，p是指向13的
然后直接return
它上层的递归，也会执行完
因为，无论是执行第5行也好
执行第7行也好，执行第9行也好
这些行执行完了，实际上，整个函数也执行完了
会导致它们上层的递归也会结束
大家看到，当找的关键字，在树当中存在的时候
这个p，它是指向那个关键字的
那如果
关键字不存在呢
这时候，p的值又是多少呢
我们接下来，继续分析
现在，我们来找一个不存在的
比如，k等于85
我们依然记录下这三个参数
T、f、p
T的初值
毫无疑问，是56
这两个都是空
我就这样简写了
第一行进来，T是56
那么
85是大于56的，我们应该执行第9行，56的右子树赋给T
右子树是80，当前T是56
f始终是指向T的父结点
p是空
现在，继续进来
T指向80，那么
85依然大于80，还是执行第9行，80的右子树88，赋值给T
80是T的父结点，p为空
再次进入第1行，T是88
85是小于T指向的88的，应该执行第7行，T的左子树赋给T，T的左子树(88的左子树)是空
这时候，T变成空了
它的父结点，也就是88
我们再进入第1行，T为空
这时候，应该执行第3行
将f赋给p
f这时候是88
也就是我们比较的最后一个结点
我们将它赋值给p
p就指向88
所以大家看到，当我们要找的关键字，在BST当中不存在的时候
这个p
它是指向我们最后一次比较的那个结点
将来我们做插入
我们把85插到BST当中
它应该插入到88的左子树的位置
为此，我们需要知道88这个结点在哪
这时候，就由p来指向
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
