[算法] 二叉树的前中后层序遍历（递归、非递归Golang实现）

[算法] 二叉树的前中后层序遍历（递归、非递归Golang实现）

简介

种类

• 基于递归的前序, 中序, 后续 遍历(3种)
• 基于栈的前序, 中序, 后续遍历(3种)
• 基于队列的层序遍历(3种)

{8,6,5,7,10,9,11}{5,6,7,8,9,10,11}{5,7,6,9,11,10,8}{8,6,10,5,7,9,11}

递归的前序/中序/后续 遍历

树节点的定义如下

type BTree struct {
	value int
	left  *BTree
	right *BTree
}

前序遍历(递归)

//递归前序遍历
func PreOrderByTraversal(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	preOrderByTraversal(root, &path)
	return path
}
func preOrderByTraversal(root *BTree, path *[]int) {
	if root == nil {
		return
	}
	*path = append(*path, root.value)
	if root.left != nil {
		preOrderByTraversal(root.left, path)
	}
	if root.right != nil {
		preOrderByTraversal(root.right, path)
	}
}

中序遍历(递归)

//递归中序遍历
func InnerOrderByTraversal(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	innerOrderByTraversal(root, path)
	return path
}
func innerOrderByTraversal(root *BTree, path []int) {
	if root == nil {
		return
	}
	if root.left != nil {
		innerOrderByTraversal(root.left, path)
	}
	path = append(path, root.value)
	if root.right != nil {
		innerOrderByTraversal(root.right, path)
	}
}

后序遍历(递归)

//递归后序遍历
func PostOrderByTraversal(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	postOrderByTraversal(root, path)
	return path
}
func postOrderByTraversal(root *BTree, path []int) {
	if root == nil {
		return
	}
	if root.left != nil {
		postOrderByTraversal(root.left, path)
	}
	path = append(path, root.value)
	if root.right != nil {
		postOrderByTraversal(root.right, path)
	}
}

基于栈的前序/中序/后序遍历

前序遍历(栈)

步骤	操作	stack	输出
1	root 节点入栈	8
2	stack.Pop() 并输出临时节点 temp 8	8
3	temp.right 入栈 10	10
4	temp.left 入栈 6	10 6
5	stack.Pop() 并输出临时节点 temp 6	10	6
6	temp.right 入栈 7	10 7
7	temp.left 入栈 5	10 7 5
8	stack.Pop() 并输出临时节点 temp 5	10 7	5
9	temp 5 没有左子树和右子树放弃操作
10	stack.Pop() 并输出临时节点 temp 7	10	7
11	temp 7 没有左子树和右子树放弃操作
12	stack.Pop() 并输出临时节点 temp 10	10
13	temp.right 入栈 11	11
14	temp.right 入栈 9	11 9
15	stack.Pop() 并输出临时节点 temp 9	11	9
16	temp 9 没有左子树和右子树放弃操作
17	stack.Pop() 并输出临时节点 temp 11	11
18	temp 11 没有左子树和右子树放弃操作
19	stack 为空退出循环

golang 代码

	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]*BTree, 0)
	mStack := stack.NewStack()
	mStack.Push(root)
	node := root
	for {
		if mStack.IsEmpty() {
			break
		}
		node = mStack.Pop().(*BTree)
		path = append(path, node)
		//注意这里先入栈右子树
		if node.right != nil {
			mStack.Push(node.right)
		}
		if node.left != nil {
			mStack.Push(node.left)
		}

	}
	return
}

中序遍历(栈)

中序遍历是: 找到最左的左子树, 返回父节点, 遍历右子树

golang 代码

func innerOrderByStack(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	mStack := stack.NewStack()
	node := root
	for !mStack.IsEmpty() || node != nil {
		//一直将左子树遍历到底部
		for node != nil {
			mStack.Push(node)
			node = node.left
		}
		temp := mStack.Pop().(*BTree)
		path = append(path, temp.value)
		node = temp.right
	}
	return
}

后序遍历(栈)

栈的后续遍历有点比前面的复杂一点, 正确的输出是

{5, 7, 6, 9, 11, 10, 8}

左子树->右子树->根节点根节点->右子树->左子树根节点->左子树->右子树根节点->右子树->左子树

golang 代码

func postOrderByStack(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	pathList := list.New()
	mStack := stack.NewStack()
	mStack.Push(root)
	for !mStack.IsEmpty() {
		node := mStack.Pop().(*BTree)
		pathList.PushFront(node.value)
		if node.left != nil {
			mStack.Push(node.left)
		}
		//注意这里先入栈右子树
		if node.right != nil {
			mStack.Push(node.right)
		}
	}
	path = make([]int, 0)
	element := pathList.Front()
	for element != nil {
		path = append(path, element.Value.(int))
		element = element.Next()
	}
	return path
}

基于队列的层序遍历

golang 代码

//基于队列的层序遍历
func LevelOrder(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	mQueue := queue.NewQueue()
	mQueue.Push(root)
	for !mQueue.IsEmpty() {
		temp := mQueue.Pop().(*BTree)
		path = append(path, temp.value)
		if temp.left != nil {
			mQueue.Push(temp.left)
		}
		if temp.right != nil {
			mQueue.Push(temp.right)
		}
	}
	return path
}

测试

package main

import (
	"container/list"
	"fmt"
	"testing"

	"github.com/dengjiawen8955/gostl/ds/queue"
	"github.com/dengjiawen8955/gostl/ds/stack"
)

func TestP25_2(t *testing.T) {
	a8 := &BTree{value: 8}
	a6 := &BTree{value: 6}
	a10 := &BTree{value: 10}
	a5 := &BTree{value: 5}
	a7 := &BTree{value: 7}
	a9 := &BTree{value: 9}
	a11 := &BTree{value: 11}
	a8.left = a6
	a8.right = a10
	a6.left = a5
	a6.right = a7
	a10.left = a9
	a10.right = a11
	var bs []int
	//前序遍历
	bs = PreOrderByTraversal(a8)
	fmt.Printf("PreOrderByTraversal=%#v\n", bs)
	bs = PreOrderByStack(a8)
	fmt.Printf("PreOrderByStack=%#v\n", bs)
	fmt.Printf("%s\n", "")
	//中序遍历
	bs = InnerOrderByTraversal(a8)
	fmt.Printf("InnerOrderByTraversal=%#v\n", bs)
	bs = InnerOrderByStack(a8)
	fmt.Printf("InnerOrderByStack=%#v\n", bs)
	fmt.Printf("%s\n", "")
	//后序遍历
	bs = PostOrderByTraversal(a8)
	fmt.Printf("PostOrderByTraversal=%#v\n", bs)

	bs = PostOrderByStack(a8)
	fmt.Printf("PostOrderByStack=%#v\n", bs)
	fmt.Printf("%s\n", "")
	//层序遍历
	bs = LevelOrder(a8)
	fmt.Printf("LevelOrder=%#v\n", bs)
}

//递归前序遍历
func PreOrderByTraversal(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	preOrderByTraversal(root, &path)
	return path
}
func preOrderByTraversal(root *BTree, path *[]int) {
	if root == nil {
		return
	}
	*path = append(*path, root.value)
	if root.left != nil {
		preOrderByTraversal(root.left, path)
	}
	if root.right != nil {
		preOrderByTraversal(root.right, path)
	}
}

//递归中序遍历
func InnerOrderByTraversal(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	innerOrderByTraversal(root, path)
	return path
}
func innerOrderByTraversal(root *BTree, path []int) {
	if root == nil {
		return
	}
	if root.left != nil {
		innerOrderByTraversal(root.left, path)
	}
	path = append(path, root.value)
	if root.right != nil {
		innerOrderByTraversal(root.right, path)
	}
}

//递归后序遍历
func PostOrderByTraversal(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	postOrderByTraversal(root, path)
	return path
}
func postOrderByTraversal(root *BTree, path []int) {
	if root == nil {
		return
	}
	if root.left != nil {
		postOrderByTraversal(root.left, path)
	}
	path = append(path, root.value)
	if root.right != nil {
		postOrderByTraversal(root.right, path)
	}
}

//基于栈的前序遍历
func PreOrderByStack(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	mStack := stack.NewStack()
	mStack.Push(root)
	for !mStack.IsEmpty() {
		node := mStack.Pop().(*BTree)
		path = append(path, node.value)
		//注意这里先入栈右子树
		if node.right != nil {
			mStack.Push(node.right)
		}
		if node.left != nil {
			mStack.Push(node.left)
		}
	}
	return
}

//基于栈的中序遍历
func InnerOrderByStack(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	mStack := stack.NewStack()
	node := root
	for !mStack.IsEmpty() || node != nil {
		//一直将左子树遍历到底部
		for node != nil {
			mStack.Push(node)
			node = node.left
		}
		temp := mStack.Pop().(*BTree)
		path = append(path, temp.value)
		node = temp.right
	}
	return
}

// 5  7  6  9 11 10 8  后序
// 8 10 11 9  6  7  5 后序的逆
//基于栈的后序遍历
func PostOrderByStack(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	pathList := list.New()
	mStack := stack.NewStack()
	mStack.Push(root)
	for !mStack.IsEmpty() {
		node := mStack.Pop().(*BTree)
		pathList.PushFront(node.value)
		if node.left != nil {
			mStack.Push(node.left)
		}
		//注意这里先入栈右子树
		if node.right != nil {
			mStack.Push(node.right)
		}
	}
	path = make([]int, 0)
	element := pathList.Front()
	for element != nil {
		path = append(path, element.Value.(int))
		element = element.Next()
	}
	return path
}

//基于队列的层序遍历
func LevelOrder(root *BTree) (path []int) {
	if root == nil {
		fmt.Printf("%s\n", "err: root is nil")
		return nil
	}
	path = make([]int, 0)
	mQueue := queue.NewQueue()
	mQueue.Push(root)
	for !mQueue.IsEmpty() {
		temp := mQueue.Pop().(*BTree)
		path = append(path, temp.value)
		if temp.left != nil {
			mQueue.Push(temp.left)
		}
		if temp.right != nil {
			mQueue.Push(temp.right)
		}
	}
	return path
}

debug

PreOrderByTraversal=[]int{8, 6, 5, 7, 10, 9, 11}
PreOrderByStack=[]int{8, 6, 5, 7, 10, 9, 11}

InnerOrderByTraversal=[]int{}
InnerOrderByStack=[]int{5, 6, 7, 8, 9, 10, 11}

PostOrderByTraversal=[]int{}
PostOrderByStack=[]int{5, 7, 6, 9, 11, 10, 8}

LevelOrder=[]int{8, 6, 10, 5, 7, 9, 11}
PASS

reference