一、概念、性质
二叉搜索树（Binary Search Tree），简写BST，又称为二叉查找树
它满足：
- 空树是一颗二叉搜索树
- 对于任意结点 node ，它的左右孩子如果不为空 ，满足：
-
- 左子树上所有结点的值都小于node的值
-
- 右子树上所有结点的值都大于node的值
- 不存在数值重复的结点
如下图，图（1）是二叉搜索树，图（2）、图（3）不是二叉搜索树
图（2）中不满足 70 < 50
图（3）中不满足 30 < 10
之所以叫做二叉搜索树，是因为在BST中搜索一个值是很简单的
例如图（1）中要查找40
从根结点出发，40比50小，来到根结点的左孩子30，40比30大，来到30的右孩子40，40等于40，这样就找到了
例如图（1）中要查找10
从根结点出发，10比50小，来到根节点的左孩子30，10比30小，来到30的左孩子20，10比20小，来到20的左孩子null，所以没有10这个结点
对图（1）进行中序遍历，得到 20 30 40 50 60
发现是一个有序的序列
所以对二叉搜索树进行中序遍历，会得到一个有序的序列
二、二叉搜索树的实现
1. 结构
定义一个二叉搜索树很简单，就和定义一个二叉树的结构一样，需要包含 数据、左右孩子指针
// 定义结点结构
type TSNode struct {
data int
left *TSNode
right *TSNode
}
2. 查找
查找一个值target，从根结点开始，递归进行比较。
如果等于根结点，找到返回
如果小于根结点则走到左子树，在左子树中找
如果大于根结点则走到右子树，在右子树中找
// 判断结点是否存在
func (t *TSNode) Search(data int) *TSNode {
if t == nil {
return nil
}
if t.data == data { //找到了 返回结点
return t
}
if data < t.data { //要找的数据小于根结点 向左找
return t.left.Search(data)
} else { //要找的数据大于根结点 向右找
return t.right.Search(data)
}
}
3. 插入
向二叉搜索树插入数据data ，分为两种情况
- 树为空，定义一个新结点储存data，直接 根结点 = 新结点
- 树不为空，和结点进行比较（和查找数据步骤一样），直到结点为空，将新结点插入
如向图（1）中插入数据35
- 首先和根结点50进行比较，小于50，走到左孩子30
- 和30进行比较，大于30，走到30的右孩子40
- 和40进行比较，小于40，走到40的左孩子 null，将35 插入40 左孩子
最终得到
// 插入数据
func (t *TSNode) Insert(data int) {
newNode := &TSNode{
data,
nil,
nil,
}
//如果根结点为空 直接插入
if t == nil {
t = newNode
return
}
//根结点不为空 判断
if data < t.data { //小于根结点数据 向左找
if t.left == nil { //左孩子为空 直接赋值
t.left = newNode
} else {
t.left.Insert(data) //左孩子不为空 遍历左孩子 找
}
} else {
if t.right == nil {
t.right = newNode
} else {
t.right.Insert(data)
}
}
}
4. 删除
删除二叉搜索树的数据分为三种情况
- 要删除的结点没有左右孩子
- 要删除的结点没有左孩子或右孩子
- 要删除的结点既有左孩子也有右孩子
有这样一颗二叉搜索树，下面第一二种拿这个举例子
- 删除的结点没有左右孩子
直接删除结点就可以
例如删除上图中的25，直接删除25得到
- 要删除的结点只有左孩子或只有右孩子
如果只有右孩子，比如删除图中的60
直接让60父结点与60的右孩子连接，将60删除就可以
得到：
3. 要删除的结点既有左孩子也有右孩子
这里要引入中序后继和中序前驱的概念，我把这两个概念放在最后了
比如要删除30，找到30的中序后继结点或者中序前驱结点，哪个都可以，就拿中序后继结点举例子
30的中序后继结点是35，将35的值赋给30这个节点，再对30的右子树进行删除中序后继结点的操作就可以了
使用中序前驱结点一样，将中序前驱节点的值赋给要删除的节点的值，再对要删除的节点的左子树进行删除中序前驱节点的操作
实现删除操作的代码：
首先要找到要删除的结点， if、else if、else 就是在找要删除的结点
// 删除结点
func (t *TSNode) Delete(data int) *TSNode {
//查找结点 -- 查找到要找的结点，分情况对结点进行删除操作
if t == nil {
return nil
}
if data < t.data { //要删除的数据小于根结点
//递归查找左子树
t.left = t.left.Delete(data)
} else if data > t.data {
//递归查找右子树
t.right = t.right.Delete(data)
} else { //查找到了要删除的数据
//此时t是要删除的结点 分情况
if t.left == nil && t.right == nil { //如果左右孩子都是空 直接删除 返回空
return nil
}
//只有一个结点
if t.left == nil { //只有一个右结点 父结点和左孩子结点相连
return t.right
}
if t.right == nil { //只有一个左结点 父结点和右孩子结点相连
return t.left
}
//左右孩子结点都存在
//找到 中序后继结点 -- 右孩子一直向左找
minNode := t.right.MinNode()
//用这个结点替换要删除的结点
t.data = minNode.data
//删除中序后继结点--因为是查找的右孩子的中序后继，所以调整右子树
t.right = t.right.Delete(minNode.data)
}
return t
}
// 查找中序后继结点
func (t *TSNode) MinNode() *TSNode {
if t.left == nil {
return t
}
return t.left.MinNode()
}
5. 中序遍历
使用递归遍历，和二叉树的中序遍历一样
先递归左子树，再打印节点的值，最后递归右子树
// 中序遍历
func (t *TSNode) InOrder() {
if t == nil {
return
}
t.left.InOrder()
fmt.Printf("%d ", t.data)
t.right.InOrder()
}
中序前驱/后继结点
中序后继结点：在中序遍历中紧跟在某个节点后面的节点
怎么找中序后继结点呢？
先走到一个结点Node 的右孩子，再从右孩子不断向左走，直到某个节点的左孩子为空，那这个结点就是Node 的中序后继结点
比如要找30的中序后继结点，30走到40，40向左走到35，35的左孩子为空，那35就是30的后继结点中序前驱结点：在中序遍历中在某个结点前一个的结点
怎么找中序前驱结点呢？
先走到一个结点Node 的左孩子，再从左孩子不断向右走，直到某个节点的右孩子为空，那这个结点就是Node 的中序前驱结点
比如要找30的中序前驱结点，30走到左孩子20，20向右走到25，25的右孩子为空，所以25就是30的中序前驱结点