二叉树遍历

2021-09-26

二叉树的遍历

二叉树的遍历，主要有四种方式

先序遍历
中序遍历
后序遍历
层序遍历

实现方式有两种

递归实现
迭代实现

先序遍历

前序遍历的顺序是根节点-左子树-右子树。意思是从根节点开始，要一直访问左子树，直到没有左孩子，然后访问右子树。

前序遍历

中序遍历

中序遍历的过程是左子树-根节点-右子树

后序遍历

后序遍历的过程就是左子树-右子树-根节点

源码

准备一个二叉树

      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

下面是源码实现，有两种实现方式

递归方式
迭代方式

package main

import "fmt"

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

func NewTree() (*Tree) {
	node8 := Tree{Val: 8}
	node9 := Tree{Val: 9}
	node7 := Tree{Val: 7}
	node6 := Tree{Val: 6, Left: &node8, Right: &node9}
	node5 := Tree{Val: 5}
	node4 := Tree{Val: 4}
	node3 := Tree{Val: 3, Left: &node6, Right: &node7}
	node2 := Tree{Val: 2, Left: &node4, Right: &node5}
	root := Tree{Val: 1, Left: &node2, Right: &node3, IsRoot: true}
	return &root
}

// 递归生成一个二叉树
func NewTree2(t *Tree, depth int) {
	if depth < 3 {
		t.Left = &Tree{Val: 2 * depth}
		t.Right = &Tree{Val: 4 * depth}

		NewTree2(t.Left, depth+1)
		NewTree2(t.Right, depth+1)
	}
}

func main() {
	root := NewTree()

	//t := Tree{}
	//NewTree2(&t, 1)
	//
	//root = &t

	PreOrder(root)
	fmt.Println()

	MidOrder(root)
	fmt.Println()

	PostOrder(root)
	fmt.Println()

	LevelOrder(root)
	fmt.Println()

	LevelOrder2(root)
	fmt.Println()

	PreOrder2(root)
	fmt.Println()

	MinOrder2(root)
	fmt.Println()

	PostOrder2(root)
	fmt.Println()
}

// 前序遍历
func PreOrder(t *Tree) {
	if t == nil {
		return
	}
	fmt.Print(t.Val, " ")
	PreOrder(t.Left)
	PreOrder(t.Right)
}

// 中序遍历
func MidOrder(t *Tree) {
	if t == nil {
		return
	}
	MidOrder(t.Left)
	fmt.Print(t.Val, " ")
	MidOrder(t.Right)
}

// 后续遍历
func PostOrder(t *Tree) {
	if t == nil {
		return
	}
	PostOrder(t.Left)
	PostOrder(t.Right)
	fmt.Print(t.Val, " ")
}

// 层序遍历
func LevelOrder(t *Tree) {
	queue := []*Tree{t}

	if t == nil {
		return
	}
	// 注意此为2层循环
	for len(queue) > 0 {
		length := len(queue)
		for length > 0 {
			length--
			if queue[0].Left != nil {
				queue = append(queue, queue[0].Left)
			}
			if queue[0].Right != nil {
				queue = append(queue, queue[0].Right)
			}
			fmt.Print(queue[0].Val, " ")
			queue = queue[1:]
		}
	}
}

// 前序遍历
func PreOrder2(root *Tree) {
	queue := make([]*Tree, 0)

	for root != nil || len(queue) != 0 {
		for root != nil {
			fmt.Print(root.Val, " ")
			queue = append(queue, root)

			root = root.Left
		}

		root = queue[len(queue)-1].Right
		queue = queue[:len(queue)-1]
	}
}

// 中序遍历
func MinOrder2(root *Tree) {
	queue := make([]*Tree, 0)

	for root != nil || len(queue) != 0 {
		for root != nil {
			queue = append(queue, root)
			root = root.Left
		}

		node := queue[len(queue)-1]

		fmt.Print(node.Val, " ")
		queue = queue[:len(queue)-1]
		root = node.Right
	}
}

// 后续遍历
func PostOrder2(root *Tree) {
	queue := make([]*Tree, 0)

	var lastVisited *Tree

	for root != nil || len(queue) != 0 {
		for root != nil {
			queue = append(queue, root)
			root = root.Left
		}

		n := queue[len(queue)-1]
		if n.Right == nil || n.Right == lastVisited {
			fmt.Print(n.Val, " ")
			queue = queue[:len(queue)-1]
			lastVisited = n
		} else {
			root = n.Right
		}
	}
}

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

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

func (q *Queue) Pop() (node *Tree) {
	len := q.len

	if len == 0 {
		fmt.Println("queue is empty")
	}
	node = q.Val[0]
	if len == 1 {
		q.Val = []*Tree{}
	} else {
		q.Val = q.Val[1:]
	}
	return
}

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

// 层序遍历2
func LevelOrder2(t *Tree) {
	q := Queue{}
	q.Push(t)

	for q.Len() > 0 {
		node := q.Pop()

		if node == nil {
			panic("node is nil")
		}
		if node.IsRoot {
			fmt.Print(node.Val, " ")
		}
		if node.Left != nil {
			fmt.Print(node.Left.Val, " ")
			q.Push(node.Left)
		}
		if node.Right != nil {
			fmt.Print(node.Right.Val, " ")
			q.Push(node.Right)
		}
	}
}

参考网站

https://studygolang.com/articles/31047

https://visualgo.net/zh/heap

http://tigerb.cn/2020/04/21/go-base/tree-traverse/