原文链接： 使用 Go 语言实现二叉搜索树

二叉树是一种常见并且非常重要的数据结构，在很多项目中都能看到二叉树的身影。

它有很多变种，比如红黑树，常被用作 std::map 和 std::set 的底层实现；B 树和 B+ 树，广泛应用于数据库系统中。

本文要介绍的二叉搜索树用的也很多，比如在开源项目 go-zero 中，就被用来做路由管理。

这篇文章也算是一篇前导文章，介绍一些必备知识，下一篇再来介绍具体在 go-zero 中的应用。

二叉搜索树的特点

最重要的就是它的有序性，在二叉搜索树中，每个节点的值都大于其左子树中的所有节点的值，并且小于其右子树中的所有节点的值。

这意味着通过二叉搜索树可以快速实现对数据的查找和插入。

Go 语言实现

本文主要实现了以下几种方法：

• Insert(t)：插入一个节点
• Search(t)：判断节点是否在树中
• InOrderTraverse()：中序遍历
• PreOrderTraverse()：前序遍历
• PostOrderTraverse()：后序遍历
• Min()：返回最小值
• Max()：返回最大值
• Remove(t)：删除一个节点
• String()：打印一个树形结构

下面分别来介绍，首先定义一个节点：

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)
    }
}

// internal function to find the correct place for a node in a tree
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
    }
}

查找节点是否存在：

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
}

删除节点：

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