二叉搜索树概念
二叉排序树，又叫二叉查找树，是一种快速高效的排序方式。它可以是一棵空树（没有值）；或者是具有以下性质的二叉树：
1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 它的左右子树也分别为二叉排序树。
对于二叉树中的任意节点X，它的左子树中所有关键字的值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。这也意味着二叉搜索树中的所有节点都可以按照某种方式来排序。
图例
## Golang 中实现
创建结构体
1
2
3
4
5
|
type TreeNode struct {
elem int
left *TreeNode
right *TreeNode
}
|
创建一个空树或者清空树
注：
- 创建一棵空树: 不像其他一些数据结构中通过一个结构体来定义一棵空树，我们直接通过空指针来定义一棵空树，所以在 MakeEmpty 尾部我们直接返回了空指针来代表一棵空树。
- 清空一棵树：MakeEmpty 函数还可以清空一棵树，由于Go语言中并不需要我们手动管理内存空间，所以删除树节点并不需要释放空间，只需要将指向树节点的指针置为nil即可。
1
2
3
4
5
6
7
8
9
|
func MakeEmpty(tree *TreeNode) *TreeNode {
if tree != nil {
MakeEmpty(tree.left)
tree.left = nil
MakeEmpty(tree.right)
tree.right = nil
}
return nil
}
|
插入数据
注意：如果要插入的值已经在树中存在，我们什么也不做，树中不会保存两个相同的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func Insert(elem int, tree *TreeNode) *TreeNode {
if tree == nil {
tree = &TreeNode{}
tree.left = nil
tree.right = nil
tree.elem = elem
} else if elem < tree.elem {
tree.left = Insert(elem, tree.left)
} else if elem > tree.elem {
tree.right = Insert(elem, tree.right)
} else {
// 该节点已经在这颗树中了，我们什么也不做
}
return tree
}
|
在main函数中新建一个数组和空树，插入数据
1
2
3
4
5
6
7
8
|
func main() {
var a = [10]int{9,12,5,8,35,22,9,33,1,2}
var testTree *TreeNode
MakeEmpty(testTree)
for i:=0; i<len(a);i++ {
testTree = Insert(a[i], testTree)
}
}
|
判断是否存在某值，添加函数：
1
2
3
4
5
6
7
8
9
10
11
12
|
func Find(elem int, tree *TreeNode) bool {
if tree == nil {
return false
}
if tree.elem == elem {
return true
} else if elem > tree.elem {// 查找节点比当前树节点要大
return Find(elem, tree.right)
} else { // 查找节点比当前树节点要小
return Find(elem, tree.left)
}
}
|
在main函数中进行配对：
1
2
3
4
|
exist := Find(35,testTree)
exists := Find(3,testTree)
fmt.Println(exist)
fmt.Println(exists)
|
Find操作的功能是通过递归来实现的。判断当前树节点是否是要查找的节点，如果是则返回当前节点。否则，根据目标关键字的值的是否小于当前节点的关键字值分别去当前节点的左子树或右子树中去查找目标节点。打印的第一个值为 true，第二个值为 false（输出结果为 bool 型）
查找最小、最大值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func FindMin(tree *TreeNode) *TreeNode {
if tree == nil {
return nil
}
for tree.left != nil {
tree = tree.left
}
return tree
}
func FindMax(tree *TreeNode) *TreeNode {
if tree == nil {
return nil
}
if tree.right == nil {
return tree
}
return FindMax(tree.right)
}
|
查找最小值是通过迭代实现的，由于二叉搜索树中某个树节点的左子树的关键字始终小于这个树节点的关键字值，所以我们只需要一直遍历，找到最左的那个树节点，它就是整个树中最小的节点。
参考文章：Go与数据结构之二叉搜索树