---
tags: 資料結構
---
# 資料結構 第五章 樹

## 一、樹的介紹
### (一)Definition(定義):
1、最源頭(Level值最小)的點稱之為樹根(Root)
2、其他的點被分割為不同的集合，每個集合也皆為樹的型態，我們也稱這些點為Root的子樹(Subtree)
3、不能為空
### (二)常用術語

1、Root(樹根)：
A點為樹根

2、Degree(分支度)：
表示此點有幾棵子樹，EX:A點Degree = 3，C點Degree = 1，F點 = 0 ..etc)

3、Leaf(葉子又稱terminal node終端點)：
分支度為 = 0(如上圖：K、L、F、G、M、I、J為此樹所有葉子)

4、Parent(父點):
直接舉例較為明白，EX:B為E、F的父點、C為G的父點、D為H、I、J的父點..etc

5、Children(子點):
直接舉例與父點相反，EX:E、F為B的子點、G為C的子點、H、I、J為D的子點...etc

6、Sibling(兄弟):
為同Level的其他點，EX:H、I、F、為兄弟..etc

7、Grandparents(祖父點):
為父點的父點，直接舉例較為清晰，EX:D為M的祖父點、B為K、L的祖父點...etc

8、Grandchildren(後代點):
為子點的子點，直接舉例與祖父點相反，EX:M為D的後代點、K、L為B的後代點...etc

9、Height(高度又稱depth深度):
將Root定義為1每向下一個子點增加1，(有些書籍將Root定義成level 0)，此圖樹高度為4。

### (三)樹的表示
#### 1、列表表示(括號表示)

**表示為：(A(B(E(KL)F)C(G)D(H(M)IJ)))**

#### 2、Left Child-Right Sibling Representation(左子點-右兄弟表示法)
**(1)先定義節點結構：**


**(2)依上述圖做轉化表示為：**


**(3)將Left Child-Right Sibling轉換為Tree**

作法：將兄弟點(同Level點)的分支線向右轉(順時針)轉45度。
【重要觀念：後面森林轉換樹也會使用到】

## 二、二元樹
### (一)介紹
#### 1、Definition(定義):
(1)一組有限的點，可以為空。
(2)父點下可分為左子樹及右子樹(左右有次序之分)
#### 2、樹與二元樹之比較

| 樹| 二元樹 |
| -------- | -------- |
|不可為空 | 可為空 |
|分支度 ≧ 0|0≦分支度≦2|
|子點無次序之分|子點有左右次序之分|

#### 3、二元樹抽象資料型態

【變數設定】
for all bt, bt1, bt2 belong to Binary Tree, item belong to element

(1)BinTree Create():
創造一個二元樹(空的)

(2)Boolean IsEmpty(bt):
判斷二元樹是否為空，是回傳True，否則為False。

(3)BinTree MakeBT(bt1, item, bt2):
回傳左子樹至bt1，回傳右子樹至bt2，回傳Root值至item。

(4)BinTree Lchild(bt):
前提假設為空，回傳error(無左子樹)，前提假設不成立，則回傳左子樹(bt)。

(5)element Data(bt):
前提假設為空，回傳error(無Root)，前提假設不成立，則回傳Root點(bt)。

(6)BinTree Rchild(bt):
前提假設為空，回傳error(無右子樹)，前提假設不成立，則回傳右子樹(bt)。

#### 4、二元樹特性定理
#### 圖示：

#### (1)高度固定下最多節點數
在固定高度下能塞最多節點的樹也稱Full Tree，總節點數公式 = 2^高度^-1　【EX: 2^4^-1 = 15節點】
#### (2)某層高度最大節點數
只討論某一層高度最多能塞的節點數，公式為 = 2^高度-1^　【EX: 2^4-1^ = 8節點】
#### (3)葉節點與分支度為二的節點關係
總分支度 = 總點數-1 (因為每個點都有父點，只有Root沒有)
葉節點個數 = 分支度為2的點個數+1 (證明如下)
step1:總分支度 = 分支度為2的點個數 * 2 +分支度為1的點個數 *1 + 葉節點個數(分支度為0)*0
step2:總點數 = 總分支度+1 = 分支度為2的點個數 * 2 +分支度為1的點個數 *1 +1
step3:總點數 = 分支度為2的點個數 + 分支度為1的點個數 + 葉節點個數
step4:利用2、3相等，並移項消去
分支度為2的點個數 + 分支度為1的點個數 + 葉節點個數 = 分支度為2的點個數 * 2 +分支度為1的點個數 *1 +1
葉節點個數 = 分支度為2的點個數+1 得證

#### 5、二元素(陣列)表示
#### (1)圖示:
#### (2)陣列表示:
通常不使用index 0，為了方便計算
①左子點 = 父點*2
②右子點 = 父點*2+1
③父點 = ⌊ 子點/2 ⌋ 取floor

#### (3)鏈結表示：
##### ①定義節點結構：
##### ②以此圖為例：

### 6、二元樹追蹤
#### (1)介紹:
追蹤讓我們經過該樹所有節點一次
依二元樹特性(左右方向)可以分成LVR, LRV, VLR. VRL, RVL, and RLV，共計六種。
加上左子樹優先次之右子樹條件，則只剩LVR, LRV, VLR，3種。
將分別稱為：
LVR：inorder (中序)
LRV：postorder(後序)
VLR：preorder (前序)
#### (2)圖示範例:

1、inorder(中序LDR) ：A/B＊C＊D+E
2、postorder(後序LRD):AB/C＊D＊E+
3、preorder(前序DLR):+＊＊/ABCDE
#### (3)【程式碼】
##### ①Inorder(中序LDR)
【遞迴版本】
void inorder(tree_pointer ptr)
{
if(ptr)
{
inorder(ptr→left_child);
printf("%d",ptr→data);
inorder(ptr→right_child);
}
}
---
【迭代版本】
void iter_inorder(tree—pointer node)
{
int top = -1;
tree_pointer stack[MAX_STACK_SIZE];
for(;;)
{
for(; node; node = node→left_child)
add(&top, node);
node = delete(&top);
if(!node)
break;
printf("%d", node→data);
node = node→right_child;
}
}
---

##### ②Preorder(前序DLR)
void preorder(tree_pointer ptr)
{
if(ptr)
{
printf("%d",ptr→data);
preorder(ptr→left_child);
preorder(ptr→right_child);
}
}
##### ③Postorder(後序LRD)
void postorder(tree_pointer ptr)
{
if(ptr)
{
postorder(ptr→left_child);
postorder(ptr→right_child);
printf("%d",ptr→data);
}
}
#### ④Level由小到大追蹤(Level Order Traversal)
Level_Order：+＊E＊D/CAB
#### 【程式碼】
void level_order(tree_pointer ptr)
{
int front = rear = 0;
tree_pointer queue[MAX_QUEUE_SIZE];
if (!ptr) return;
addq(front, &rear, ptr);
for (;;)
{
ptr = deleteq(&frent, rear);
if (ptr)
{
printf ("%d', ptr→data);
if (ptr→left_child)
addq(front,&rear,ptr→left_child);
if (ptr→right_child)
addq(front,&rear,ptr→right_child);
}
else break;
}
}

## 7、二元樹操作
### (1)測試兩棵二元樹是否相同
#### 【程式碼】
int equal(tree_pointer first,　tree_pointer second)
{
return ((!first && Isecond) || (first && second) &&
(first_>data == second->data) &&
equal(first->left_child,second->left_child) &&
equal(first->right—child, second->right_child))
}

### (2)複製二元樹
#### 【程式碼】
tree_pointer copy(tree_pointer original)
{
tree_pointer temp;
if (original)
{
temp = (tree—pointer) malloc(sizeof(node));
if(is_full(temp))
{
fprint(stderr, "the memory is full\n");
exit(1);
}
temp→left_child = copy(original→left_child);
temp→right_child = copy(original→right_child);
temp→dara = original→data;
return temp;
}
return NULL;
}

### (3)二元樹左右交換(swap-tree)
#### ①圖示:
#### ②【程式碼】
void swap (node *t)
{
if(t!=null)
{
swap(t→Lchild);
swap(t→Rchild);
Node * temp = t→Lchild;
t→Lchild = t→Rchild;
t→Rchild = temp;
}
}

## 三、引線二元樹
### 緣由:為了充分運用節點中的空間(葉節點的左右子點皆為NULL浪費了空間)
### 1、圖示:
#### (1)將空的鏈結連結至前後繼者
#### (2)節點結構如下圖:

### (3)中序式追蹤(在引線二元樹)
#### 如圖:

### (4)引線二元樹中做插入動作
#### ①插入步驟:
step1:更改父點的link (及thread)並將插入的點Thread指向父點
step2:將插入的點link連結至原本的子點
step3:將後代Thread指向至插入的點
#### ②圖示:

### (5)找到中序追蹤節點的後繼者
threaded_pointer insucc(threaded_pointer tree
)
{
threaded_pointer temp;
if(!tree→right_thread)
temp = temp→left_child;
return temp;
}

### (6)引線二元樹中序追蹤
【程式碼】
void tinorder(threaded_pointer tree)
{
threaded_pointer temp = tree;
for(;;)
{
temp = insucc(temp);
if(temp = tree)
break;
printf("%3c", temp→data);
}
}

## 四、堆積
### (一) 定義 Dehnition:
#### 1、最大堆積:
##### (1)每個父點的值都比子點的值大
##### (2)此樹為一棵完全樹
##### (3)圖示:
#### 2、最小堆積:
##### (1)每個父點的值都比子點的值小
##### (2)此樹為一棵完全樹
##### (3)圖示:
#### 3、優先權佇列
與佇列一樣但從佇列中取值(刪除)有優先權(如最大值)那每次取出的值將會是佇列中值最大的數。
#### 4、堆積抽象資料型態

【變數設定】
for all heap belong to MaxHeap, item belong to Element, n, max_size belong to integer
(1)MaxHeap Create(max_size):創造一個空的堆積可容納空間(max_size)
(2)Boolean HeapFull(heap,n):前提假設n等於最大可用空間，則回傳True，前提假設不成立則回傳False。
(3)MaxHeap Insert(heap, item, n):前提假設堆積空間尚未滿，則插入值並回傳，前提假設不成立則回傳error。
(4)Boolean HeapEmpty(heap, n):前提假設n>0回傳True，前提假設不成立則回傳False。
(5)Element Delete(heap, n):前提假設堆積空間不為空，則刪除元素中最大or最小值(視優先權決定)，前提假設不成立則回傳error。
#### 5、優先佇列時間複雜度討論
##### (1)使用無次序陣列插入:
因無關次序只要在rear端做插入一個動作，時間複雜度為O(1)
##### (2)無次序陣列刪除:
因為資料無次序關係必須先搜尋O(1)+刪除O(1)+搬移O(N)，故先時間複雜度為O(N)。
##### (3)無次須鏈結串列插入:
鏈結串列插入只需1個動作插入，故時間複雜度為O(1)
##### (4)無次序鏈結串鍊刪除:
刪除時需要先搜尋(優先權)並斷開前面一位的鏈結，故需要先搜尋後刪除，時間複雜度約為O(n)
##### (5)有次序陣列插入:
因已排序好了故插入時會影響次序，需要做搬動時間複雜度為O(N)
##### (6)有次序陣列刪除:
因已排序好了故不論刪除哪個元素，不搬動也不影響次序，只需要做刪除的動作時間複雜度為O(1)
##### (7)有次序鏈結串列插入:
插入有序(特定)位置需要先做搜尋(先找出優先權)O(N)，插入只需花費O(1)故時間複雜度為O(N)。
##### (8)有次序鏈結串列刪除:
因為以排序好了故優先權為第一個鏈結，故刪除只需要一個動作時間複雜度為O(1)
##### (9)最大堆積插入:
將值插入最後一個位置向上調整至父點均大於子點(次數約為樹高)，完全樹樹高為logn故時間複雜度O(logn)
##### (10)最大堆積刪除:
刪除最大值後，將最後一個值補至樹根再向下調整至所有父點均大於子點，調整次數為樹高故複雜度為O(logn)
### (二)堆積的操作
#### 1、插入:
#### ①圖示:
#### ②【程式碼】
void insert_max_heap(element item, int *n)
{
int i;
if (HEAP_FULL(*n))
{
fprintf(stderr, "The heap is full.\n");
exit(1);
}
i = ++(*n);
while((i != 1)) && (item.key > heap[i/2].key))
{
heap[i] = heap[i/2];
i /= 2;
}
heap[i] = item;
}
#### 2、刪除
#### 1、插入:
#### ①圖示:
#### ②【程式碼】
void deltet_max_heap(int *n)
{
int parent, child;
element item, temp;
if (HEAP_EMPTY(*n))
{
fprintf(stderr, "The heap is empty\n");
exit(1);
}
item = heap[1];
temp = heap[(*n)—];
parent = 1;
child = 2;
while (c

if (child < *n) && (heap[child].key < heap[child+1].key)
child++;
if(temp.key >= heap[child].key)
break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}

## 五、二元搜尋樹
### (一) 定義 Dehnition:
二元搜尋樹為一棵二元樹可以為空，若不為空須符合下面四個特性
1、每個節點都有一個鍵值，每個鍵值都是唯一且不重複
2、若左子樹非空，左子樹的鍵值必小於樹根的鍵值
3、若右子樹非空，右子樹的鍵值必大於樹根的鍵值
4、左右子樹也會是二元搜尋樹
### (二)圖示:
### (三)程式碼:
【遞迴版本】
tree_pointer search(tree＿pointer root, int key)
{
if (! root) return NULL
if (key == root->data) return root;
if (key < root->data)
return search(root->left—child, key);
return search(root->right_child,key);
}
---
【迭代版本】
tree＿pointer search2{tree＿pointer tree, int key)
{
while (tree)
{
if (key == tree->data)
return tree;
if (key < tree->data)
tree=tree->left—child;
else
tree=tree->right— child;
}
return NULL;
}

### (三)二元搜尋樹操作:
#### 1、插入:
##### ①步驟:
step1:使用要插入的鍵值，對二元搜尋樹做搜尋
step2:若搜尋到(代表該鍵值已存在二元搜尋樹中)得到鍵值位置。
若搜尋失敗(代表該鍵值不存在於二元搜尋樹中)，插入搜尋失敗的位置(一直比大小置NULL表示搜尋失敗，插入NULL這空間)
##### ③圖示:
##### ②【程式碼】
void insert_node(tree_pointer *node, int num)
{
tree_pointer ptr, temp = modified_search(*node, num);
if (temp || ! (*node))
{
ptr = (tree_pointer)malloc(sizeof(node));
if (IS_FULL(ptr))
{
fprintf(stderr, "The memory is full\n");
exit(1);
}
ptr->data =num;
ptr->left—child = ptr→right_child = NULL;
if (*node)
if (num <　temp→data)
temp→left_child = ptr;
else
temp→right_child = ptr;
else *node = ptr;
}
}
#### 2、刪除:
##### ①步驟:
step1:刪除鍵值後利用(左子樹最大值or右子樹最小值)替代。
step2:將為連結在樹上的節點，重新搜尋後插入。
##### ③圖示:
##### ②【程式碼】

### 六、選擇樹
#### (一)選擇樹(贏家樹)圖示:
#### 選擇樹(贏家樹)
兩兩比較數字越小的獲勝向上調整
#### (二)選擇樹(輸家樹)圖示:
輸家樹元素為贏家樹輸的元素

### 七、森林
#### (一)定義Definition:
森林一組N>0個不相交的樹所組成
#### (二)圖示:
#### (三)森林轉換為二元樹
##### 1、步驟
step1:將森林的樹先轉換成Left Child-Right Sibling Representation(左子點-右兄弟表示法)
step2:再將每棵樹Root相連在一起
step3:再轉換成二元樹

##### 2、森林的追蹤

### 八、集合表示
#### (一)用途及圖示:
可此用樹結構表示，並應用後面章節圖形
---
#### (二)呈現方法:
##### 1、鏈結串列呈現:
step1:先將各集合隨便取一個節點當作Root
step2:看有幾個幾何準備幾個鏈結連結至各樹的Root

##### 2、陣列呈現:
step1:看有幾個節點就準備多少空間的陣列
Step2:將Data值當作索引，並記錄下父點為誰，若無父點則為-1 (有些會定義成0)

#### (三)集合操作
##### (1)聯集操作(Union)
##### 將兩個集合做合併(集合不計重數沒有次序關係)故 (S~1~ U S~2~) = (S~2~ U S~1~)
##### (2)圖示

##### (3)找出值(Find)
找出鍵值位於哪個集合(回傳Root)大部分的應用在於"判斷x,y兩個鍵值是否屬於相同集合"

##### (4)程式碼
int find1(int i)
{
for(; parent[i] >= 0; i = parent[i]);
return i;
}
void unionl(int i, int j)
{
parent[i] = j;
}
#### (四)集合討論
##### (1)缺點
uniom(i,j)運作，可能建出高度為n之樹，導致Find(x)需花費O(n)之時間若要操作m次則時間複雜度為O(m*n)
##### (2)圖示:

##### (3)改善(union by weight):
①Union:
樹較高的集合之Root當作New Root，而樹高較低的集合為他的子樹。
故高度不同的情況下合併完高度不會改變，只有2個不同高度集合合併才會改變高度。
---
②Find:
花費則為樹高O(log n)，若有m個操作則需花費O(m*log n)。(以樹的分支為log底數)

##### (4)程式碼:
void union2(int i, int j)
{
int temp = parent[i]+parent[j];
if(parent[i]> parent[j])
{
parent[i] = j;
parent[j] = temp;
}
else
{
parent[j] = i;
parent[i] = temp;
}
}

##### (5)最終改善(Find with path compression)
在尋找x的Root過程中，X到Root之路徑上，所有的Node(除Root外)之patent均改成指向Root。
則在搜尋的過程整棵樹就會變得扁平化(leave 2)。
##### 圖示:

### 九、計數二元樹問題
#### (一)二元樹個數問題
二元樹有左右之分所以當節點數一樣時，可以有很多種不同的樹。
【公式】：個數=(1/n+1) * C(2n,n)
##### 圖示:
#### (二)利用堆疊:
將可利用中序與前序or後序orlevel order推敲出原本樹的狀況，二元樹中序特性(鍵值會從小排列到大)
#### (三)矩陣相乘:
類似於二元樹個數問題。
EX:有3個矩陣相乘但相乘順序不一樣，將會影響計算的複雜度不同。
((M1*M2)*M3)
(M1*(M2*M3))

> 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed