# [資料結構] CH6. Trees

* 樹(Tree)是一種新的資料結構，和過去的線性Array或Linked List不同，是屬於**非線性**的結構。
* Tree的資料具有上下的祖先關係，就像祖譜一樣的概念。
* 由於每個節點的結構類似，常配合**遞迴**的方式來撰寫功能。
* 加上一些限制後，會延伸出許多特性。樹狀結構是資料結構中非常重要的一個部分。
* 簡單的Tree範例：

digraph Tree{
    1 [label="A"];
    2 [label="B"];
    3 [label="C"];
    4 [label="D"];
    5 [label="E"];
    6 [label="F"];
    7 [label="G"];
    8 [label="H"];
    9 [label="I"];
    
    1 -> 2
    1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
    3 -> 8
    5 -> 9
}

## Tree的名詞解釋
* 接觸的一個新的東西時，總是要背一些新的專有名詞的。
* 雖然這部分繁瑣，但是考試的關鍵，請務必不要搞錯每個名詞的定義！
* 範例的部分會拿上圖來表示：
* node: 樹裡面每個資料就是一個**節點(node)**。
* ex: A,B,C...I。
* Root node: 一棵樹最上面的node。
* ex: A
* Root node若為NULL節點，表示這棵樹是空的。
* Sub-trees: 上面的範例是一棵樹，但若你只看B D E的部分，它也可以說是一個樹。這時我們就會說B D E是原本樹的**子樹(Sub-trees)**。
* Leaf node: 葉節點(Leaf node)指最下面、沒有小孩的node。
* ex: D,F,G,H,I。
* Path: 從X節點到Y節點所需經過的節點序列稱作**路徑(Path)**。
* ex: A到F的路徑為A,C,F。
* Children: 一個node往下連接的所有node即為它的**子節點(Children)**。
* ex: B,C是A的子節點。
* Ancestor node: 節點X到root node路徑上所有經過的節點Y，都是**節點X的祖先(Ancestor node)**。
* ex: A,B,E都是節點I的Ancestor node。
* root沒有Ancestor node。
* Descendant node: 就是Ancestor node的相反，X是Y的Ancestor；Y就是X的Descendant。
* ex: I,B,E都是節點A的Descendant node。
* leaf沒有Descendant node。
* Level number: root node的level是`0`，然後每往下一層level就加1。
* ex:B,C的level是`1`；I的level是`3`。
* Degree: 表示一個node有幾個子節點。
* ex: A的Degree是`2`；C的Degree是`3`。
* leaf的Degree必定為`0`。

## Forest
* 森林(Forest)是指多個樹的集合，且這些樹所有的node不可重複。
* 假設一棵樹的root node Degree為`n`，我們將它的root node刪除後，便可以得到一個內含`n`個樹的森林。
* 相對的，我們可以為一個森林添加一個新的root node，並將森林內所有樹的root當作它的小孩，便形成了一顆新的樹(且這棵樹包含了原先森林的所有node)。

## Binary Trees
* 二元樹(Binary Trees)是Tree的一種特例；它所有的node至多只能擁有`2`個小孩。
* 一個二元樹的範例：

digraph Tree{
    1 -> 2
    1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
    4 -> 8
    4 -> 9
    6 -> 10
    6 -> 11
    7 -> 12
}

### Binary Trees的名詞解釋
* 度ㄉ，Binary Tree又有一些名詞要背了。
* 一樣，範例參照上圖。
* Parent: 上一層的node就是自己的老爸。
* ex: `4`是`8``9`的Parent。
* root node沒有Parent。
* Sibling: 當我們有同樣的老爸時，我們就是兄弟(Sibling)。
* ex: `8`和`9`是Sibling，因為他們的老爸都是`4`
* Sibling的level會一樣。
* Height: 從root到leaf的**最長**距離稱作這棵樹的高度(Height)。
* ex: 這棵樹的高度為`4`。
* 高度為`n`的二元樹，最多擁有$2^{n}-1$個node。
* Similar Binary Trees: 當兩個二元樹結構一樣時，我們便稱他們為Similar Binary Trees。
* 下面這棵二元樹和上面的範例是相似二元樹。

digraph Tree{
    11 -> 21
    11 -> 31
    21 -> 41
    21 -> 51
    31 -> 61
    31 -> 71
    41 -> 81
    41 -> 91
    61 -> 101
    61 -> 111
    71 -> 121
}

* Copies: 兩棵樹不但結構一樣，連資料都一樣時，我們稱他們為複製體(Copies)。
* Complete Binary Trees: 當一顆二元樹符合下面兩個特性時，我們稱它為完整二元樹(Complete Binary Trees)：
1. 除了leaf之外的所有node，一定擁有兩個小孩。
2. 所有node要向左邊靠。

digraph Tree{
    label="Complete Binary Tree的範例"
    1 -> 2
    1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
    4 -> 8
    4 -> 9
    5 -> 10
    5 -> 11
    6 -> 12
    6 -> 13
}

* Extended Binary Tree: 當一顆二元樹的所有node，不是沒有小孩，就是有兩個小孩時，我們便稱這棵二元樹為Extended Binary Tree。
* 其中，有兩個小孩的node稱為internal nodes。
* 沒有小孩的node稱為external nodes。

### Linked List 實作
* 使用Linked List來連結node大概長這樣：

Struct node{
    node *leftnode;
    int data;
    node *rightnode;
}

* 至於怎麼去新增並連接、刪除各node就交給各位自己去實踐了。

### Array 實作
* 我們也會使用一維的Array來實作Tree的結構。
* `Tree[1]`為root node。
* `Tree[k]`的兩個小孩分別為`Tree[k*2]`和`Tree[k*2+1]`。
* 相對地，要找`Tree[k]`的老爸就是`Tree[k/2]`。
* 雖然簡單，但是相對的浪費空間。

### 二元樹的延伸
* Binary Search Trees: 用於排序、搜索的二元樹，我們會在下一章詳細介紹。
* Expression Trees: 用來表示一個數學算式的樹，可以方便的得到前序中序後序。
* 如果你對[這張圖](https://hackmd.io/s/SyHco0i2m#%E7%94%A8%E7%95%ABamp%E7%9C%8B%E5%BF%AB%E9%80%9F%E5%BE%97%E5%88%B0%E7%AD%94%E6%A1%88%EF%BC%9A)有印象的話...
* Tournament Trees: 又被稱作選擇樹(Selection trees)，就像是比賽時採用一對一淘汰賽一樣，所有參賽者原先都在leaf，贏家不停向上移動，root表示最後贏家。

### 一般樹轉二元樹
* 一般的樹可以有任意數量的小孩，但二元樹至多只能擁有兩個。
* 我們有一個方法可以將任意的樹轉換為二元樹，只要記住以下三點規則：
1. 二元樹的root就是本來的root。
2. 對於每個node來說，在二元樹時的左邊小孩，就是在一般樹時他的最左邊小孩。
3. 而在二元樹時的右邊小孩，就是在一般樹它的右邊一個的兄弟。

### 前序中序後序
* 前面已經教過你如何從圖看出前序中序後序了，現在要教你怎麼用code輸出：

void InOrder(node* n)
{
    if(n == NULL)
        return;
    InOrder(n->leftnode);
    cout << n->data << endl;
    InOrder(n->rightnode);
}

void PreOrder(node* n)
{
    if(n == NULL)
        return;
    cout << n->data << endl;
    PreOrder(n->leftnode);
    PreOrder(n->rightnode);
}

void PostOrder(node* n)
{
    if(n == NULL)
        return;
    PostOrder(n->leftnode);
    PostOrder(n->rightnode);
    cout << n->data << endl;
}

* 沒錯！他們就只是輸出的時機點不同而已，利用遞迴可以輕鬆得到！

---

* 我們只要有
1. 中序表示法
2. 前序或後序表示法
* 便可以還原出一棵樹的結構。
* 例如：
* 中序: D B E A F C G
* 前序: A B D E C F G
* 還原樹就是：

digraph Tree{
    1 [label="A"];
    2 [label="B"];
    3 [label="C"];
    4 [label="D"];
    5 [label="E"];
    6 [label="F"];
    7 [label="G"];
    
    1 -> 2
    1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
}

* 方法是要先利用前序或後序知道誰是root/老爸，然後再看中序知道哪些在右邊哪些在左邊。
* 以上面例子來說，由前序可以知道A是root，然後中序可以知道DBE在左邊、FCG在右邊。
* 接著D B E再做一次，前序知道B是老爸，中序知道D在左邊、E在右邊。這樣就完成左半邊了。
* 右半邊也同理，前序知道C是老爸，中序知道F在左邊、G在右邊。

###### tags: `DS` `note`