圖源：庫洛魔法使第一季第四集

經過昨天聖誕夜和雪兔哥在遊樂園激戰後，時間一下子又來到了開學，小櫻已是五年級的學生。

這天才剛開學，天上卻不斷的降雪，根據先前的經驗，一定又是庫洛牌搞得鬼。但是這集雪跟要教的樹沒有關係，所以只能把第一季第四集的樹拿來移花接木當一下封面了。

劇情來到了第二季，各位魔法使們，我們還有幾張「簡單」的資結Golang牌要搜集，大家一起加油吧！

什麼是樹

樹(Tree)，如同先前教的鏈結串列(Linked list)、堆疊(Stack)和佇列(Queue)一樣，都是一種資料結構。在魔法科學(資訊科學)中樹是倒過來長的，我們通常會這樣子形容一棵樹

先不要管什麼根、莖、葉、花、果實、種子了。

每個圓圈都是一個節點 Node ，而 Node 通常包含了「值」和指向「下一個節點的指標們」，有點類似先前學的鏈結串列(linked list)，只是樹的指標不侷限下一個。

今天不會講到那麼複雜，只會討論分支度只有 2 的樹，又稱為「二元樹」

二元樹的每個節點最多只會指向另外 2 個節點

因此可以簡單的用 Go 表示成

type Node struct{
    val interface{}    // 節點值
    left *Node         // 指向左節點
    right *Node        // 指向右節點
}

創建一棵樹

首先我們先創建一個 package，至於要怎麼創建？請複習：#14 套件 Package (2020) & 套件實戰(math, http, sort) | Golang魔法使

因為這次只要實作簡單的操作，所以這次實作一步做完

./tree/tree.go

package tree

type Node struct{
    Val interface{}
    Right *Node
    Left *Node
}

func NewNode(val interface{}) *Node{
    node := new(Node)
    node.Val = val
    return node
}

func (n *Node) AddLeftNode(l *Node){
    n.Left = l
}

func (n* Node) AddRightNode(r *Node){
    n.Right = r
}

本系列教學採用新版 Golang version >= 1.11 並使用 go mod 初始化為 practice module

實作上圖二元樹

./lesson24.go

package main

import(
    "practice/tree"
)

func main(){
    root   := tree.NewNode(3)
    node7  := tree.NewNode(7)
    node1  := tree.NewNode(1)
    node2  := tree.NewNode(2)
    node6  := tree.NewNode(6)
    node9  := tree.NewNode(9)
    node5  := tree.NewNode(5)
    node11 := tree.NewNode(11)
    node4  := tree.NewNode(4)

    root.AddLeftNode(node7)
    root.AddRightNode(node1)
    node7.AddLeftNode(node2)
    node7.AddRightNode(node6)
    node6.AddLeftNode(node5)
    node6.AddRightNode(node11)
    node1.AddRightNode(node9)
    node9.AddLeftNode(node4)
}

走訪一棵樹

創建一顆單純的二元樹並沒有很複雜，甚至比 Linked-list 還簡單，但是如果想要走訪一棵樹，或著照著某些規則創建都不容易

在走訪一顆樹時有主要三種走訪方式後序、前序、中序

後序走訪

1. 後序走訪：依序先走訪 「左」「右」「中」
   什麼意思呢？簡單來說從根節點開始走
   1. 如果有左節點，那就往左走
   2. 否則如果有右節點就往右走
   3. 否則把自己印出

STEP1

從根節點開始一直可以往左走最後走到 2，因為 2 沒有左節點也沒有右節點所以將其印出

STEP2

回到前一個節點 7 ，因為還有右節點所以往 6 走，而 6 又有左節點所以往左走，節點 5 沒有左節點也沒有右節點因此印出

STEP3

回到前一個節點 6，因為還有右節點所以往 11 走，11 沒有左節點也沒有右節點所以印出

STEP4

回到前一個節點 6，因為 6 沒有左節點也沒有右節點所以印出

STEP5

回到前一個節點 7，因為 7 沒有左節點也沒有右節點所以印出

STEP6

回到前一個節點 3，因為 3 還有右子點所以往右走到 1，1 沒有左子點所以往右走到 9 ，9 有左子點所以走到 4，但 4 沒有左節點也沒有右節點所以印出

STEP7

回到前一個節點 9，因為 9 沒有左節點也沒有右節點所以印出

STEP8

回到前一個節點 1，因為 1 沒有左節點也沒有右節點所以印出

STEP9

最後回到根節點 3，印出 3

總結：

因為根節點最後印出所以稱為後序走訪，這根樹的後序走訪為

2 5 11 6 7 4 9 1 3

實作後序走訪

package main

import(
    "practice/tree"
    "fmt"
)

func postorder(n *tree.Node){
    if n != nil{
        // 嘗試往左走
        postorder(n.Left)
        // 嘗試往右走
        postorder(n.Right)
        // 都嘗試過後印出
        fmt.Printf("%d ", n.Val)
    }
}

func main(){
    root   := tree.NewNode(3)
    node7  := tree.NewNode(7)
    node1  := tree.NewNode(1)
    node2  := tree.NewNode(2)
    node6  := tree.NewNode(6)
    node9  := tree.NewNode(9)
    node5  := tree.NewNode(5)
    node11 := tree.NewNode(11)
    node4  := tree.NewNode(4)

    root.AddLeftNode(node7)
    root.AddRightNode(node1)
    node7.AddLeftNode(node2)
    node7.AddRightNode(node6)
    node6.AddLeftNode(node5)
    node6.AddRightNode(node11)
    node1.AddRightNode(node9)
    node9.AddLeftNode(node4)

    postorder(root)
}

執行結果：
2 5 11 6 7 4 9 1 3

中序走訪

而所謂的中序走訪則是先走左子樹，如果沒有左子樹則把自己印出，然後開始走右子樹

func inorder(n *tree.Node){
    if n != nil{
        // 嘗試往左走
        inorder(n.Left)
        // 印出
        fmt.Printf("%d ", n.Val)
        // 嘗試往右走
        inorder(n.Right)
    }
}

前序走訪

前序走訪則是先將自己印出，再開始走左子樹，走完再走右子樹

func preorder(n *tree.Node){
    if n != nil{
        // 印出
        fmt.Printf("%d ", n.Val)
        // 嘗試往左走
        preorder(n.Left)
        // 嘗試往右走
        preorder(n.Right)
    }
}

後記

• 二元搜尋樹
• AVL樹
• 霍夫曼樹
• 紅黑樹
• B樹

本集圖片主要來自：

• 庫洛魔法使第二季第一集