4.2 二叉搜索树
二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树结构，它在上一节的基础上做了新的规则限制。
它的特性使得在进行查找、插入、删除等操作时效率非常高。二叉搜索树广泛应用于搜索、排序和数据存储等场景。
本节我们将介绍二叉搜索树的基本概念、其特有的规则以及在 Go 语言中的实现。
本节代码存放目录为 lesson7
概念及原理
二叉搜索树（BST） 是一种有序的二叉树，其每个节点都有以下特性：
-
左子树节点的值 小于 父节点的值。
-
右子树节点的值 大于 父节点的值。
-
对于每个节点，左子树和右子树 本身也都是二叉搜索树。
这样的性质使得我们可以在二叉搜索树上快速进行查找、插入、删除操作。
二叉搜索树的结构示意图如下所示：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
-
节点 8 是根节点，左子树上的所有节点都小于
8，右子树上的所有节点都大于8。 -
节点 3 是
8的左子节点，节点 10 是8的右子节点。 -
节点 1、6、14、4、7、13 也是遵循二叉搜索树的性质，左子节点小于父节点，右子节点大于父节点。
总的来说，对于二叉搜索树，我们只需要记住：左子小于父，右子大于父。
二叉搜索树具有以下几个重要特性：
-
查找操作：查找某个节点的过程类似于二分查找。我们根据值的大小决定是否向左子树或右子树递归查找，这样可以快速缩小查找范围。
-
插入操作：插入一个新值时，我们根据该值与当前节点的比较结果，递归找到合适的空位插入，确保二叉搜索树的有序性。
-
删除操作：删除节点时有三种情况：
-
节点没有子节点：直接删除该节点。
-
节点有一个子节点：删除节点后，直接将其子节点连接到父节点。
-
节点有两个子节点：找到该节点的中序后继节点，替换到被删除节点的位置，再递归删除后继节点。
-
与普通二叉树一样，二叉搜索树也可以使用前序遍历、中序遍历、后序遍历和层序遍历。特别是中序遍历，它会按照升序输出节点的值。
以上面的树为例，使用 中序遍历 的顺序就是从小到大依次输出节点值：
1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14
如何查找中序后继节点？
我么可以简单理解为：采用中序遍历后，第一个比当前节点大的节点。
比如在上面的中序遍历后，我们得到：
1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14
那么1的后继就是3，因为3是第一个比1大的；同理6的后继就是7，7的后继就是8。
删除操作示例
我们同样以上文的例子示范：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
首先我们删除13，由于13是没有任何子节点的，所以我们直接将13节点删除即可。此时结构如下：
8
/ \
3 10
/ \ \
1 6 14
/ \
4 7
接下来我们删除10节点，由于10节点只有一个节点14，所以我们直接将14连接到父节点8即可。此时结构如下：
8
/ \
3 14
/ \
1 6
/ \
4 7
接下来我们删除6节点，由于6节点有两个子节点，所以我们需要找到6的中序后继节点，也就是7，之后我们将7替换到被删除的6节点。此时结构如下：
8
/ \
3 14
/ \
1 7
/ \
4 7
接下来我们需要删除原本的中序后继节点7。最终结构如下：
8
/ \
3 14
/ \
1 6
/
4
Go语言的实现
接下来我们使用 Go 语言实现二叉搜索树，包括插入、查找和删除等基本操作。
实现代码如下所示：
// Tree 定义树结构
type Tree struct {
data int
left *Tree
right *Tree
}
func (t *Tree) insert(data int) {
newTree := &Tree{
data: data,
}
if data < t.data {
if t.left == nil {
t.left = newTree
} else {
t.left.insert(data)
}
} else {
if t.right == nil {
t.right = newTree
} else {
t.right.insert(data)
}
}
}
func (t *Tree) search(data int) *Tree {
if t == nil {
return nil
}
if t.data == data {
return t
}
// 递归查找左子树
if data < t.data {
return t.left.search(data)
}
// 递归查找右子树
return t.right.search(data)
}
func (t *Tree) delete(data int) *Tree {
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 {
// 没有任何子节点
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.findMin()
// 用中序后继的值替换当前节点的值
t.data = minNode.data
// 删除中序后继节点
t.right = t.right.delete(minNode.data)
}
return t
}
// 查找最小节点（中序后继）
func (t *Tree) findMin() *Tree {
if t.left == nil {
return t
}
return t.left.findMin()
}
// 中序遍历
func (t *Tree) inOrder() {
if t == nil {
return
}
t.left.inOrder()
fmt.Printf("%d ", t.data)
t.right.inOrder()
}
func (t *Tree) printTree() {
if t == nil {
return
}
if t.left != nil {
fmt.Printf("left: %d, ", t.left.data)
}
if t.right != nil {
fmt.Printf("right-> %d\n", t.right.data)
}
if t.left == nil && t.right == nil {
return
}
t.left.printTree()
t.right.printTree()
}
func main() {
tree := &Tree{data: 8}
tree.insert(3)
tree.insert(10)
tree.insert(1)
tree.insert(6)
tree.insert(14)
tree.insert(4)
tree.insert(7)
tree.insert(13)
tree.printTree()
fmt.Println("\n中序遍历结果:")
tree.inOrder()
fmt.Println("\n\n查找节点 6")
node := tree.search(6)
if node != nil {
fmt.Printf("找到节点: %d\n", node.data)
} else {
fmt.Println("节点不存在")
}
fmt.Println("\n删除节点 13 后的中序遍历结果:")
tree = tree.delete(13)
tree.inOrder()
fmt.Println("\n删除节点 10 后的中序遍历结果:")
tree = tree.delete(10)
tree.inOrder()
fmt.Println("\n删除节点 6 后的中序遍历结果:")
tree = tree.delete(6)
tree.inOrder()
}
执行结果输出如下：
left: 3, right-> 10
left: 1, right-> 6
left: 4, right-> 7
right-> 14
left: 13,
中序遍历结果:
1 3 4 6 7 8 10 13 14
查找节点 6
找到节点: 6
删除节点 13 后的中序遍历结果:
1 3 4 6 7 8 10 14
删除节点 10 后的中序遍历结果:
1 3 4 6 7 8 14
删除节点 6 后的中序遍历结果:
1 3 4 7 8 14
在上面的代码中我们实现了基本的插入、查询、删除、遍历，可能代码看起来不是太明白，我们可以先将递归了解清楚，我们主要使用的也就是递归的概念。
通过递归进行各种操作，所以代码看起来会比较抽象，我们可以拿到代码demo，去加一下日志输出详细查看一下他的整个过程。
小结
二叉搜索树是二叉树的一种扩展形式，具有排序和快速查找的优势。通过本节的学习，我们了解了二叉搜索树的特性和操作实现。
下一节我们将继续深入学习AVL树，它们在保持二叉搜索树性能的同时，通过自平衡机制进一步优化了查找和插入的效率。
我的GitHub：https://github.com/swxctx
书籍地址：https://gs.golang.website/
书籍代码：https://github.com/YouCanGolang/GoStructedCode
