golang 二叉树的遍历

问题

实现二叉树的先序，中序，后序，层级遍历

举例的二叉树图如下

代码示例：

package main

import (
    "fmt"
    "sync"
)

// 二叉树的先序，中序，后序，层级遍历

// 二叉树结点
type TreeNode struct {
    Data  string
    Left  *TreeNode
    Right *TreeNode
}
// 链表结点
type LinkNode struct {
    Data *TreeNode
    Next *LinkNode
}
// 链表队列
type LinkQueue struct {
    Top  *LinkNode
    Size int
    Lock sync.Mutex
}

func main() {
    // A B C D E F
    t := &TreeNode{Data: "A"}
    t.Left = &TreeNode{Data: "B"}
    t.Right = &TreeNode{Data: "C"}
    t.Left.Left = &TreeNode{Data: "D"}
    t.Left.Right = &TreeNode{Data: "E"}
    t.Right.Left = &TreeNode{Data: "F"}

    fmt.Println("前序：")
    PreOrder(t)
    fmt.Println()
    fmt.Println("中序：")
    MidOrder(t)
    fmt.Println()
    fmt.Println("后序：")
    PostOrder(t)
    fmt.Println()
    fmt.Println("层级：")
    LayerOrder(t)
    fmt.Println()
}

// 先序
func PreOrder(t *TreeNode) {
    if t == nil {
        return
    }
    fmt.Print(t.Data, " ")
    PreOrder(t.Left)
    PreOrder(t.Right)
}
// 中序
func MidOrder(t *TreeNode) {
    if t == nil {
        return
    }
    MidOrder(t.Left)
    fmt.Print(t.Data, " ")
    MidOrder(t.Right)
}
// 后序
func PostOrder(t *TreeNode) {
    if t == nil {
        return
    }
    PostOrder(t.Left)
    PostOrder(t.Right)
    fmt.Print(t.Data, " ")
}
// 层级
func LayerOrder(t *TreeNode) {
    if t == nil {
        return
    }

    q := new(LinkQueue)
    q.Add(t)
    for !q.IsEmpty() {
        e := q.Remove()
        fmt.Print(e.Data, " ")

        if e.Left != nil {
            q.Add(e.Left)
        }
        if e.Right != nil {
            q.Add(e.Right)
        }
    }
}

// 入队
func (q *LinkQueue) Add(t *TreeNode) {
    q.Lock.Lock()
    defer q.Lock.Unlock()

    if q.Top == nil {
        q.Top = new(LinkNode)
        q.Top.Data = t
    } else {
        temp := new(LinkNode)
        temp.Data = t
        TNode := q.Top
        for TNode.Next != nil {
            TNode = TNode.Next
        }
        TNode.Next = temp
    }
    q.Size++
}
// 出队
func (q *LinkQueue) Remove() *TreeNode {
    q.Lock.Lock()
    defer q.Lock.Unlock()

    if q.Size == 0 {
        panic("queue is empty!")
    }

    t := q.Top.Data
    q.Top = q.Top.Next
    q.Size--
    return t
}
// 是否为空
func (q *LinkQueue) IsEmpty() bool {
    return q.Size == 0
}