二叉树(Binary tree)

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分…二叉树百度百科

golang中二叉树定义

type BTree struct {
    Data   int
    LBTree *BTree
    RBTree *BTree
}

插入结点

// InsertBtreeNode 插入节点
func InsertBtreeNode(tree *BTree, data int) *BTree {
    if tree == nil {
        tree = &BTree{Data: data}
        return tree
    }
    if data > tree.Data {
        tree.RBTree = InsertBtreeNode(tree.RBTree, data)
    } else {
        tree.LBTree = InsertBtreeNode(tree.LBTree, data)
    }
    return tree
}
func NewBtree(data []int) *BTree {
    var tree *BTree
    for _, v := range data {
        tree = InsertBtreeNode(tree, v)
    }
    return tree
}

先序遍历

// PreOrder 先序遍历
func PreOrder(tree *BTree, result *[]int) {
    if tree == nil {
        return
    }
    *result = append(*result, tree.Data)
    if tree.LBTree != nil {
        PreOrder(tree.LBTree, result)
    }
    if tree.RBTree != nil {
        PreOrder(tree.RBTree, result)
    }
}

中序遍历

// InOrder 中序遍历
func InOrder(tree *BTree, result *[]int) {
    if tree == nil {
        return
    }
    if tree.LBTree != nil {
        InOrder(tree.LBTree, result)
    }
    *result = append(*result, tree.Data)
    if tree.RBTree != nil {
        InOrder(tree.RBTree, result)
    }
}

后序遍历

// PostOrder 后序遍历
func PostOrder(tree *BTree, result *[]int) {
    if tree == nil {
        return
    }
    if tree.LBTree != nil {
        PostOrder(tree.LBTree, result)
    }
    if tree.RBTree != nil {
        PostOrder(tree.RBTree, result)
    }
    *result = append(*result, tree.Data)
}

测试代码

func main() {
    tree := bst.NewBtree([]int{9, 3, 2, 2, 7, 3, 1, 0, 12, 45})
    var result []int
    bst.PreOrder(tree, &result)
    log.Println("先序遍历 ", result)
    result = []int{}
    bst.InOrder(tree, &result)
    log.Println("中序遍历 ", result)
    result = []int{}
    bst.PostOrder(tree, &result)
    log.Println("后序遍历 ", result)
    result = []int{}
}

测试结果

2022/01/08 14:44:13 先序遍历  [9 3 2 2 1 0 3 7 12 45]
2022/01/08 14:44:13 中序遍历  [0 1 2 2 3 3 7 9 12 45]
2022/01/08 14:44:13 后序遍历  [0 1 2 3 2 7 3 45 12 9]