Go 遍历树

1. 二叉树遍历

      1
    /   \
  2       3
 / \    /  \
4   5  6    7
      / \
     8   9

前序输出: 1 2 4 5 3 6 8 9 7
中序输出: 4 2 5 1 8 6 9 3 7
后序输出: 4 5 2 8 9 6 7 3 1
层序输出: 1 2 3 4 5 6 7 8 9

2. 实现代码

2.1 构建二叉树

type Tree struct {
	Val    int
	Left   *Tree
	Right  *Tree
	IsRoot bool
}

var root = &Tree{
	Val:    1,
	Left:   node2,
	Right:  node3,
	IsRoot: true,
}

var node2 = &Tree{
	Val:   2,
	Left:  node4,
	Right: node5,
}

var node3 = &Tree{
	Val:   3,
	Left:  node6,
	Right: node7,
}

var node4 = &Tree{
	Val: 4,
}

var node5 = &Tree{
	Val: 5,
}

var node6 = &Tree{
	Val:   6,
	Left:  node8,
	Right: node9,
}

var node7 = &Tree{
	Val: 7,
}

var node8 = &Tree{
	Val: 8,
}

var node9 = &Tree{
	Val: 9,
}

2.2 前序遍历

func preorder(t *Tree) {
	if t == nil {
		return
	}

	fmt.Printf("%d, ", t.Val)
	preorder(t.Left)
	preorder(t.Right)
}

2.3 中序遍历

func inorder(t *Tree) {
	if t == nil {
		return
	}

	inorder(t.Left)
	fmt.Printf("%d, ", t.Val)
	inorder(t.Right)
}

2.4 后序遍历

func postorder(t *Tree) {
	if t == nil {
		return
	}

	postorder(t.Left)
	postorder(t.Right)
	fmt.Printf("%d, ", t.Val)
}

2.5 层序遍历

先将二叉树改造为队列

type Queue struct {
	Val    []*Tree
	Length int
}

func (q *Queue) Push(t *Tree) {
	q.Val = append(q.Val, t)
}

func (q *Queue) Pop() *Tree {
	len := q.Len()
	if len == 0 {
		panic("Queue is empty")
	}
	node := q.Val[0]
	if len == 1 {
		q.Val = []*Tree{}
	} else {
		q.Val = q.Val[1:]
	}
	return node
}

func (q *Queue) Len() int {
	q.Length = len(q.Val)
	return q.Length
}

func levelorder(t *Tree) {
	queue := Queue{}
	queue.Push(root)

	for queue.Len() > 0 {
		node := queue.Pop()
		if node == nil {
			panic("node is nil")
		}

		if node.IsRoot {
			fmt.Printf("%d, ", node.Val)
		}

		if node.Left != nil {
			fmt.Printf("%d, ", node.Left.Val)
			queue.Push(node.Left)
		}

		if node.Right != nil {
			fmt.Printf("%d, ", node.Right.Val)
			queue.Push(node.Right)
		}
	}
}