要在一棵樹上走訪(traverse)時,可以有很多種不同的方式,但主要的方式有以下四種:

其中,若你的樹是運算樹,則前、中、後序三種走訪的結果,就是前、中、後序三種運算式(但中序式的括號需要有另外的原則補上,此篇不做相關說明)。

以基礎介紹看過的這棵樹來說,

四種走訪的順序分別如下:

而在實作上,前、中、後序三種走訪會靠遞迴來實作,而層序則需要用 queue 來實作,如下:

class TreeNode(object):
	def __init__(self, val, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right


def pre_order(root):
	if root:
		print(root.val, end=' ')
		pre_order(root.left)
		pre_order(root.right)


def in_order(root):
	if root:
		in_order(root.left)
		print(root.val, end=' ')
		in_order(root.right)


def post_order(root):
	if root:
		post_order(root.left)
		post_order(root.right)
		print(root.val, end=' ')


def level_order(root):
	q = [root]
	while q:
		node = q.pop(0)
		print(node.val, end=' ')
		if node.left:
			q.append(node.left)
		if node.right:
			q.append(node.right)


# Construct
root = TreeNode('A')
b = TreeNode('B')
c = TreeNode('C')
d = TreeNode('D')
e = TreeNode('E')
f = TreeNode('F')
g = TreeNode('G')
h = TreeNode('H')
root.left = b
root.right = c
b.left = d
b.right = e
e.left = g
e.right = h
c.right = f

pre_order(root)
print()

in_order(root)
print()

post_order(root)
print()

level_order(root)
print()

反過來說,如果只知道前、中、後序三種走訪順序的其中幾種,那是否可以還原出唯一的樹來呢?很顯然的,如果只知道其中一種順序時,一般來說是無法還原出唯一的樹的。例如下面這兩棵樹的前序走訪,都是 A B C D:

下面這兩棵樹的中序走訪,則也都是 A B C D:

只知道後序走訪為 A B C D 時的狀況,在此先留給各位自行練習。而對於同時知道兩種走訪順序的狀況,如果它們是前序和後序走訪,則也無法保證還原,例如前面那一組兩棵的 left-skewed tree 和 right-skewed tree,其前序走訪都是 A B C D,而後序走訪都是 D C B A。

但在將不同節點用不同字母代表的情況下,如果你知道的是前序和中序(或者中序和後序,下同)走訪,則可以還原出一棵確定的樹。以前序走訪為 A B C D E,和中序走訪為 C B A E D 為例,首先你看了前序走訪,會知道 root 一定是 A,而用 A 把中序走訪分成兩邊,會發現節點 B 和 C 在左子樹,節點 D 和 E 在右子樹,即:

接著,對於 A 的左子樹,其前序走訪是 B C,即左子樹的 root 是 B,而用 B 把中序的 C B 切開以後,會發現 C 在左子樹,而右子樹是空的,即:

而對於 A 的右子樹,其前序走訪是 D E,即右子樹的 root 是 D,而用 D 把中序的 E D 切開以後,會發現 E 在左子樹,而右子樹是空的,即:

但若你是隨便寫下一組自以為的前序和中序走訪,則樹有可能不存在,例如前序走訪為 A B C D E,中序走訪為 C E A B D,則以 A 為 root 分割左右後,看中序走訪的左子樹應包含 C E,但這很明顯的不可能在前序走訪走出 B C,因此樹不存在。

事實上,前、中、後序三種走訪天生就跟遞迴和堆疊相對應。你可以把前序走訪當作進堆疊的順序,中序走訪當作出堆疊的順序;則若能經由堆疊操作讓這樣子的進出方式成立,樹就會存在,反之則不存在。