二叉树前序、中序和后序遍历

二叉树(binary tree)有三种常见的遍历方式

  • 前序遍历(preorder traversal): VLR

    先访问树的根节点,然后使用前序遍历递归地访问根节点的左子树,最后使用前序遍历递归地访问根节点的右子树

  • 中序遍历(inorder traversal): LVR

    先使用中序遍历递归地访问根节点的左子树,然后访问根节点,最后使用中序遍历递归地访问根节点的右子树

  • 后序遍历(postorder traversal): LRV

    先使用后序遍历递归地访问根节点的左子树,然后使用后序遍历递归地访问根节点的左子树,最后访问根节点

这三种访问方式都是深度优先搜索(deep first search, DFS): 沿着某个方向一直访问节点,当到了根节点时(无法继续访问节点),就返回到某个合适的节点继续沿着该固定方向访问。

下面二叉树的前序遍历VLR为:[0,1,3,4,2,5,6]

From http://mishadoff.com/blog/dfs-on-binary-tree-array/

本文用递归和非递归方式实现三种不同的遍历,完整代码见binary tree and its traverse


构造树

1
2
3
4
5
6
7
8
9
10
11
# 定义节点
class node(object):
def __init__(self,val=None):
self.left = None
self.right = None
self.val = val
# 定义上图中的树
r = node(0)
r.left, r.right = node(1),node(2)
r.left.left, r.left.right = node(3),node(4)
r.right.left,r.right.right = node(5),node(6)


递归方式

将遍历方式定义为一个函数,然后根据不同遍历的定义写代码。

比如前序遍历VLR用preorderTraverse(root)表示。那么

可以表示为

1
2
3
4
def preorderTraverse(root):
访问root的值
preorderTraverse(root.left) #前序遍历左子树
preorderTraverse(root.right) #前序遍历右子树

前序遍历VLR

1
2
3
4
5
6
7
8
9
10
11
def preorderTraverse(r):
if r is None:
return []
result = []
if r:
result += [r.val]
if r.left:
result += preorderTraverse(r.left)
if r.right:
result += preorderTraverse(r.right)
return result

输出

1
preorderTraverse(r)

Out:[3, 1, 4, 0, 5, 2, 6]

中序遍历LVR

1
2
3
4
5
6
7
8
9
10
11
def inorderTraverse(r):
if r is None:
return []
result = []
if r.left:
result += inorderTraverse(r.left)
if r:
result += [r.val]
if r.right:
result += inorderTraverse(r.right)
return result

输出

1
inorderTraverse(r)

Out:[3, 1, 4, 0, 5, 2, 6]

后序遍历LRV

1
2
3
4
5
6
7
8
9
10
11
def postorderTraverse(r):
if r is None:
return []
result = []
if r.left:
result += postorderTraverse(r.left)
if r.right:
result += postorderTraverse(r.right)
if r:
result += [r.val]
return result

输出

1
postorderTraverse(r)

Out:[3, 4, 1, 5, 6, 2, 0]


非递归方式

非递归方法比较复杂一些。

深度优先搜索(DFS)算法是一种使用回溯思想的递归算法: 它首先沿着某方向一直搜索直到无可访问节点,然后通过回溯继续访问其它节点。

这类过程适合用数据结构中的栈stack来实现。分为如下3个过程:

  1. 选择一个起始节点并将其所有相邻节点推入堆栈。
  2. 从堆栈弹出一个节点作为访问的下一个节点,并将其所有相邻节点推入堆栈。
  3. 重复此过程,直到堆栈为空。注意,需要标记或者通过逻辑防止二次访问某节点。如果程序处于无限循环中,可检查是否有标记或者逻辑错误。

前序遍历VLR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def preorderTraverse2(r):
if r is None:
return []
stack = []
result = []
node = r # 起始节点
while stack or node:
# 一直访问左子树直到根节点,同时将访问过的节点添加到stack中,
# 以便回溯时使用
while node:
result.append(node.val)
stack.append(node)
node = node.left
# 回溯
temp = stack.pop()
node = temp.right
return result

输出

1
preorderTraverse2(r)

Out:[3, 1, 4, 0, 5, 2, 6]

中序遍历LVR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def inorderTraverse2(r):
if r is None:
return []
stack = []
result = []
node = r
while stack or node:
# 先走到最左的根节点
while node:
stack.append(node)
node = node.left
# 然后开始访问节点的值
temp = stack.pop()
result.append(temp.val)
node = temp.right
return result

输出

1
inorderTraverse2(r)

Out:[3, 1, 4, 0, 5, 2, 6]

后序遍历LRV

将后序遍历LRV,看做VRL的逆。
所以,先对做VRL遍历,然后翻转节点列表,得到后序遍历列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def postorderTraverse2(r):
if r is None:
return []
stack = []
result = []
node = r
# VRL
while stack or node:
while node:
result.append(node.val)
stack.append(node)
node = node.right
temp = stack.pop()
node = temp.left
# reverse VRL to get LRV
result = result[::-1]
return result

输出

1
postorderTraverse2(r)

Out:[3, 4, 1, 5, 6, 2, 0]


参考

  1. Problem Solving with Algorithms and Data Structures-6.7. Tree Traversals
  2. DFS on Binary Tree Array
  3. Depth First Search