本篇文章为A Binary Search Tree的核心内容翻译，仅做个人学习之用。
原文在文章开头花了不少篇幅介绍查找、二叉树相关内容，本译文假定你具备一定的计算机基础，就不做过多介绍了。
Import and globals
在构建BST的结构时候，需要导入以下包，作用都很简单分别是提示Error，打印以及Log相关内容：
package main
import (
"errors"
"fmt"
"log"
)
A Tree Node
按照之前的定义，一个树节点需要包含节点数值、左孩子节点、右孩子节点。树就是一种递归的数据结构，孩子节点也同样具备上述特性。在这个小实例中，每个树节点还包含一个简单的string值域。所以Node节点的定义如下所示：
type Node struct {
Value string
Data string
Left *Node
Right *Node
}
Insert
插入操作。首先要考虑树是否为nil，无法向nil树中插入数据。如果树不是nil，则由于二叉查找树的特性，即节点根据节点内的数值，是存在顺序的。所以新插入的节点，需要找到合适的位置。新插入的节点的值，需要跟树中节点的数值进行比较。
func (n *Node) Insert(value, data string) error {
// 如果树为nil，则抛出异常
if n == nil {
return errors.New("Cannot insert a value into a nil tree")
}
switch {
// 如果插入的数值在树中早已存在，返回
case value == n.Value:
return nil
// 若插入的数值小于当前的value
case value < n.Value:
if n.Left == nil {
n.Left = &Node{Value: value, Data: data}
return nil
}
return n.Left.Insert(value, data)
// 若插入的数值大于当前的value
case value > n.Value:
if n.Right == nil {
n.Right = &Node{Value: value, Data: data}
return nil
}
return n.Right.Insert(value, data)
}
return nil
}
如上代码所示，在与当前节点的value进行比较之后，分为以下情况：1：若新插入的节点值小于当前节点，按照BST的特性，应该往当前节点的左子树插入，此时要考虑当前节点的左孩子节点是否为nil，如果为nil，则直接将插入节点放置到当前节点的左孩子节点位置，如果当前节点的左孩子节点不是nil，则需要递归插入。2：若新插入的节点值大于当前节点，也是重复上述过程，道理是一样的。
Find
查找操作首先也要判断树是不是为nil，如果为nil就不必要进行后续的操作了。如果树不是nil，则接着比较，需要查找的value与当前的节点value值域进行比较。也是按照大于、小于、等于划分不同情况，根据需要决定是否进行递归查询。
func (n *Node) Find(s string) (string, bool) {
if n == nil {
return "", false
}
switch {
case s == n.Value:
return n.Data, true
case s < n.Value:
return n.Left.Find(s)
default:
return n.Right.Find(s)
}
}
findMax
查找最大值。这个操作本身是有点麻烦，但是由于BST的特性，即数值的排列是有序递归的，所以最大值肯定是在右子树中，本质上也是一个递归查询的过程。递归的终止节点就是遇到了叶子节点。
func (n *Node) findMax(parent *Node) (*Node, *Node) {
if n.Right == nil {
return n, parent
}
return n.Right.findMax(n)
}
replaceNode
replaceNode用来替换，本身由parent指向n节点的指针，使得parent指向replacement节点。该种需求情况下，要求parent不能为nil节点。如果parent的左指针指向n，则将其改变成指向replacement节点即可，如果不是这种情况就用parent的右指针指向replacement节点。
func (n *Node) replaceNode(parent, replacement *Node) error {
if n == nil {
return errors.New("replaceNode() not allowed on a nil node")
}
if n == parent.Left {
parent.Left = replacement
return nil
}
parent.Right = replacement
return nil
}
Delete
节点的删除操作。同样要求树不能为nil，即n节点不能为nil。删除操作同样是递归操作，要与当前节点比较。一旦匹配到要删除的节点，则需要考虑当前节点是存在左右孩子节点、只左孩子节点还是只存在右孩子节点。并且，需要知道当前要删除节点的父母节点。因为节点的删除，并不是简单的删除操作，还要去再次将树的节点给链接起来。
func (n *Node) Delete(s string, parent *Node) error {
// 如果树为nil，抛出异常
if n == nil {
return errors.New("Value to be deleted does not exist in the tree")
}
switch {
// value小于当前节点的数值
case s < n.Value:
return n.Left.Delete(s, n)
// value大于当前节点的数值
case s > n.Value:
return n.Right.Delete(s, n)
// value与当前节点的数值相等
default:
// 如果要删除的节点是叶子节点
if n.Left == nil && n.Right == nil {
n.replaceNode(parent, nil)
return nil
}
// 如果要删除的节点左孩子节点为nil
if n.Left == nil {
n.replaceNode(parent, n.Right)
return nil
}
// 如果要删除的节点右孩子节点为nil
if n.Right == nil {
n.replaceNode(parent, n.Left)
return nil
}
// 如果有两个孩子节点，在左子树中找出最大的值
replacement, replParent := n.Left.findMax(n)
// 用replacement的数值替代n节点的值域
n.Value = replacement.Value
n.Data = replacement.Data
// 删除这个替代节点
return replacement.Delete(replacement.Value, replParent)
}
}
Traverse
树的遍历操作。基本的遍历操作，从左至右，也就是传统的中序遍历。
func (t *Tree) Traverse(n *Node, f func(*Node)) {
if n == nil {
return
}
t.Traverse(n.Left, f)
// 核心操作
f(n)
t.Traverse(n.Right, f)
}
如何去应用这个遍历方法呢？看下面的代码：
fmt.Print("Sorted values: | ")
// 匿名函数简化操作
tree.Traverse(tree.Root, func(n *Node) { fmt.Print(n.Value, ": ", n.Data, " | ") })
fmt.Println()
类似于上面这种调用还是很有意思的，代码量不多，简单清晰。
ok，以上内容就是Go中二叉查找树的实现方式！！！
有疑问加站长微信联系（非本文作者）
