二叉树Golang语言实现

二叉树(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]
广告 广告位招租
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
小黄脸
上一篇
下一篇