初學紀錄 - Tree

• 樹狀圖

• 學跟 Tree 有關的演算法之前要先認識 Graph 這結構

Graph 定義

• abstract data type

• 包含 finite set (nodes 跟 points)

• 點跟點相連的線 edges

Tree 定義

1. tree is a graph without a loop

2. one and only one root

• 不能出現兩個 root

滿足上面兩點就是 tree

有用到 Tree 的應用：

1. DOM(Document Object Model)

2. 文件存放位置的資料(File System)

3. Artificial Intelligence

Tree Traversal

有系統性地把在 Tree 裡面的 nodes 給找出來。

tree Traversal 最主要的兩種做法

1. Breadth-First Tree Traveral

2. Depth-First Tree Traversal

   1. PreOrder

   2. InOrder

   3. PostOrder

Breadth-First Tree Traveral(BFS)

Breadth 是寬度的意思，這個詞指的是寬度優先。

作法：從 root 開始，先走訪同一層的所有節點，再往下一層。

實作方式：使用 Queue

應用情境：

• 找最短路徑（例如迷宮、網路路由）

• 層級遍歷（level-order traversal），適合輸出「每一層」的資料

     A
    / \
   B   C
  / \   \
 D   E   F

BFS → A, B, C, D, E, F

Breadth-First Tree Traveral(DFS)

深度優先。

意義是先一直往下鑽到底，再回頭。

如果是 PreOrder：

理解方式： root, left, right。

每個 subtrees 都要做 root, left, right。

如果是 InOrder：

理解方式：left, root, right。

如果是：PostOrder：

理解方式：left, right, root

整理一下就是做法如下：

• PreOrder → Root → Left → Right

• InOrder → Left → Root → Right （在 BST 會輸出排序結果）

• PostOrder → Left → Right → Root

實作方式：通常用 Recursion（遞迴），也可用 Stack

應用情境：

• 適合處理「需要完整訪問所有節點」的情況

• 用於計算樹的大小、結構轉換、表達式運算 (Expression Tree)

     A
    / \
   B   C
  / \   \
 D   E   F

DFS (PreOrder) → A, B, D, E, C, F

Binart Search Tree( aka BST)

• 每個 node 最多兩個 children 在一個 tree 裡面

• 跟 binary tree 一樣只是更嚴格，left child 要總是小於 root，right child 要大於 root

小結

• Tree 是一種沒有環的 Graph，且只有一個 root。

1. Binary Search Tree 讓搜尋更快（平均 O(log n)）。

2. Traversal 的不同方式在不同情境會有不同應用：

   • InOrder 在 BST 中能得到排序資料。

   • BFS 常用在找「最短路徑」或「逐層分析」。

   • PostOrder 適合處理刪除或釋放記憶體的情境。