Traverse a tree (DFS & BFS)

前言

紀錄 Tree 的用途還有 DFS 與 BFS 的概念

Tree 的用途

樹狀結構可以用在很多地方

Syntax Tree for sentence

I ate the cake

Expression

sin(3z - 7)

Abstract Syntax Tree

while x < 0
  x = x + 2
  foo(x)

Binary Search Tree (BST)

通常是左小又大，這邊放的例子是以字母(ASCII)排序

Tree 的結構

一棵樹有好幾個節點，其中的關係有

• Root (最頂端的節點)
• Ancestor (父母、祖先)
• Decendants (小孩、子孫)
• Sibling (兄弟)
• Leaf (no children)

一棵樹的高度定義為

Height: maximum depth of subtree node and farthest leaf

可以用 recursive 來計算樹的高度

Height(tree)
  if tree = null: return
  // 分別跑左子樹和右子樹，每跑一次就+1個高度，取遞迴結束最大的那一邊就是樹的高度
  return 1 + MAX(Height(tree->left), Height(tree->right))

拜訪一棵樹有兩種做法

1. Depth First
2. Breadth First

Depth First

先找leaf，再找sibling

DFS 基本上就是 recursive

Inorder 中序

left → root → right

InOrderTraversal(tree)
  if tree = null: return
  InOrderTraversal(tree.left)
  Print(tree.key)  
  InOrderTraversal(tree.right)

Pre-order 前序

root → left → right

PreOrderTraversal(tree)
  if tree = null: return
  Print(tree.key)
  PreOrderTraversal(tree.left)
  PreOrderTraversal(tree.right)

Post-order 後序

left → right → root

PostOrderTraversal(tree)
  if tree = null: return
  PostOrderTraversal(tree.left)
  PostOrderTraversal(tree.right)
  Print(tree.key)

Breadth First

level by level

先把sibling找完了才往下找

通常實作 BFS 會用 Queue 的特性來實現

LevelTraversal(tree)
  if tree = null: return
  // 先把樹的root放進Queue
  Queue q
  q.Enqueue(tree)
  // 開始BFS
  while not q.Empty():
    node ← q.Dequeue()
    Print(node)
    // 從樹的左右子樹開始First in first out 
    if node.left != null:
      q.Enqueue(node.left)
    if node.right != null:
      q.Enqueue(node.right)

以上演算法跑例圖的過程如下