# [資料結構] CH6. Trees
* 樹(Tree)是一種新的資料結構,和過去的線性Array或Linked List不同,是屬於**非線性**的結構。
* Tree的資料具有上下的祖先關係,就像祖譜一樣的概念。
* 由於每個節點的結構類似,常配合**遞迴**的方式來撰寫功能。
* 加上一些限制後,會延伸出許多特性。樹狀結構是資料結構中非常重要的一個部分。
* 簡單的Tree範例:
```graphviz
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`個小孩。
* 一個二元樹的範例:
```graphviz
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。
* 下面這棵二元樹和上面的範例是相似二元樹。
```graphviz
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要向左邊靠。
```graphviz
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大概長這樣:
```C++
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. 而在二元樹時的右邊小孩,就是在一般樹它的右邊一個的兄弟。
![](https://i.imgur.com/Qzmk8x5.png)
### 前序中序後序
* 前面已經教過你如何從圖看出前序中序後序了,現在要教你怎麼用code輸出:
```C++
void InOrder(node* n)
{
if(n == NULL)
return;
InOrder(n->leftnode);
cout << n->data << endl;
InOrder(n->rightnode);
}
```
```C++
void PreOrder(node* n)
{
if(n == NULL)
return;
cout << n->data << endl;
PreOrder(n->leftnode);
PreOrder(n->rightnode);
}
```
```C++
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
* 還原樹就是:
```graphviz
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`