（7）Go实现二分搜索树-前中后序递归

上图是一种树数据结构，由n>=1个节点组成的有层次的关系集合，每个节点有0或多个子节点，没有父节点的节点称为跟节点root，有父节点但没有子节点的节点称为叶子节点。

为什么要有树数据结构，因为树是一种天然的组织结构，具有高效的性质，在很多场景，数据采用树结构存储后，会更高效

下面是树结构的一种实现类型：二分搜索树

（1）二分搜索数存储的数值要有可比性
（2）二分搜索树左子树的值都小于父节点，右子树的值都大于父节点

二分搜索树的定义和方法：该实现方法不存在重复元素
type node struct {
    value *int
    Left  *node
    Right *node
}

func NewNode() *node {
    return &node{}
}

// 向搜索树中插入val：非递归算法
func (tree *node) Add1(val int) {
    if tree.value == nil {
        *tree = node{&val, new(node), new(node)}
        return
    }

    for {
        switch {
        case *tree.value == val:
            return
        case *tree.value > val:
            if tree.Left.value == nil {
                *tree.Left = node{&val, new(node), new(node)}
                return
            }
            tree = tree.Left
        case *tree.value < val:
            if tree.Right.value == nil {
                *tree.Right = node{&val, new(node), new(node)}
                return
            }
            tree = tree.Right
        }
    }
}

// 向搜索树中插入val：递归算法
func (tree *node) Add2(val int) {
    if tree.value == nil {
        *tree = node{&val, new(node), new(node)}
    }

    if *tree.value > val {
        tree.Left.Add2(val)
    }
    if *tree.value < val {
        tree.Right.Add2(val)
    }
}

// 以root为根的二分搜索树中是否包含元素val，递归算法
func (tree *node) Contains(val int) bool {
    if tree.value == nil {
        return false
    }

    if *tree.value == val {
        return true
    }

    if *tree.value > val {
        return tree.Left.Contains(val)
    }
    return tree.Right.Contains(val)
}

//  前序遍历：递归算法: 前序遍历（先root节点，再左子树，再右子树）
func (tree *node) TraversePreOrder(resp *[]int) {
    // (写法1)，时间复杂度一样，但写法1比较清晰，更易于理解，
    if tree.value == nil {
        return
    }

    *resp = append(*resp, *tree.value)
    tree.Left.TraversePreOrder(resp)
    tree.Right.TraversePreOrder(resp)
}

// 中序遍历: 递归算法，先左子树，再root节点，再右子树
// 输出结果为所有节点小到大排序后的顺序
func (tree *node) TraverseInOrder(resp *[]int) {
    if tree.value == nil {
        return
    }

    tree.Left.TraverseInOrder(resp)
    *resp = append(*resp, *tree.value)
    tree.Right.TraverseInOrder(resp)
}

// 后序遍历: 递归算法，先输出左子树，再输出右子树，再输出根节点
func (tree *node) TraverseRearOrder(resp *[]int) {
    if tree.value == nil {
        return
    }

    tree.Left.TraverseRearOrder(resp)
    tree.Right.TraverseRearOrder(resp)
    *resp = append(*resp, *tree.value)
}

测试3种递归算法
func main() {
    b := fork_tree1.NewNode()
    nums := []int{5, 2, 3, 4, 8, 6, 9, 7，7}
    for _, v := range nums {
        b.Add2(v)
    }

    buf1 := &[]int{}
    b.TraversePreOrder(buf1)
    fmt.Println("前序遍历结果：", *buf1)

    buf2 := &[]int{}
    b.TraverseInOrder(buf2)
    fmt.Println("中序遍历结果：", *buf2)

    buf3 := &[]int{}
    b.TraverseRearOrder(buf3)
    fmt.Println("后序遍历结果：", *buf3)
}

测试结果
前序遍历结果： [5 2 3 4 8 6 7 9]
中序遍历结果： [2 3 4 5 6 7 8 9]
后序遍历结果： [4 3 2 7 6 9 8 5]

待续...

有bug欢迎指出，转载请注明出处。