# Tree 樹
## 定義
(1)任兩點之間有一個路徑可以相通，且沒有"環"結構的圖。也可以看做是由一個點開始，藉由很多條邊向外拓展到其他點上，而且點和邊都沒有被重複拓展到。
(2)是由≧1個node所形成的集合，==不可以為空==，並且滿足以下條件:
a.至少有一個特殊的node，稱為root。
b.其餘node分成 $T_1,T_2,...T_n$之互斥集合，而$T_1~T_n$稱為root的子樹(subtrees)。
* **環 (cycle)** : 沿著邊的排列走，可以走到起點的圖。
```graphviz
graph graphname{
a--b;
a--c;
b--d;
b--e;
c--f;
c--g;
}
```
## 名詞定義
* **節點 (node)** : 進行延伸拓展的點、被延伸拓展到的點，也就是說樹上的點都是「節點」。每個節點包括一項資料以及指向其他節點的分枝。
* **分支 (branch)** : 兩個節點之間的連線或指標，分枝所連接的兩個節點具有父子關係。
```graphviz
graph graphname{
a [label="node" ; fontcolor=blue ; color = blue ]
b [label="node" ; fontcolor=blue ; color = blue ]
c [label="node" ; fontcolor=blue ; color = blue ]
a -- b [color=red];
a -- c [label="branch" ; color=red ; fontcolor=red];
}
```
* **樹根 (root)** : 一棵樹可以想作是由一個點開始分枝所形成，而這個點即為樹根。一棵樹上的每個點都可以當作樹根。
* **樹葉 (leaf)** : 在一棵樹上選定一個根之後，由根開始不斷分枝，途中無法繼續分枝的點即為樹葉。也可以不選定根，這種情況下，只連著一條邊的點都是「葉」。如果樹上總共只有一個點，那麼此點既是根、也是葉。又可稱為 **「終端節點 (terminal node)」** 或 **「外部節點 (externel node)」**。
```graphviz
digraph graphname{
a[label="root" ; color=brown ; fontcolor = brown]
d[label="leaf" ; color=green ; fontcolor = green]
e[label="leaf" ; color=green ; fontcolor = green]
f[label="leaf" ; color=green ; fontcolor = green]
g[label="leaf" ; color=green ; fontcolor = green]
h[label="leaf" ; color=green ; fontcolor = green]
b[label=" "]
c[label=" "]
a->b;
a->h;
a->c;
b->d;
b->e;
c->f;
c->g;
{rank=same;a,c}
}
```
* **階層 (level)** : 在一棵樹上選定根後，按照拓展的順序（也就是按照每個點離根的距離），將樹上的點分層次，使得樹上每一個點都擁有一個層數。如果改變根，那麼分層的結果就會不同。
* **父親(parent)** 與 **小孩(child)** : 。在一棵樹上選定根後，以邊相連的任兩點，靠近樹根者相對地稱作「父親」，靠近樹葉者相對地稱作「小孩」。父親只有一個，特例是:是樹根沒有父親；小孩可以很多個，特例是:樹葉沒有小孩。
* **樹的分支度(degree)** :一棵樹中所有節點支度最大者，又稱作 **「樹的階度 (order)」**。若一棵樹的order為k，則在樹中節點的最大分支度為k。
* **祖先(ancestor)** 和 **子孫(descendant)** : 在一棵樹上選定根後，一個點的父親、父親的父親等等，皆是此點的「祖先」。一個點的小孩、小孩的小孩等等，皆是此點的「子孫」。
* **高度(height)** : 樹中節點的最大階層，又可稱為 **「深度(depth)」** 。
* **森林(forest)** : 由很多棵樹所形成的集合稱作森林。只有一棵樹也可以稱作森林。
## Tree的表示方式(PDF p.83)
### 方法一 : 利用Linked List 直接表示
* 作法 : **假設Tree的degree為k**
則每個節點的structure為
```graphviz
digraph structs{
node[shape=record]
struct1[label="<f0>Data|<f1>Link_1|<f2>Link_2|<f3>........|<f4>Link_k"]
struct2[label="<f0>Data|<f1>Link_1|<f2>Link_2|<f3>........|<f4>Link_k"; color=white ; fontcolor = white]
struct1:f1->struct2:f1;
struct1:f2->struct2:f2[label=" 共有k條Link欄"];
struct1:f4->struct2:f4;
}
```
* 範例 :
```graphviz
graph{
A--B;
A--C;
A--D;
C--E;
C--F;
}
```
```graphviz
digraph structs{
node[shape=record]
A[label="<f0>A|<f1>Link_1|<f2>Link_2|<f3>Link_3"]
B[label="<f0>B|<f1>Link_1|<f2>Link_2|<f3>Link_3"]
C[label="<f0>C|<f1>Link_1|<f2>Link_2|<f3>Link_3"]
D[label="<f0>D|<f1>Link_1|<f2>Link_2|<f3>Link_3"]
E[label="<f0>E|<f1>Link_1|<f2>Link_2|<f3>Link_3"]
F[label="<f0>F|<f1>Link_1|<f2>Link_2|<f3>Link_3"]
A:f1->B:f0
A:f2->C:f0
A:f3->D:f0
C:f1->E:f0
C:f2->F:f0
{rank=same;B,C,D}
}
```
* 分析 :
最大缺點在於極度浪費linking space。
說明:
==假設有**n**個node==，==Tree的degree為**k**==，則 link 總共有 **n×k** 條，其中==有用的==有**n-1**條
$\Rightarrow$浪費比例
$$
\frac{nk-(n-1)}{nk}=\frac{n(k-1)+1}{nk}\cong\frac{n(k-1)}{nk}=\frac{k-1}{k}
$$
(k=2時會最少)
### 方法二 : 括號法
* 以 ==父(子1,子2,.......,子k)== 括號的方式來表達父點和的子點的關係。
* 範例 : **A(BC(EF)D)**
```graphviz
graph{
A--B;
A--C;
A--D;
C--E;
C--F;
}
```
### 方法三 : "Child-Sibling"方法(左子右弟法)
* 做法 :
**Node**
```graphviz
digraph struct{
node[shape=record]
a[label="<1>Data|<2>child|<3>siblig"]
}
```
**child** : 將 pointer 指向第一個(最左邊)的 child (若無 child，則為 NULL )。
**sibling** : 將 pointer 指向其右鄰兄弟。
* 範例 :
```graphviz
graph{
A--B;
A--C;
A--D;
C--E;
C--F;
}
```
```graphviz
digraph struct{
rankdir="LR"
splines="line"
nodesep=0.5
node[shape=record]
A[label="{<1>A|<2>|<3>NULL}"]
B[label="{<1>B|<2>NULL|<3>}"]
C[label="{<1>C|<2>|<3>}"]
D[label="{<1>D|<2>|<3>NULL}"]
E[label="{<1>E|<2>NULL|<3>}"]
F[label="{<1>F|<2>|<3>NULL}"]
B:1->A:2[dir="back";color=red;label="child"]
A->C[color =white]
B->C[color=blue;label="sibling"]
B->E[color =white]
E:1->C:2[dir="back";color=red;label="child"]
C->D[color=blue;label="sibling"]
C->F[color =white]
E->F[color=blue;label="sibling"]
}
```
### 方法四 : 將tree化成binary tree之後再表示
(見binary tree)