Tree

應用場合

  1. [電腦的] 資料夾裡面有資料夾, 它裡面又有更多資料夾 ...
  2. phylogenetic tree: 黑猩猩 (chimpanzee) 與侏儒黑猩猩 (bonobo 又稱 pygmy chimpanzee) 在三百五十萬年前有共同的祖先; 他們與人類在七百萬年前有共同的祖先; 這三種物種在一千萬年前與大猩猩 (gorilla) 又有共同的祖先; ...
  3. 學校分成幾個學院/處/室, 學院又分成幾個系, 系裡面分幾個組, ...
  4. 臺中縣有好幾個鄉鎮市, 霧峰鄉裡面有分成好幾個村, 每個村裡面有好幾戶人家...
  5. expression tree

這類觀念, 都可以畫成一棵 tree 樹 來表示。 樹由 node 節點 (例如每個資料夾; 每個物種; 每個單位; 每個行政區域) 與 edge 邊 所構成。 nodes 是主角; edges 用來描述 nodes 之間的關係, 例如 "...資料夾內含有...", "...物種產生...物種", "...單位包含...單位", "...行政區域包含...行政區域",

基本名詞

彼此之間有直接包含/產生/...關係的兩 nodes, 稱為 parent node 父節點 與 child node 子節點, 例如朝陽科大是資訊學院的 parent node; 資訊學院是朝陽科大的 child node。 沒有 parent node 的那個 node (一定有, 且只有一個, 否則不叫做樹), 叫做 root 樹根。 例如根目錄 (沒有其他資料夾包含它); 最原始的巨猿祖先 (假設文中只討論巨猿, 沒有其他物種產生它); 朝陽科大 (假設文中沒有談到教育部等更上級單位)...。 沒有 child node 的 node, 叫做一個 leaf node, 也叫做 external node 例如 ...; 有 child node 的 node, 叫做一個 internal node。 如果有兩個 nodes 具有相同的 parent nodes, 則稱此二 nodes 互為 sibling nodes, 例如資訊學院與管理學院互為 sibling nodes。 "Parent" 的關係重複數次, 稱為 ancestor, 例如朝陽科大與資訊學院都是資管系的 ancestors。 甚至資管系也是自己的 ancestor! (重複零次) 至少一層的 parent 關係, 稱為 proper ancestor, 例如朝陽科大與資訊學院都是資管系的 proper ancestors; 但資管系不是資管系的 proper ancestor。 同樣地, child 關係重複數次, 稱為 descendent; 至少一層的 child 關係, 稱為 proper descendent。 例如朝陽科大, 資訊學院, 與資管系都是朝陽科大的 descendents; 但是只有後二者是 proper descendents。 ...subtree...

一串兩兩相鄰的 nodes 依序列出, 稱為一個 path。 一條 path 上面如果有 k 個 nodes, 就有 k-1 條 edges, 而它的 path length 長度 則記為 k-1。 一個 node, 從 root 走到它的 (唯一) path 的長度, 稱為它的 depth, 也稱為 level; 從它走到它最遠的 descendent 的 path 長度, 稱為它的 height。 一棵 tree 的 height, 定義為它的 root 的 height。

Binary Tree

Tree 上面的一個 node x, 它的 children 的個數, 稱為它的 out degree。 所以 leaves 正好也就是那些 out degree 為 0 的 nodes。 一棵 tree 裡面, 如果每一個 node 的 out degree 都不超過 n, 就稱此 tree 為一棵 n-ary tree。 n=3 時, 特別又稱為 ternary tree; n=2 時, 特別又稱為 binary tree, 資訊科學當中最常用到這類樹。

一棵高度為 k 的 binary tree 如果 level 0 恰有 1 個 node, level 1 恰有 2 個 nodes, ... level k-1 恰有 2^(k-1) 個 nodes, 而最下一層也就是第 k 層的所有 nodes 都盡量擠在最左邊, 則稱為一棵 complete binary tree。

一棵 binary tree, 如果所有的 internal nodes 的 out degree 都是 2, 且所有的 external nodes 都在同一 level, 則稱為一棵 full binary tree。 顯然, full binary tree 必然是 complete binary tree; 反之不然。

為什麼我們對 complete binary tree 有興趣呢? 原因之一是它的高度 h 與 node 個數 n 之間, 有著簡單的關係: 2^h <= n < 2^(h+1) 如果用 asymptotic notation 來描述, n 屬於 Theta(2^h) 也可以說 h 屬於 Theta(lg n)。 重點是: 這樣的樹不必長得很高, 就可以容納很多的 nodes。

Tree Traversal

逐一走訪一棵 tree 的每一個 node, 這個動作叫做 tree traversal。 如果走訪過程當中, 按照走訪順序為每一個 node 編號, 當然不同的走訪順序, 會產生不同的編號方式。 例如最先走訪 level 0 的 node -- 只有 root 一個, 並列為 1 號; 其次由左而右依序走訪 level 1 內的所有 nodes 並依序列為 2 號, 3 號, ...; 再次由左而右依序走訪 level 2 內的所有 nodes; ... 這樣的走訪方式, 稱為 level order traversal, 是 breadth first search 的一種。 (不同的 BFS 在同一層內可能採用不同的順序, 未必像 level order traversal 要求一定要由左而右。)

如果用 遞迴 的方式進行 traversal, 則得到 depth first search 類的 traversal。 "要走訪所有 nodes? 基本上只有三件事要做: 走訪 left, 走訪 right, 走訪 root... (待續)

BFS: 長幼有序, 第一代走完, 才輪到第二代; 第二代全部走完, 才輪到第三代; ... (連戰和宋楚瑜每個人至少要做過一任總統, 馬英九才有機會 ;-) DFS: 衝! 衝! 衝! 一路衝到底, 直到無路可走, 才退回去。 沒有好壞對錯的問題, 只是兩類不同的演算法。