基礎演算法系列 — Tree 樹狀資料結構
在資料結構中，「Tree」與「Graph」是兩個重要的資料結構，許多實務上系統的應用與開發，底層都跟他們脫不了關係，像是資料儲存、HTML DOM Tree 或甚至是組織架構圖都會用到 Tree 的概念。本篇筆記以 Tree 為主題，紀錄一下常見最基本的幾種 Tree，以及經典的 BFS 與 DFS 兩種演算法。
Tree 的基本概念
廣義的 Tree 這種資料結構，其實可以算是一種非封閉性的 Graph。
特性
- 由一個根節點(root) 與多個子節點(child node) 所組成
- 每個 node 的節點數量稱做 degree ，可以有多個子節點
- 每個 node 會記錄他的子節點是誰與在節點上儲存的資料
- 每個 node 只能有一個父節點
- 每一條分支都可以看作一條 Linked List
- 沒有子節點的 node 又稱作為 leaf node
- 樹裡面沒有環路(cycle)
Binary Tree (二元樹)
如果把剛剛的 Tree，限制每一個 node 最多只能有兩個子節點，這時候就可以稱作為 Binary Tree 二元樹。
特性
- 每一個 node 最多只能有兩個子節點
- 子節點有左右之分 (left node, right node)
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}Binary Search Tree (二元搜尋樹)
如果我們再把訂定更多條件，他會成為一個方便搜索的 Binary Search Tree 二元搜尋樹也可以稱為有序二元樹。
特性
- 左子樹上所有節點的值均小於它的根節點的值
- 右子樹上所有節點的值均大於它的根節點的值
- 任意節點的左、右子樹也分別為二元搜尋樹
- 不會出現有重複值的節點
從上圖簡單的 Binary Search Tree 可以看出，如果要搜尋某一個數值的時候，和 Binary Search 一樣的概念，我們可以先從 root 看這個 target 是大於還是小於 root 的值，如此一來可以大大減低搜尋的時間。
其他幾種 Binary Tree
- Full Binary Tree: 除了 leaf node 之外的所有 node 都有 child node。
- Complete Binary Tree: 除了最後一層之外各層節點都是全滿，最後一層節點都靠左。
- Perfect Binary Tree: 符合 Full Binary Tree 與 Complete Binary Tree，也就是所有各層的節點都必須是滿的。
Traversal 遍歷
在 Graph 與 Tree 的資料結構中，如何遍歷所有的點，是最重要的議題之一，這裡就以 Binary Tree 來看看 Traversal 一棵樹的方式。
Binary Tree Traversal
二元樹有幾種遍歷(Traversal)的方式：
- Pre-order 前序：root → left → right
- In-order 中序：left → root → right
- Post-order 後序：left → right → root
- Level-order 層序：一層一層從左至右
記憶法：pre, in, post 主要是 root 被查找的位置，其餘從左至右
用剛剛上面介紹過的這棵二元樹，我們可以找出他四種遍歷方式的結果：
- Pre-order 前序：ABDECFG
- In-order 中序：DBEAFCG
- Post-order 後序：DEBFGCA
- Level-order 層序：ABCDEFG
Depth-First Search (DFS, 深度優先搜尋)
DFS，就是一般大家常說的深度優先搜尋，核心的邏輯就如同剛剛介紹的 Pre-order，先往第一個節點的最深處走，再去找相鄰的點，如果該節點的邊上每一個節點都走過，則回到上一個點(backtracking)，繼續去找其他還沒走過的點。
以剛剛的二元樹來看：
- 一開始會從 A → B → D 走到第一個節點的最深處
- Backtracking 回 B，接著走第二個點 E
- Backtracking 回 B，再一次的 backtracking 回 A
- 往 C 的方向開始做一樣的邏輯
- 結果：A → B → D → E → C → F → G
實作的話通常可以用比較直覺的遞迴方式，或是利用 Stack 的 FILO (First-in-Last-out) 特性來達成 DFS。
先定義 node 的長相為：
DFS in recursive
DFS in stack
DFS in stack 思考上沒有用 recursive 來的那麼直覺，主要是利用 Stack 的特性，把 right node 比 left node 先 push 到 stack 裡面來，這樣子當要讀取的時候，就會因為 FILO 的原因，會先讀取後放進來的 Left node 了，以下圖解一下 DFS in stack：
Breadth-First Search (BFS, 廣度優先搜尋)
BFS 則是廣度優先，也就是剛剛提到的 Level-order 層序搜尋的方式，把每一層的所有節點從左到右都走過一遍，才會往下一層接著去做一樣的邏輯，直到所有的節點都走完。
以剛剛的二元樹來看：
- 第一層 A，接著往下一層
- 第二層 B → C，都走完後再往下一層
- 最後可以找到：A → B → C → D → E → F → G
BFS 可以利用 queue 的特性來實作：
Notes: shift() 方法會移除並回傳陣列的第一個元素。此方法會改變陣列的長度。
Tree on the Leetcode
如果實際想找幾題 Tree 的題目來試試看的話，以下有幾題 Leetcode 上蠻基本的題目，可以當作複習練手感用。
94. Binary Tree Inorder Traversal
- 題目：最基本的 In-order traversal
- 概念：這題蠻簡單，從 DFS 演算法來改動一點點就可以達成了
- https://leetcode.com/problems/binary-tree-inorder-traversal/
98. Validate Binary Search Tree
- 題目：驗證是否為一個 Binary Search Tree，也就是要符合：左子節點 < 父節點 < 右子節點
- 概念：這題可以從 #94 題的方向下去想，剛剛前面有提到 In-order：left → root → right，這順序剛好符合 Binary Search Tree 要的左子節點 < 父節點 < 右子節點，因此只需要用 in-order 遍歷出來後，去看看是不是有從小排到大，就可以驗證是不是一個 Binary Search Tree 囉！
- https://leetcode.com/problems/validate-binary-search-tree/
其他更多相關題目：
Tree — DFS
- https://leetcode.com/problems/maximum-depth-of-binary-tree/
- https://leetcode.com/problems/leaf-similar-trees/description/
Tree — BFS
如果你覺得這篇文章對你有幫助，歡迎買杯咖啡贊助 ☕️ 謝謝
