DAY 06 : 樹

6.1 什麼是樹?

在這之前，我們都是在討論一對一的儲存結構，那如果碰到一對多的情形的話該怎麼辦呢?

樹是一種一對多的資料結構，是n(n>=0)個節點的有限集合。n=0時稱之為｢空樹」，在任何一顆非空樹中會有以下的特性:

(請參照圖片編號)

圖6.1

1. 存在著唯一一個根節點(Root)。
2. 沒有擁有任何子樹的節點稱為葉子節點(Leaf)或是終端節點(Terminal Node)。
3. 當n>1時，其餘節點可分為m個互不相交的有限集合，而每一個集合本身就是一顆子樹。
4. 節點擁有的子樹數量稱為度(Degree)，度為0的節點稱為葉子節點，而整棵樹的度是看各個節點中度的最大值，因此此圖上的樹的度就是3。
5. 內部節點又稱為分支節點(Branch)或非終端節點(Non-Terminal Node)。
6. 節點的子樹的根稱為孩子，孩子只會有一個雙親，同個雙親的孩子之間為兄弟。
7. 樹中節點的最大階度就是樹的深度又稱作高度。
8. 階度是從根節點開始算起，根是第一階，以此類推。

6.2 樹的儲存結構(請參照圖6.1的樹狀結構)

樹中節點的儲存位置無法直接反映邏輯關係，和先前的線性串列不同，因此需要使用特別的方法才能夠展現出對樹的儲存結構的表示法。

6.2.1 雙親標記法

由於非每一個節點都有孩子，但每個節點一定都有雙親，運用這個特性，在每個節點中附設一個指標指向雙親節點在陣列中的位置。

1. 由於根節點沒有雙親，因此我們將根節點的指標欄設為-1。
2. |編號|data|parent|
   |0 |A |-1 |
   |1 |B |0 |
   |2 |C |0 |
   |3 |D |1 |
   |4 |E |2 |
   |5 |F |2 |
   |6 |G |3 |
   |7 |H |3 |
   |8 |I |3 |
   |9 |J |4 |
3. 時間複雜度為O(1)
4. 當找到parent=-1時就代表已找到樹的根。

如果再加上最左邊孩子欄(長子欄)便可得知節點的孩子是誰，再加上右邊兄弟欄便可以表示兄弟關係:

|編號|data|parent|firstchild| rightchild|
|0 |A |-1 |1 |-1 |
|1 |B |0 |3 |2 |
|2 |C |0 |4 |-1 |
|3 |D |1 |6 |-1 |
|4 |E |2 |9 |5 |
|5 |F |2 |-1 |-1 |
|6 |G |3 |-1 |7 |
|7 |H |3 |-1 |8 |
|8 |I |3 |-1 |-1 |
|9 |J |4 |-1 |-1 |

1. 長子欄中若沒有孩子的節點則將指標設為-1。
2. 右邊兄弟欄中若沒有右邊兄弟的節點則將指標設為-1。

6.2.2 孩子標記法

由於每一個節點可能有多個子樹，因此適合用多向鏈結串列，也就是讓每個節點有多個指標欄位，每個指標指向一顆子樹的根節點，這種方法就叫做多重鏈結串列標記法。不過因為樹的每個節點的度不一樣所以又可以設計成兩種方案:

1. 指標欄位的個數等於樹的度
   一個節點會有一個資料欄位和多個指標欄位，指標欄位的數量取決於樹的度，以6.1的圖為例，這棵樹的度為3，因此每個節點就會有三個指標欄位，但是這個方法只適用於各節點的度相差很小的時候，不然很浪費空間。
2. 指標欄位的個樹等於該節點的度
   當各節點的度相差很大時就適用這個方法。在這個方法中除了資料欄位和指標欄位外，還要有一個度欄位來儲存該節點的孩子節點個數，這樣子可以改善空間浪費但也帶來了時間的損耗。
   不過如果再對每個節點的孩子節點建立單向鏈結串列作為儲存結構，就可以改善這個問題，為了這個方法需要再另外設計兩種節點結構，一個是孩子鏈結串列的孩子節點，具有資料欄位(儲存某個節點在陣列中的編號)和指向某一個節點的下一個孩子節點的指標欄位。另一種是陣列的首節點，具有資料欄位(儲存某節點資訊)和首指標欄位(儲存該節點的孩子鏈結串列的首指標)。
   孩子標記法的進階版:｢雙親孩子標記法」，是將雙親標記法和孩子標記法結合的方法。

6.2.3 孩子兄弟標記法

任何一顆樹，其節點若有第一個孩子(左孩子)就是唯一的，右兄弟也是，運用這個特徵，我們可以設置兩個指標，分別為第一個孩子指標和右邊兄弟指標，來幫助我們更方便去搜尋某個節點的某個孩子。