[ 資料結構 小學堂 ] 樹狀結構導論 : 樹

前言 :


樹的專有名詞 :
接下來還需要了解樹的相關專有名詞, 我們將以下的樹狀圖形為範本進行說明 :

* 樹根或根節點 (Root) : 沒有父節點的節點為根節點, 如上樹的根節點為A.
* 父節點 (Parent) : 每一個節點的上層節點為父節點, 如B 的父節點為 A, G 的父節點為C.
* 子節點 (Children) : 每一個節點的下層節點為子節點, 如B 的子節點有 E 及 F, A 的子節點有 B, C, D.
* 兄弟節點 (Siblings) : 有共同父節點的節點為兄弟節點, 如 B,C,D 的父節點均為 A, 所以彼此為兄弟節點.
* 分支度 (Degree) : 子樹的個數為該節點的分支度, 如 A 的分支度為 3, B 的分支度為 2.
* 終端節點或樹葉節點 (Terminal Node) : 沒有子節點的節點, 即分支度為 0 的節點, 例如 E,F,G,H etc 均為樹葉節點.
* 非終端節點 (Non-terminal Node) : 樹葉以外的節點均為非終端節點, 及分支度不為0 的節點, 如A,B,C 均為非終端節點.
* 階層或階度 (Level) : 樹的層級, 假設樹根A 為階層一, BCD 節點為階層二, EFGHI 為階層三.
* 高度 (Height) : 樹的最大階度, 此例高度為3.
* 樹林 (Forest) : 樹林是由 n 個互斥樹的集合 (n>=0), 移去樹根即為樹林.
* 祖先 (Ancestor) 與子孫 (Decendent) : 所謂祖先是指從樹根到該節點路徑上所包含的節點, 而子孫則是在該節點子樹的任一節點, 例如E 的祖先為A, B. B 的子孫為 E,F.

二元樹簡介 :
一般樹狀結構在電腦記憶體中的儲存方式是以鏈結串列 (Linked List) 為主. 對於 n 元樹 (n-way)來說, 因為每個節點的分支度都不相同, 所以為了方便起見, 我們必須取n 為鏈結個數的最大固定長度, 然而此 n元樹十分浪費空間. 假設此n 元樹有 m個節點, 那麼此樹共用了 n*m 個鏈結欄位. 如果考慮除了樹葉節點外, 如果每個節點的分支度都是一的話, 可以得知空鏈結個數為 :
n*m-(m-1)=m*(n-1)+1;

所以得知n 元樹鏈結浪費率為 :
(m*(n-1)+1) / n*m;

當m 很大時, 可以得到以下結論 :

n=2 時, 2元樹的鏈結浪費率約為 1/2
n=3 時, 3元樹的鏈結浪費率約為 2/3
...

當 n=2 時, 它的鏈結浪費率為最低, 所以為了改進空間浪費的缺點, 我們最常使用二元樹(Binary Tree) 結構來取代樹狀結構.

二元樹定義 :
二元樹 (又稱Knuth 樹) 是一個由有限節點所組成的集合, 此集合可以是空集合, 或由一個樹根及左右兩個子樹所組成. 簡單的說, 二元樹每個節點最多只能有兩個子節點, 也就是分支度小於等於2. 至於二元樹和一般樹的不同之處, 整理如下 :

1. 樹不可以為空集合, 但是二元樹可以.
2. 樹的分支度為 d>=2, 但是二元樹的分支度為 0<=d<=2 .
3. 樹的子樹間沒有次序關係, 二元樹有.

下圖是以A 為根節點的二元樹, 且包含了以B,D 為根節點的兩顆互斥的左子樹與右子樹, 要注意的是B->C 與 D->F 在二元樹裡是被認為不同樹狀結構, 主要是因為前後次序關係 :


特殊二元樹簡介 :
由於二元樹的應用相當廣泛, 所以衍生許多特殊的二元樹結構. 分別介紹如下 :
- 完滿二元樹 (Fully Binary Tree) :
如果二元樹的高度為h, 樹的節點數為2^h-1, h>=0, 則我們稱此樹為”完美二元樹”, 如下圖 :


- 完整二元樹 (Complete Binary Tree) : 
如果二元樹的高度為h, 樹的節點數小於2^h-1, h>=0, 從左到右, 由上到下的順序一一對應結合, 則我們稱此樹為”完整二元樹”, 如下圖 :

補充說明 :
* Wiki - 樹(資料結構) :

樹是一種資料結構，它是由n（n>=1）個有限結點組成一個具有層次關係的集合。把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

- 每個結點有零個或多個子結點；
- 每一個子結點只有一個父結點；
- 沒有前驅的結點為根結點；
- 除了根結點外，每個子結點可以分為m個不相交的子樹；

This message was edited 9 times. Last update was at 17/04/2010 09:45:01