【golang】二叉树的遍历

本文使用golang实现二叉树的遍历，包含以下7种方法。

• 深度优先遍历
  • 先序遍历
    • 递归法
    • 非递归法
  • 中序遍历
    • 递归法
    • 非递归法
  • 后序遍历
    • 递归法
    • 非递归法
• 广度优先遍历

二叉树节点定义：

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}
1
2
3
4
5

深度优先遍历

先序遍历

定义：
1） 访问根节点；
2） 先序遍历左子树；
3） 先序遍历右子树。

递归实现

func preorder(root *Node, consume func(*Node)) {
	if root == nil {
		return
	}
	consume(root)
	preorder(root.Left, consume)
	preorder(root.Right, consume)
}
1
2
3
4
5
6
7
8

非递归实现
思路：使用一个栈实现
1）将根节点压入栈；
2）栈中弹出一个节点，访问该节点；
3）将该节点的右孩子、左孩子依次压入栈；
4）重复步骤2~3直至完成步骤3时栈为空。

栈实现：

type Stack struct {
	values []*Node
}

func (s *Stack) Push(node *Node) {
	if s.values == nil {
		s.values = make([]*Node, 0)
	}
	s.values = append(s.values, node)
}

func (s *Stack) Pop() *Node {
	sl := len(s.values)
	if sl <= 0 {
		return nil
	}
	node := s.values[sl-1]
	s.values = s.values[:sl-1]
	return node
}

func (s *Stack) IsEmpty() bool {
	return len(s.values) == 0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func preorder(root *Node, consume func(*Node)) {
	if root == nil {
		return
	}
	stack := Stack{}
	stack.Push(root)
	for node := stack.Pop(); node != nil; node = stack.Pop() {
		consume(node)
		if node.Right != nil {
			stack.Push(node.Right)
		}
		if node.Left != nil {
			stack.Push(node.Left)
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

中序遍历

定义：
1） 中序遍历左子树；
2） 访问根节点；
3） 中序遍历右子树。

递归实现

func inorder(root *Node, consume func(*Node)) {
	if root == nil {
		return
	}
	inorder(root.Left, consume)
	consume(root)
	inorder(root.Right, consume)
}
1
2
3
4
5
6
7
8

非递归实现
思路：使用一个栈实现
1） 将根节点及其所有直系左孩子压入栈（直系左孩子：其父节点也是左孩子）；
2） 栈弹出一个节点，访问该节点；
3） 若弹出的节点有右孩子，则将右孩子视为根节点执行步骤1；
4） 重复步骤2~3，直至栈为空。

func inorder(root *Node, consume func(*Node)) {
	if root == nil {
		return
	}
	stack := Stack{}
	pushAllLeft(root, &stack)
	for !stack.IsEmpty() {
		node := stack.Pop()
		consume(node)
		if node.Right != nil {
			pushAllLeft(node.Right, &stack)
		}
	}
}

func pushAllLeft(root *Node, stack *Stack) {
	for node := root; node != nil; node = node.Left {
		stack.Push(node)
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

后序遍历

定义：
1） 后序遍历左子树；
2） 后序遍历右子树；
3） 访问根节点。

递归实现

func postorder(root *Node, consume func(*Node)) {
	if root == nil {
		return
	}
	postorder(root.Left, consume)
	postorder(root.Right, consume)
	consume(root)
}
1
2
3
4
5
6
7
8

非递归实现
思路：使用2个栈实现
1） 将根节点压入栈1；
2） 栈1弹出一个节点，将其左孩子、右孩子依次压入栈1；
3） 将步骤2弹出的节点压入栈2；
4） 重复步骤2~3，直至执行完步骤3时栈1为空；
5） 栈2弹出一个节点，并访问该节点；
6） 重复步骤5，直至栈2为空。

func postorder(root *Node, consume func(*Node)) {
	if root == nil {
		return
	}
	stack1 := Stack{}
	stack2 := Stack{}
	stack1.Push(root)
	for !stack1.IsEmpty() {
		node := stack1.Pop()
		stack2.Push(node)
		if node.Left != nil {
			stack1.Push(node.Left)
		}
		if node.Right != nil {
			stack1.Push(node.Right)
		}
	}
	for !stack2.IsEmpty() {
		consume(stack2.Pop())
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

广度优先遍历

定义：按从上往下、从左往右的顺序来遍历
思路：使用一个队列实现
1） 将根节点加入队尾；
2） 从队列头取出一个节点，访问该节点；
3） 将该节点的左孩子、右孩子依次加入队尾；
4） 重复步骤2~3，直至执行完步骤3时队列为空。

func widthorder(root *Node, consume func(*Node)) {
	if root == nil {
		return
	}
	queue := make([]*Node, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		consume(node)
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18