Golang 数据结构:二叉搜索树

Golang 中二叉搜索树的实现及常用操作,数据结构系列原文:flaviocopes.com,翻译已获作者授权。

概念

树(tree):一种分层的数据结构,类比家谱

二叉树(binary tree):每个节点最多只有 2 个子节点的树

二叉搜索树(binary search tree):左节点的值均小于右节点值的二叉树

  • 深度(depth):从 root 根结点到当前节点唯一路径的长度
  • 高度(height):从当前节点到一片树叶最长的路径的长度

  • 根(Root):深度为 0 的树节点

  • 内部节点(Internal node):至少有一个子节点的节点
  • 树叶(Leaf):无子节点的节点
  • 兄弟节点(sibling):拥有相同父节点的子节点

二叉搜索树

常用操作与节点定义

1
2
3
4
5
6
7
8
9
Insert(v)		// 向二叉搜索树的合适位置插入节点
Search(k) // 检查序号为 k 的元素在树中是否存在
Remove(v) // 移除树中所有值为 v 的节点
Min() // 获取二叉搜索树中最小的值
Max() // 获取二叉搜索树中最大的值
InOrderTraverse() // 中序遍历树
PreOrderTraverse() // 先序遍历树
PostOrderTraverse() // 后续遍历树
String() // 在命令行格式化打印出二叉树

同样使用 genny 提供代码的复用性,树类型命名为: ItemBinarySearchTree,树节点的结构体定义如下:

1
2
3
4
5
6
type Node struct {
key int // 中序遍历的节点序号
value Item // 节点存储的值
left *Node // 左子节点
right *Node // 右子节点
}

key 是各节点的位置在先序遍历中的序号,key 的值这里使用 int,可以是任意可比较的数据类型。

插入操作与遍历

插入操作需要使用到递归,插入操作需要从上到下查找新节点在树中合适的位置:新节点的值小于任意节点,则向左子树继续寻找,同理向右子树查找,直到查找到树叶节点再插入。

遍历操作有三种方式:

  • 中序遍历(in-order):左子树–>根结点–> 右树:1->2->3->4->5->6->7->8->9->10->11

  • 先序遍历(pre-order):根结点–>左子树–>右子树:8->4->2->1->3->6->5->7 >10->9->11

  • 后序遍历(post-order):左子树–>右子树–>根结点:1->3->2->5->7->6->4->9->11->10->8

String() 可视化树结构:


代码实现

Insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 向二叉搜索树的合适位置插入节点
func (tree *ItemBinarySearchTree) Insert(key int, value Item) {
tree.lock.Lock()
defer tree.lock.Unlock()
newNode := &Node{key, value, nil, nil}
// 初始化树
if tree.root == nil {
tree.root = newNode
} else {
// 在树中递归查找正确的位置并插入
insertNode(tree.root, newNode)
}
}

func insertNode(node, newNode *Node) {
// 插入到左子树
if newNode.key < node.key {
if node.left == nil {
node.left = newNode
} else {
// 递归查找左边插入
insertNode(node.left, newNode)
}
} else {
// 插入到右子树
if node.right == nil {
node.right = newNode
} else {
// 递归查找右边插入
insertNode(node.right, newNode)
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 检查序号为 k 的元素在树中是否存在
func (tree *ItemBinarySearchTree) Search(key int) bool {
tree.lock.RLock()
defer tree.lock.RUnlock()
return search(tree.root, key)
}
func search(node *Node, key int) bool {
if node == nil {
return false
}
// 向左搜索更小的值
if key < node.key {
return search(node.left, key)
}
// 向右搜索更大的值
if key > node.key {
return search(node.right, key)
}
return true // key == node.key
}

Remove

删除节点的流程

先递归查找,再删除节点。但在删除时需根据节点拥有子节点的数量,分如下 3 种情况:

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 删除指定序号的节点
func (tree *ItemBinarySearchTree) Remove(key int) {
tree.lock.Lock()
defer tree.lock.Unlock()
remove(tree.root, key)
}

// 递归删除节点
func remove(node *Node, key int) *Node {
// 要删除的节点不存在
if node == nil {
return nil
}

// 寻找节点
// 要删除的节点在左侧
if key < node.key {
node.left = remove(node.left, key)
return node
}
// 要删除的节点在右侧
if key > node.key {
node.right = remove(node.right, key)
return node
}

// 判断节点类型
// 要删除的节点是叶子节点,直接删除
// if key == node.key {
if node.left == nil && node.right == nil {
node = nil
return node
}

// 要删除的节点只有一个节点,删除自身
if node.left == nil {
node = node.right
return node
}
if node.right == nil {
node = node.left
return node
}

// 要删除的节点有 2 个子节点,找到右子树的最左节点,替换当前节点
mostLeftNode := node.right
for {
// 一直遍历找到最左节点
if mostLeftNode != nil && mostLeftNode.left != nil {
mostLeftNode = mostLeftNode.left
} else {
break
}
}
// 使用右子树的最左节点替换当前节点,即删除当前节点
node.key, node.value = mostLeftNode.key, mostLeftNode.value
node.right = remove(node.right, node.key)
return node
}

Min、Max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 获取树中值最小的节点:最左节点
func (tree *ItemBinarySearchTree) Min() *Item {
tree.lock.RLock()
defer tree.lock.RUnlock()
node := tree.root
if node == nil {
return nil
}
for {
if node.left == nil {
return &node.value
}
node = node.left
}
}

// 获取树中值最大的节点:最右节点
func (tree *ItemBinarySearchTree) Max() *Item {
tree.lock.RLock()
defer tree.lock.RUnlock()
node := tree.root
if node == nil {
return nil
}
for {
if node.right == nil {
return &node.value
}
node = node.right
}
}

Traverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 先序遍历:根节点 -> 左子树 -> 右子树
func (tree *ItemBinarySearchTree) PreOrderTraverse(printFunc func(Item)) {
tree.lock.RLock()
defer tree.lock.RUnlock()
preOrderTraverse(tree.root, printFunc)
}
func preOrderTraverse(node *Node, printFunc func(Item)) {
if node != nil {
printFunc(node.value) // 先打印根结点
preOrderTraverse(node.left, printFunc) // 再打印左子树
preOrderTraverse(node.right, printFunc) // 最后打印右子树
}
}

// 中序遍历:左子树 -> 根节点 -> 右子树
func (tree *ItemBinarySearchTree) PostOrderTraverse(printFunc func(Item)) {
tree.lock.RLock()
defer tree.lock.RUnlock()
postOrderTraverse(tree.root, printFunc)
}
func postOrderTraverse(node *Node, printFunc func(Item)) {
if node != nil {
postOrderTraverse(node.left, printFunc) // 先打印左子树
postOrderTraverse(node.right, printFunc) // 再打印右子树
printFunc(node.value) // 最后打印根结点
}
}

// 后序遍历:左子树 -> 右子树 -> 根结点
func (tree *ItemBinarySearchTree) InOrderTraverse(printFunc func(Item)) {
tree.lock.RLock()
defer tree.lock.RUnlock()
inOrderTraverse(tree.root, printFunc)
}
func inOrderTraverse(node *Node, printFunc func(Item)) {
if node != nil {
inOrderTraverse(node.left, printFunc) // 先打印左子树
printFunc(node.value) // 再打印根结点
inOrderTraverse(node.right, printFunc) // 最后打印右子树
}
}

String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 后序遍历打印树结构
func (tree *ItemBinarySearchTree) String() {
tree.lock.Lock()
defer tree.lock.Unlock()
if tree.root == nil {
println("Tree is empty")
return
}
stringify(tree.root, 0)
println("----------------------------")
}
func stringify(node *Node, level int) {
if node == nil {
return
}

format := ""
for i := 0; i < level; i++ {
format += "\t" // 根据节点的深度决定缩进长度
}
format += "----[ "
level++
// 先递归打印左子树
stringify(node.left, level)
// 打印值
fmt.Printf(format+"%d\n", node.key)
/// 再递归打印右子树
stringify(node.right, level)
}

测试用例:tree_test.go


总结

对于二叉搜索树的操作,增删查都与递归相关,所以在实现时一定要分析清楚递归的终止条件,在正确的条件下 return,避开死循环