树用于表示层次结构，比较好理解的类比是家族关系树。和哈希表或图结构一样，属于非连续数据结构。
二叉树是每个节点最多只有两个子节点。二叉搜索树的特性是左节点的值小于右节点，它是非常有用的数据结构，用于有效地存储和索引数据，以及数据检索。
1. 功能描述
1.1 术语
根节点：树的第顶级(零级)节点
子节点：树中除了根节点的节点
内部节点：每个节点至少有一个子节点
叶子节点：没有子节点的节点
子树：以某个节点作为根的节点集
1.2 方法说明
二叉树结构一般需要以下方法：
- Insert(t) 在树中插入原始
- Search(t) 如果树中存在该元素则返回true
- InOrderTraverse() 按照中序方式遍历所有
- PreOrderTraverse() 按照前序方式遍历所有
- PostOrderTraverse() 按照后序方式遍历所有
- Min() 返回树中最小元素
- Max() 返回树中最大元素
- String() 在命令行下渲染树
ItemBinarySearchTreegenny首先定义节点结构体：
type Node struct {
key int
value Item
left *Node //left
right *Node //right
}
key对应值可以是任意数据类型Item类型，key类型这里使用int类型，实际可以是任何能进行比较的数据类型。
在树中插入元素需要使用递归，因为需要为其找到合适的位置。规则是如果节点的key小于当前节点，如果其没有左子节点则作为其左子节点，否则使用其左子节点作为当前节点重新计算。又子节点规则一样。
遍历是遍历树所有节点的过程，提供三种方法实现。以这棵二叉搜索树为例:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 118 -> 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 -> 10 -> 9 -> 111 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4 -> 9 -> 11 -> 10 -> 8String方法，用于测试，通过打印节点信息让用户通过可视化方式检查。
------------------------------------------------
---[ 1
---[ 2
---[ 3
---[ 4
---[ 5
---[ 6
---[ 7
---[ 8
---[ 9
---[ 10
---[ 11
------------------------------------------------
2. 实现
这里主要说下删除逻辑，给定键删除对应节点。
如果待删除key小于当前节点key，则设当前节点为其左节点并递归调用自身。如果大于当前节点，则设当前节点为其右节点并递归调用自身。
直到两者key相等，则找到对应要删除的节点。如果找不到则直接返回nil。
删除节点有分几种情况。
- 没有子节点
直接设置该节点为nil，返回该节点。 - 有一个子节点
如果左节点为nil，则让该节点为其右节点。如果右节点为nil，让该节点为其左节点。然后返回该节点。 - 有两个子节点
最复杂的是这种情况。
因为可能节点还有其子节点。我们找到有子子树中的最小节点作为当前节点，然后删右边最小节点，最后返回该节点。
package tree
import (
"fmt"
"github.com/cheekybits/genny/generic"
"sync"
)
// 定义泛型
type Item generic.Type
// 树节点结构体
type Node struct {
key int
value Item
left *Node //left
right *Node //right
}
// 二叉搜索树结构体
type ItemBinarySearchTree struct {
root *Node
lock sync.RWMutex
}
// 插入元素
func (bst *ItemBinarySearchTree) Insert(key int, value Item) {
bst.lock.Lock()
defer bst.lock.Unlock()
n := &Node{key, value, nil, nil}
if bst.root == nil {
bst.root = n
} else {
insertNode(bst.root, n)
}
}
// 从node开始查找位置并插入新节点
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)
}
}
}
// 中序遍历
func (bst *ItemBinarySearchTree) InOrderTraverse(f func(Item)) {
bst.lock.RLock()
defer bst.lock.RUnlock()
inOrderTraverse(bst.root, f)
}
// internal recursive function to traverse in order
func inOrderTraverse(n *Node, f func(Item)) {
if n != nil {
inOrderTraverse(n.left, f)
f(n.value)
inOrderTraverse(n.right, f)
}
}
// 前序遍历
func (bst *ItemBinarySearchTree) PreOrderTraverse(f func(Item)) {
bst.lock.Lock()
defer bst.lock.Unlock()
preOrderTraverse(bst.root, f)
}
// internal recursive function to traverse pre order
func preOrderTraverse(n *Node, f func(Item)) {
if n != nil {
f(n.value)
preOrderTraverse(n.left, f)
preOrderTraverse(n.right, f)
}
}
// 后续遍历
func (bst *ItemBinarySearchTree) PostOrderTraverse(f func(Item)) {
bst.lock.Lock()
defer bst.lock.Unlock()
postOrderTraverse(bst.root, f)
}
// internal recursive function to traverse post order
func postOrderTraverse(n *Node, f func(Item)) {
if n != nil {
postOrderTraverse(n.left, f)
postOrderTraverse(n.right, f)
f(n.value)
}
}
// 查找最小元素节点
func (bst *ItemBinarySearchTree) Min() *Item {
bst.lock.RLock()
defer bst.lock.RUnlock()
n := bst.root
if n == nil {
return nil
}
for {
if n.left == nil {
return &n.value
}
n = n.left
}
}
// 查找最大元素节点
func (bst *ItemBinarySearchTree) Max() *Item {
bst.lock.RLock()
defer bst.lock.RUnlock()
n := bst.root
if n == nil {
return nil
}
for {
if n.right == nil {
return &n.value
}
n = n.right
}
}
// 搜索指定key的节点
func (bst *ItemBinarySearchTree) Search(key int) bool {
bst.lock.RLock()
defer bst.lock.RUnlock()
return search(bst.root, key)
}
// internal recursive function to search an item in the tree
func search(n *Node, key int) bool {
if n == nil {
return false
}
if key < n.key {
return search(n.left, key)
}
if key > n.key {
return search(n.right, key)
}
return true
}
// 删除指定key的节点
func (bst *ItemBinarySearchTree) Remove(key int) {
bst.lock.Lock()
defer bst.lock.Unlock()
remove(bst.root, key)
}
// internal recursive function to remove an item
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
}
// key == node.key
if node.left == nil && node.right == nil {
node = nil
return nil
}
if node.left == nil {
node = node.right
return node
}
if node.right == nil {
node = node.left
return node
}
minRightNode := node.right
for minRightNode.left != nil {
//find smallest value on the right side
minRightNode = minRightNode.left
}
node.key, node.value = minRightNode.key, minRightNode.value
node.right = remove(node.right, node.key)
return node
}
// 以字符串方式打印树
func (bst *ItemBinarySearchTree) String() {
bst.lock.Lock()
defer bst.lock.Unlock()
fmt.Println("------------------------------------------------")
stringify(bst.root, 0)
fmt.Println("------------------------------------------------")
}
// internal recursive function to print a tree
func stringify(n *Node, level int) {
if n != nil {
format := ""
for i := 0; i < level; i++ {
format += " "
}
format += "---[ "
level++
stringify(n.right, level)
fmt.Printf(format+"%d\n", n.key)
stringify(n.left, level)
}
}
3. 测试
package tree
import (
"fmt"
"testing"
)
var bst ItemBinarySearchTree
func fillTree(bst *ItemBinarySearchTree) {
bst.Insert(8, "8")
bst.Insert(4, "4")
bst.Insert(10, "10")
bst.Insert(2, "2")
bst.Insert(6, "6")
bst.Insert(1, "1")
bst.Insert(3, "3")
bst.Insert(5, "5")
bst.Insert(7, "7")
bst.Insert(9, "9")
}
func TestInsert(t *testing.T) {
fillTree(&bst)
bst.String()
bst.Insert(11, "11")
bst.String()
}
func TestRemove(t *testing.T) {
fillTree(&bst)
bst.String()
bst.Remove(4)
bst.String()
}
gennygenny -in binarysearchtree.go -out binarysearchtree-int.go gen "Item=int"
4. 总结
本文实现了Golang版本的二叉搜索树。删除操作相对复杂，这里只实现了右侧最小节点，读者还可以尝试左边最大节点。