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 intleft *Treeright *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