Go：实现二叉搜索树（BST）

二叉搜索树是一种支持快速查找、增加和删除元素的数据结构。二叉搜索树中的节点是有序的，因此支持快速查找。该数据结构由P.F.Windley、A.D.Booth、A.J.T.Colin和T.N.Hibbard发明的。

二叉搜索树的平均空间复杂度是O(n)，插入、删除和搜索操作的时间就复杂的是O(logn)。二叉搜索树节点包含以下属性：

• 一个整型key值
• 一个整型value值
• 包含左节点leftNode和右节点rightNode
• 左节点key小于当前节点，右节点key大于当前节点

节点定义代码如下：

type TreeNode struct {
    key int
    value int
    leftNode *TreeNode
    rightNode *TreeNode
}

二叉搜索树结构体定义，其包含一个根节点rootNode是TreeNode类型，以及一个互斥锁sync.RWMutex类型。二叉搜索树的遍历是从根节点出发的，然后是左节点和右节点：

type BinarySearchTree struct {
    rootNode *TreeNode
    lock sync.RWMutex
}

定义好了二叉搜索树结构体类型，接下来实现其方法。

插入方法：InsertElement

该方法作用是将一个包含key和value的节点插入到二叉搜索树中。插入之前要获取锁，插入完成释放锁。

func (tree *BinarySearchTree)InsertElement(key int, value int)  {
    tree.lock.Lock()
    defer tree.lock.Unlock()
    var treeNode *TreeNode
    treeNode = &TreeNode{
        key:       key,
        value:     value,
        leftNode:  nil,
        rightNode: nil,
    }
    if tree.rootNode == nil {
        tree.rootNode = treeNode
    } else {
        insertTreeNode(tree.rootNode, treeNode)
    }
}

先根据key，value创建treeNode节点。然后判断根节点是否为空，如果是空就将新增的节点赋值给根节点。如果根节点不为空，调用insertTreeNode函数找到合适的位置插入。

func insertTreeNode(rootNode *TreeNode, newTreeNode *TreeNode)  {
    if newTreeNode.key < rootNode.key {
        if rootNode.leftNode ==  nil {
            rootNode.leftNode = newTreeNode
        } else {
            insertTreeNode(rootNode.leftNode, newTreeNode)
        }
    } else {
        if rootNode.rightNode == nil{
            rootNode.rightNode = newTreeNode
        } else{
            insertTreeNode(rootNode.rightNode, newTreeNode)
        }
    }
}

根据二叉搜索树的特点，每个节点的key比左节点key要大，比右节点的key要小。因此先和左节点的key比较，如果左节点为空，就将新增节点赋值给左节点，否则继续递归找。同理如果新增节点key比左节点大，就和右节点比较，为空就赋值，否则递归。

inOrderTraverse方法：顺序遍历二叉搜索树

该方法按顺序遍历树中的每个节点。先调用RLock()读锁，遍历完后释放：

func (tree *BinarySearchTree)InOrderTraverseTree(function func(int))  {
    tree.lock.RLock()
    defer tree.lock.RUnlock()
    inOrderTraverseTree(tree.rootNode, function)
}

func inOrderTraverseTree(treeNode *TreeNode, function func(int))  {
    if treeNode != nil {
        inOrderTraverseTree(treeNode.leftNode, function)
        function(treeNode.value)
        inOrderTraverseTree(treeNode.rightNode, function)
    }
}

为了避免数据竞争，这里创建一个内部调用函数来实现有序遍历二叉搜索树。根据二叉搜索树特点，先遍历左子树，然后当前节点最后遍历右子树，也称为中序遍历。

PreOrderTraverse方法：前序遍历

先遍历当前节点，然后是左子树最后右子树；

func (tree *BinarySearchTree)PreOrderTraverseTree(function func(int))  {
    tree.lock.RLock()
    defer tree.lock.RUnlock()
    preOrderTraverseTree(tree.rootNode, function)
}

func preOrderTraverseTree(treeNode *TreeNode, function func(int))  {
    if treeNode != nil {
        function(treeNode.value)
        preOrderTraverseTree(treeNode.leftNode, function)
        preOrderTraverseTree(treeNode.rightNode, function)
    }
}

PostOrderTraverse方法：后序遍历

后序遍历：先左子树，然后右子树最后是当前节点

func (tree *BinarySearchTree)PostOrderTraverseTree(function func(int))  {
    tree.lock.RLock()
    defer tree.lock.RUnlock()
    postOrderTraverseTree(tree.rootNode, function)
}

func postOrderTraverseTree(treeNode *TreeNode, function func(int))  {
    if treeNode != nil {
        postOrderTraverseTree(treeNode.leftNode, function)
        postOrderTraverseTree(treeNode.rightNode, function)
        function(treeNode.value)
    }
}

MinNode方法：最小节点

该方法：用于查找二叉搜索树中key最小的节点值。

func (tree *BinarySearchTree)MinNode() *int {
    tree.lock.RLock()
    defer tree.lock.RUnlock()
    var treeNode *TreeNode
    treeNode = tree.rootNode
    if treeNode == nil {
        return (*int)(nil)
    }
    for  {
                //最小值位于左子树
        if treeNode.leftNode == nil {
            return &treeNode.value
        }
        treeNode = treeNode.leftNode
    }
}

根据二叉搜索树的特点：左子树值都小于当前节点，所以如果当前节点的左节点为空，说明当前节点的key是最小的

MaxNode方法：查询最大key节点

该方法和MinNode方法相反，最大子位于当前节点右子树。如果当前节点的右节点为空，说明当前节点是值最大节点。

func (tree *BinarySearchTree)MaxNode() *int {
    tree.lock.RLock()
    defer tree.lock.RUnlock()
    var treeNode *TreeNode
    treeNode = tree.rootNode
    if treeNode == nil {
        return (*int)(nil)
    }
    for  {
        if treeNode.rightNode == nil {
            return &treeNode.value
        }
        treeNode = treeNode.rightNode
    }
}

SearchNode方法：根据key查询对应节点是否存在。

func (tree *BinarySearchTree)SearchNode(key int) bool {
    tree.lock.RLock()
    defer tree.lock.RUnlock()
    return searchNode(tree.rootNode, key)
}

func searchNode(treeNode *TreeNode, key int) bool {
    if treeNode == nil {
        return false
    }
    if key < treeNode.key{
        return searchNode(treeNode.leftNode, key)
    }
    if key > treeNode.key{
        return searchNode(treeNode.rightNode, key)
    }
    return true
}

二叉搜索树：当前节点比左子树所有节点大，比右子树所有节点小。因此在查找一个key是否存在时，如果当前节点key比搜索key更小，就继续在左子树查找；如果要搜索key大于当前节点的key就在右子树查找。否则当前节点就是要查找的节点。

removeNode方法：删除节点

func (tree *BinarySearchTree) RemoveNode(key int) {
    tree.lock.Lock()
    defer tree.lock.Unlock()
    removeNode(tree.rootNode, key)
}

func removeNode(treenode *TreeNode, key int) *TreeNode {
    if treenode == nil {
        return nil
    }
    if key < treenode.key {
        treenode.leftNode = removeNode(treenode.leftNode, key)
        return treenode
    }
    if key > treenode.key {
        treenode.rightNode = removeNode(treenode.rightNode, key)
        return treenode
    }
    //key == treeNode.ley
    if treenode.leftNode == nil && treenode.rightNode == nil {
        treenode = nil
        return nil
    }
    //要删除的节点，左节点为空
    if treenode.leftNode == nil {
        treenode = treenode.rightNode
        return treenode
    }
    //要删除的节点，右节点为空
    if treenode.rightNode == nil {
        treenode = treenode.leftNode
        return treenode
    }
    //要删除的节点，左右节点都不为空
    var leftmostrightNode *TreeNode
    leftmostrightNode = treenode.rightNode
    for {
        if leftmostrightNode != nil && leftmostrightNode.leftNode != nil {
            leftmostrightNode = leftmostrightNode.leftNode
        } else {
            break
        }
    }
       //将右子树最小节点值，替换待删除节点的值
    treenode.key, treenode.value = leftmostrightNode.key, leftmostrightNode.value
      //递归删除右子树最小节点
    treenode.rightNode = removeNode(treenode.rightNode, treenode.key)
    return treenode
}

二叉搜索树删除节点比较复杂，递归的删除。分4种情况：
1、待删除节点，左右节点为空，直接删除。
2、待删除节点，左节点为空，直接将右节点赋值给删除节点覆盖
3、待删除节点，右节点为空，直接将左节点赋值给删除节点覆盖。
4、待删除节点，左右节点都不为空。用其右子树的最小结点代替待删除结点。代码中的leftmostrightNode节点为右子树最小节点。