Tree order Traversal 的 4 種方式：Inorder, Preorder, Postorder, Level order
看完田神老師的 Data Structure and Algorithm 關於 Binary Tree Traversal 的部分，搭配上 Leetcode 刷題的心得，這邊稍微整理一下關於 Tree 的 Traversal 方式
名詞定義：
pre, in, post 的定義以 root 的位置為標準
- Pre: root 順序在前面
root → root.left → root.right
中 → 左 → 右
- In: root 順序在中間
root.left → root → root.right
左 → 中 → 右
- Post: root 順序在後面
root.left → root.right → root
左 → 右 → 中
- Level: 按照層級來看 root
Preorder
pseudo code
def preorder_traversal(tree_node):
if tree_node is null:
return
else:
# 中
action with tree_node.data
# 左
inorder_traversal(tree_node.left)
# 右
inorder_traversal(tree_node.right)
應用時機
- 比較兩棵樹是否相同：按照順序拜訪兩棵樹，先從 root 開始比，root 一樣才繼續看 left subtree 與 right subtree，所以是中 → 左 → 右的順序
- 將一個資料夾 copy 到另一個地方時，比較兩個資料是否相同
- 先看中間，得到 A，再看左邊，再看右邊
A -> Left Subtree
- Left Subtree 先看中間，得到 B: A -> B
再看左邊，得到 Left Subtree
- 先看中間，得到 D: A -> B -> D
- 再看左邊，null 跳過
- 再看右邊，得到 G: A -> B -> D -> G
- 此時 root 為 B 層的 Left Subtree 都做完了，所以回到 root 為 B 層的 Right Subtree，得到 E: A -> B -> D -> G -> E
- 此時 root 為 A 層的 Left Subtree 都做完了，所以回到 root 為 A 層的 Right Subtree
- 先看中間得到 C: A -> B -> D -> G -> E -> C
- 再看 Left Subtree 中間得到 F: A -> B -> D -> G -> E -> C -> F
- 再看 Left Subtree 得到 H: A -> B -> D -> G -> E -> C -> F -> H
- 再看 Right Subtree 得到 I: A -> B -> D -> G -> E -> C -> F -> H -> I
- 此時 root 為 C 層的 Left Subtree 都做完了，所以回到 root 為 C 層的 Right Subtree
- Right Subtree 為 null 因此答案及為A -> B -> D -> G -> E -> C -> F -> H -> I
Leetcode
Inorder traversal
pseudo code
def inorder_traversal(tree_node):
if tree_node is null:
return
else:
# 左
inorder_traversal(tree_node.left)
# 中
action with tree_node.data
# 右
inorder_traversal(tree_node.right)
應用時機
輸出 Infix Expression 的時候
Expression Tree
要將 Expression Tree 輸出成人類看得懂的四則運算:
3 * 4 - (5 + 6) * 7 + 8 * 9
就要先左邊，再中間，再右邊地去讀這棵 Tree，如下圖
再把 Left Subtree 拆出來，先左邊，再中間，再右邊地去讀這棵 Left Subtree，如下圖
再把 Left Subtree 拆出來，先左邊，再中間，再右邊地去讀這棵 Left Subtree，如下圖
再把 Left Subtree 拆出來，先左邊，再中間，再右邊地去讀這棵 Left Subtree，如下圖
因為 Left 為 Null，沒有 Left Subtree 了，所以換處理中間的 node data，可以取得 3，Right Subtree 也為 Null，
因此這裡為左邊的末端值，return 3
接著 return 中間值 *
最後 return 右邊值 4
因此可以得到 3 * 4
因此這裡為左邊的末端值，return 3
接著 return 中間值 *
最後 return 右邊值 4
因此可以得到 3 * 4
依此類推，可以把整顆 Expression Tree 表達成人類看得懂的 Infix 四則運算式
Leetcode
結合 preorder 與 inorder
Postorder
pseudo code
def postorder_traversal(tree_node):
if tree_node is null:
return
else:
# 左
inorder_traversal(tree_node.left)
# 右
inorder_traversal(tree_node.right)
# 中
action with tree_node.data
應用時機
要算出 Expression Tree 的值的時候
因為要先取數字，所以要先取左，取右，最後才取運算子
- 先取 Left Subtree 得到 value 3: 3
- 再取 Right Subtree 得到 value 4: 3 4
- 最後取 node data 得到 operator *: 3 4 *
- 就可以算出 3 * 4 = 12
Level order
與前三者不同，要拜訪完同一層的 node，再拜訪下一層
pseudo code
def level_order_traversal(tree_node):
if tree_node is null:
return
else:
先將 root 放入一個: q = deque([root])
level 從 0 開始: level = 0
當 queue 裡面有東西的時候，就按照順序把同時存在 queue 裡的 node 拿出來
同時存在代表同一層，全部看完後才進入下一層
while q:
用 for loop + 此時 queue 的長度，將此時存在 queue 裡的 node 都拿出來
拿出來後看此 node 的 left and right 是否存在，存在則加到 queue 的後面
for i in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
for loop 跑完後 level 要 + 1
level += 1
此時 queue 裡如果有新加入的 left or right， while 迴圈繼續
return level
應用時機
- 與 Preorder Traversal 相同，可以比對資料相同性
Leetcode
此 Tree 的
- preorder
- inorder
- postorder
- level order
Traversal 分別為什麼？
對答案：
- ABDGECFHI
- DGBEAHFIC
- GDEBHIFCA
- ABCDEFGHI
Comments
Post a Comment