本文最后更新于 超过 3 年前，文中所描述的信息可能已发生改变。
二叉树(Binary tree)
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分
golang中二叉树定义
go
type BTree struct {
Data int
LBTree *BTree
RBTree *BTree
}插入结点
go
// 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
}先序遍历
go
// 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)
}
}中序遍历
go
// 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)
}
}后序遍历
go
// 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)
}测试代码
go
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{}
}测试结果
go
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]