基礎演算法系列 — 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/