親愛的老師您好 感謝您選用本書作為授課教材，博碩文化準備本書精選簡報檔，特別摘錄重點提供給您授課專用。 說明： 博碩文化： 1、本教具為非賣品，不得作為商業之用。 2、本教具僅授權使用原著作為授課教材之教師作為教學或研究等學術用途。 3、本教具未授權提供學生任何拷貝、影印、引用、翻印等行為。 4、教師若需申請網站或內容授權，可透過您的博碩業務協助處理，謝謝。 博碩文化： 總公司：台北縣汐止市新台五路一段94號6樓A棟 電話：(02) 2696-2869 分機 313 傳真：(02) 2696-2867 網址：www.drmaster.com.tw 客服信箱：school@drmaster.com.tw 出書提案信箱 schoolbook@drmaster.com.tw

資料結構 請老師填入姓名主講 課本：圖解資料結構 博碩文化出版發行

第五章 樹狀結構 課前指引 樹(tree)是另外一種典型的資料結構，可用來描述有分支的結構，屬於一種階層性的非線性結構。樹的應用範圍很廣，包括籃球賽程、族譜、公司組織圖等，再者計算機上的MS-DOS、Unix作業系統和檔案系統，均是一種樹狀結構的應用。 備註：可依進度點選小節

章節大綱 5-1 樹的基本觀念 5-6 樹的二元樹表示法 5-2 二元樹 5-7 最佳化二元搜尋樹 5-3 二元樹的儲存方式 5-8 平衡樹 5-4 二元樹走訪 5-9 進階樹狀結構研究 5-5 引線二元樹

5-1 樹的基本觀念 「樹」(Tree)是由一個或一個以上的節點(Node)組成，存在一個特殊的節點，稱為樹根(Root)，每個節點可代表一些資料和指標組合而成的記錄。 其餘節點則可分為n≧0個互斥的集合，即是T1,T2,T3…Tn，則每一個子集合本身也是一種樹狀結構及此根節點的子樹。

5-1 樹的基本觀念 專有名詞介紹 分支度(Degree)：每個節點所有的子樹個數。例如像上圖中節點Ｂ的分支度為2，D的分支度為3，F、K、I、J等為0。 階層或階度(level)：樹的層級，假設樹根A為第一階層，BCD節點即為階層2，E、F、G、H、I、J為階層3。 高度(Height)：樹的最大階度。例如上圖的樹高度為4。 樹葉或稱終端節點(Terminal Nodes)：分支度為零的節點，如上圖中的K、L、F、G、M、I、J，下圖則有4個樹葉節點，如ECHJ：

5-1 樹的基本觀念 父節點(Parent)：每一個節點有連結的上一層節點為父節點，例如F的父節點為B，M的父節點為H，通常在繪製樹狀圖時，我們會將父節點畫在子節點的上方。 子節點(children)：每一個節點有連結的下一層節點為子節點，例如A的子節點為B、C、D，B的子節點為Ｅ、F。

5-1 樹的基本觀念 祖先(ancestor)和子孫(decendent)：是指從樹根到該節點路徑上所包含的節點，而子孫則是在該節點往下追溯子樹中的任一節點。例如K的祖先為A、B、E節點，Ｈ的祖先為A、D節點，節點B的子孫為E、F、K、L。 兄弟節點(siblings)：有共同父節點的節點為兄弟節點，例如B、C、D為兄弟，H、I、J也為兄弟。 非終端節點(Nonterminal Nodes)：樹葉以外的節點，如A、B、C、D、E、H等。 高度(Height)：樹的最大階度，例如此樹形圖的高度為4。 同代(Generation)：具有相同階層數的節點，例如E、F、G、H、I、J，或是B、C、D。

5-2 二元樹 二元樹的特性 二元樹是一種有序樹(Order Tree)，並由節點所組成的有限集合，這個集合若不是空集合，就是由一個樹根與左子樹(Left Subtree)和右子樹(Right Subtree)所組成。如下圖所示：

5-2 二元樹 二元樹與樹不同的特性： 1.在二元樹中，階度(Level)為i的節點數最多是2i-1(i0)： 例如有一種特殊的二元樹結構，稱為完滿二元樹(Fully Binary Tree)，也就是如果二元樹的高度為k，在第k階層樹的節點數就為2k-1，如下圖所示：

5-2 二元樹 2.階度為k的二元樹總節點數是2k-1： 從這完滿二元樹中，就可實證這個特性，從圖中得知當深度為4 ，共有24-1=8個節點。我們也可利用數學歸納法證明： 2.階度為k的二元樹總節點數是2k-1： 由上圖的完滿二元樹，其節點總數為level 1到level k中各層level中最大節點的總和： 當i=1時，只有樹根一個節點，所以2i-1=20=1成立。 假設對於j，且1ji，階度為j的最多點數2j-1個成立，則在j=i階度上的節點最多為2i-1個。則當j=i+1時，因為二元樹中每一個節點的分支度都不大於2，因此在階度j=i+1時的最多節點數2*2i-1=2i，由此得證。

5-2 二元樹 3.對於任何非空二元樹T，如果n0為樹葉節點數，且分支度為2的節點數是n2，則有n0= n2+1： 假設n是節點總數，n1是分支度等於1的節點數，可得n= n0+n1+n2， 令B=n-1，B是節點的分支總數，且B= n0+2n1，因為二元樹中每個節點的分支數，不是1就是2，我們可得下式： n-1= n0+2n1，且n= n0+n1+n2 => n0= n2+1

5-2 二元樹 4.高度為k的二元樹，總節點數最少為k： 由於每一階度至少要有一個節點，所以總節點數至少為k。 歪斜樹(Skewed Binary Tree)就是這種典型的範例，例如當一個二元樹完全沒有右節點或左節點時，就把它稱為左歪斜樹或右歪斜樹。

5-2 二元樹 特殊二元樹簡介 完整二元樹(Complete Binary Tree) 如果二元樹的深度為h，所含的節點數小於2h-1，但其節點的編號方式如同深度為h的完滿二元樹一般，從左到右，由上到下的順序一一對應結合。 對於完整二元樹而言，假設有N個節點，那麼此二元樹的階層 (Level)h為 。如下圖所示：

5-2 二元樹 嚴格二元樹(Strictly Binary Tree) 二元樹中的每一個非終端節點均有非空的左右子樹，如下圖：

5-2 二元樹 範例 5.3.1 假如有一個非空樹，其分支度為5，已知分支度為i的節點數有i個，其中1≤i≤5，請問終端節點數總數是多少？ 解答：41個

5-3 二元樹的儲存方式 一維陣列表示法 使用循序的一維陣列來表示二元樹，首先可將此二元樹假想成一個完滿二元樹(Full Binary Tree)，而且第k個階度具有2k-1個節點，並且依序存放在此一維陣列中。 使用一維陣列建立二元樹的表示方法及索引值的配置：

5-3 二元樹的儲存方式 一維陣列中的索引值有以下關係： 二元搜尋樹具有以下特點： 1.左子樹索引值是父節點索引值*2。 2.右子樹索引值是父節點索引值*2+1。 1.可以是空集合，但若不是空集合則節點上一定要有一個鍵值。 2.每一個樹根的值需大於左子樹的值。 3.每一個樹根的值需小於右子樹的值。 4.左右子樹也是二元搜尋樹。 5.樹的每個節點值都不相同。

5-3 二元樹的儲存方式 示範將一組資料32、25、16、35、27，建立一棵二元搜尋樹： C的二元樹建立演算法如下： Btree_create(int *btree,int *data,int length) { for (i=1;i<length;i++) printf("[%2d] ",data[i]);

5-3 二元樹的儲存方式 for(i=1;i<9;i++) /*把原始陣列中的值逐一比對*/ { for(level=1;btree[level]!=0;)/*比較樹根及陣列內的值*/ if(data[i]>btree[level]) /*如果陣列內的值大於樹根，則往右子樹比較*/ level=level*2+1; else /*如果陣列內的值小於或等於樹根，則往左子樹比較*/ level=level*2; } /*如果子樹節點的值不為0，則再與陣列內的值比較一次*/ btree[level]=data[i]; /*把陣列值放入二元樹*/ }

5-3 二元樹的儲存方式 範例 5.3.2 請設計一C程式，依序輸入一棵二元樹節點的資料，分別是0、6、3、5、4、7、8、9、2，並建立一棵二元搜尋樹，最後輸出此儲存此二元樹的一維陣列。

5-3 二元樹的儲存方式 解答 請參考程式CH05_01.c，而此陣列值在二元樹中的存放情形： #include <stdio.h> #include <stdlib.h> void Btree_create(int *btree,int *data,int length) { int i,level; for(i=1;i<length;i++) /*把原始陣列中的值逐一比對*/ for(level=1;btree[level]!=0;)/*比較樹根及陣列內的值*/ if(data[i]>btree[level]) /*如果陣列內的值大於樹根，則往右子樹比較*/ level=level*2+1; else /*如果陣列內的值小於或等於樹根，則往左子樹比較*/ level=level*2; } /*如果子樹節點的值不為0，則再與陣列內的值比較一次*/ btree[level]=data[i]; /*把陣列值放入二元樹*/ } int main() int i,length=9; int data[]={0,6,3,5,4,7,8,9,2};/*原始陣列*/ int btree[16]={0}; /*存放二元樹陣列*/ printf("原始陣列內容：\n"); for(i=0;i<length;i++) 5-3 二元樹的儲存方式 解答 請參考程式CH05_01.c，而此陣列值在二元樹中的存放情形：

5-3 二元樹的儲存方式 printf("[%2d] ",data[i]); printf("\n"); Btree_create(btree,data,9); printf("二元樹內容：\n"); for (i=1;i<16;i++) printf("[%2d] ",btree[i]); system("pause"); return 0; } 5-3 二元樹的儲存方式

5-3 二元樹的儲存方式 串列表示法 使用串列來表示二元樹的好處是對於節點的增加與刪除相當容易，缺點是很難找到父節點，除非在每一節點多增加一個父欄位。 以上述宣告而言，此節點所存放的資料型態為整數。如果使用C的結構指令，可寫成如下的宣告： struct tree { int data; struct tree *left; struct tree *right; } typedef struct tree node; typedef node *btree;

5-3 二元樹的儲存方式 以串列方式建立二元樹的C演算法如下： btree creat_tree(btree root,int val) { btree newnode,current,backup; newnode=(btree)malloc(sizeof(node)); newnode->data=val; newnode->left=NULL; newnode->right=NULL; if(root==NULL) root=newnode; return root; } else for(current=root;current!=NULL;)

5-3 二元樹的儲存方式 backup=current; if(current->data > val) current=current->left; else current=current->right; } if(backup->data >val) backup->left=newnode; backup->right=newnode; return root;

#include <stdio.h> #include <stdlib.h> struct tree { int data; struct tree *left,*right; }; typedef struct tree node; typedef node *btree; btree creat_tree(btree,int); int main() { int i,data[]={5,6,24,8,12,3,17,1,9}; btree ptr=NULL; btree root=NULL; for(i=0;i<9;i++) ptr=creat_tree(ptr,data[i]); /*建立二元樹*/ printf("左子樹:\n"); root=ptr->left; while(root!=NULL) printf("%d\n",root->data); root=root->left; } printf("--------------------------------\n"); 5-3 二元樹的儲存方式 範例 5.3.2 請設計一C程式，依序輸入一棵二元樹節點的資料，分別是5,6,24,8,12,3,17,1,9，利用鏈結串列來建立二元樹，最後並輸出其左子樹與右子樹。

5-3 二元樹的儲存方式 printf("右子樹:\n"); root=ptr->right; while(root!=NULL) { printf("%d\n",root->data); root=root->right; } printf("\n"); system("pause"); return 0; btree creat_tree(btree root,int val) /*建立二元樹函數*/ btree newnode,current,backup; newnode=(btree)malloc(sizeof(node)); newnode->data=val; newnode->left=NULL; newnode->right=NULL; if(root==NULL) root=newnode; return root; else

5-3 二元樹的儲存方式 { for(current=root;current!=NULL;) backup=current; if(current->data > val) current=current->left; else current=current->right; } if(backup->data >val) backup->left=newnode; backup->right=newnode; return root;

5-4 二元樹走訪 中序走訪 中序走訪(Inorder Traversal)是LDR的組合，也就是從樹的左側逐步向下方移動，直到無法移動，再追蹤此節點，並向右移動一節點。 如果無法再向右移動時，可以返回上層的父節點，並重覆左、中、右的步驟進行。如下所示： 1.走訪左子樹。 2.拜訪樹根。 3.走訪右子樹。

5-4 二元樹走訪 右圖的中序走訪為：FDHGIBEAC 中序走訪的C遞迴演算法如下： void in(btree ptr)/*中序走訪*/ { if (ptr != NULL) in(ptr->left); printf("[%2d] ",ptr->data); in(ptr->right); }

5-4 二元樹走訪 後序走訪 後序走訪(Postorder Traversal)是LRD的組合，走訪的順序是先追蹤左子樹，再追蹤右子樹，最後處理根節點，反覆執行此步驟。如下所示： 右圖的後序走訪為：FHIGDEBCA 1.走訪左子樹。 2.走訪右子樹。 3.拜訪樹根。

5-4 二元樹走訪 後序走訪的C遞迴演算法如下： void post(btree ptr)/*後序走訪*/ { if (ptr != NULL) post(ptr->left); post(ptr->right); printf("[%2d] ",ptr->data); }

5-4 二元樹走訪 前序走訪 前序走訪(Preorder Traversal)是DLR的組合，也就是從根節點走訪，再往左方移動，當無法繼續時，繼續向右方移動，接著再重覆執行此步驟。如下所示： 右圖的前序走訪為：ABDFGHIEC 1.拜訪樹根。 2.走訪左子樹。 3.走訪右子樹。

5-4 二元樹走訪 後序走訪的C遞迴演算法如下： void post(btree ptr)/*後序走訪*/ { if (ptr != NULL) post(ptr->left); post(ptr->right); printf("[%2d] ",ptr->data); }

5-4 二元樹走訪 範例 5.4.1 請問以下二元樹的中序、前序及後序表示法為何？ 解答: 中序走訪為：DBEACF 前序走訪為：ABDECF 後序走訪為：DEBFCA

5-4 二元樹走訪 範例 5.4.2 請問下列二元樹的中序、前序及後序走訪的結果為何？ 解答: 前序：ABDHIECFJKGLM 中序：HDIBEAJFKCLGM 後序：HIDEBJKFLMGCA

#include <stdio.h> #include <stdlib.h> struct tree { int data; struct tree *left,*right; }; typedef struct tree node; typedef node *btree; btree creat_tree(btree,int); void inorder(btree ptr) /*中序走訪副程式*/ { if(ptr!=NULL) inorder(ptr->left); printf("[%2d] ",ptr->data); inorder(ptr->right); } int main() int i,data[]={5,6,24,8,12,3,17,1,9}; btree ptr=NULL; btree root=NULL; for(i=0;i<9;i++) 5-4 二元樹走訪 範例 5.4.3 請設計一C程式，依序輸入一棵二元樹節點的資料，分別是5,6,24,8,12,3,17,1,9，利用鏈結串列來建立二元樹，最後並進行中序走訪，各位會發現可以輕鬆完成由小到大的排序。

5-4 二元樹走訪 ptr=creat_tree(ptr,data[i]); /*建立二元樹*/ printf("====================\n"); printf("排序完成結果：\n"); inorder(ptr); /*中序走訪*/ printf("\n"); system("pause"); return 0; } btree creat_tree(btree root,int val) /*建立二元樹函數*/ { btree newnode,current,backup; newnode=(btree)malloc(sizeof(node)); newnode->data=val; newnode->left=NULL; newnode->right=NULL; if(root==NULL) root=newnode; return root; else for(current=root;current!=NULL;)

5-4 二元樹走訪 { backup=current; if(current->data > val) current=current->left; else current=current->right; } if(backup->data >val) backup->left=newnode; backup->right=newnode; return root;

5-4 二元樹走訪 範例 5.4.4 請依序輸入一棵二元樹節點的資料，分別是7,4,1,5,16,8,11,12,15,9,2，首先手繪出此二元樹，並設計一C/C++程式，輸出此二元樹的中序、前序與後序的走訪結果。

5-4 二元樹走訪 解答: #include <stdio.h> #include <stdlib.h> struct tree { int data; struct tree *left,*right; }; typedef struct tree node; typedef node *btree; btree creat_tree(btree,int); void inorder(btree ptr) /*中序走訪副程式*/ { if(ptr!=NULL) inorder(ptr->left); printf("[%2d] ",ptr->data); inorder(ptr->right); } void postorder(btree ptr)/*後序走訪*/ if (ptr != NULL) postorder(ptr->left); postorder(ptr->right); 5-4 二元樹走訪 解答:

5-4 二元樹走訪 printf("[%2d] ",ptr->data); } void preorder(btree ptr)/*前序走訪*/ { if (ptr != NULL) preorder(ptr->left); preorder(ptr->right); int main() int i,data[]={7,4,1,5,16,8,11,12,15,9,2}; btree ptr=NULL; btree root=NULL; for(i=0;i<11;i++) ptr=creat_tree(ptr,data[i]); /*建立二元樹*/ printf("=======================================================\n"); printf("中序式走訪結果：\n"); inorder(ptr); /*中序走訪*/ printf("\n");

5-4 二元樹走訪 printf("後序式走訪結果：\n"); postorder(ptr); /*中序走訪*/ printf("\n"); preorder(ptr); /*中序走訪*/ system("pause"); return 0; } btree creat_tree(btree root,int val) /*建立二元樹函數*/ { btree newnode,current,backup; newnode=(btree)malloc(sizeof(node)); newnode->data=val; newnode->left=NULL; newnode->right=NULL; if(root==NULL) root=newnode; return root; else

5-4 二元樹走訪 for(current=root;current!=NULL;) { backup=current; if(current->data > val) current=current->left; else current=current->right; } if(backup->data >val) backup->left=newnode; backup->right=newnode; return root;

5-4 二元樹走訪 二元樹節點的插入與刪除 二元樹搜尋的C演算法： btree search(btree ptr,int val) /*搜尋二元樹某鍵值的函數*/ { while(1) if(ptr==NULL) /*沒找到就傳回NULL*/ return NULL; if(ptr->data==val) /*節點值等於搜尋值*/ return ptr; else if(ptr->data > val) /*節點值大於搜尋值*/ ptr=ptr->left; else ptr=ptr->right; }

#include <stdio.h> #include <stdlib.h> struct tree { int data; struct tree *left,*right; }; typedef struct tree node; typedef node *btree; btree creat_tree(btree root,int val) { btree newnode,current,backup; newnode=(btree)malloc(sizeof(node)); newnode->data=val; newnode->left=NULL; newnode->right=NULL; if(root==NULL) root=newnode; return root; } else for(current=root;current!=NULL;) 5-4 二元樹走訪 範例 5.4.5 請實作一個二元樹的搜尋程式，首先建立一個二元搜尋樹，並輸入要尋找的值。如果節點中有相等的值，會顯示出搜尋的次數。如果找不到這個值，也會顯示訊息，二元樹的節點資料依序為7,1,4,2,8,13,12,11,15,9,5。

5-4 二元樹走訪 backup=current; if(current->data > val) current=current->left; else current=current->right; } if(backup->data >val) backup->left=newnode; backup->right=newnode; return root; btree search(btree ptr,int val) /*搜尋二元樹副程式*/ { int i=1; /*判斷執行次數的變數*/ while(1) if(ptr==NULL) /*沒找到就傳回NULL*/ return NULL; if(ptr->data==val) /*節點值等於搜尋值*/ printf("共搜尋 %3d 次\n",i); return ptr; else if(ptr->data > val) /*節點值大於搜尋值*/

5-4 二元樹走訪 ptr=ptr->left; else ptr=ptr->right; i++; } int main() { int i,data,arr[]={7,1,4,2,8,13,12,11,15,9,5}; btree ptr=NULL; printf("[原始陣列內容]\n"); for (i=0;i<11;i++) ptr=creat_tree(ptr,arr[i]); /*建立二元樹*/ printf("[%2d] ",arr[i]); printf("\n"); printf("請輸入搜尋值：\n"); scanf("%d",&data); if((search(ptr,data)) !=NULL) /*搜尋二元樹*/ printf("你要找的值 [%3d] 有找到!!\n",data); printf("您要找的值沒找到!!\n"); system("pause"); return 0;

#include <stdio.h> #include <stdlib.h> struct tree { int data; struct tree *left,*right; }; typedef struct tree node; typedef node *btree; btree creat_tree(btree root,int val) { btree newnode,current,backup; newnode=(btree)malloc(sizeof(node)); newnode->data=val; newnode->left=NULL; newnode->right=NULL; if(root==NULL) root=newnode; return root; } else for(current=root;current!=NULL;) 5-4 二元樹走訪 範例 5.4.6 請實作一個二元樹的搜尋C程式，首先建立一個二元搜尋樹，二元樹的節點資料依序為7,1,4,2,8,13,12,11,15,9,5，請輸入一鍵值，如不在此二元樹中，則將其加入此二元樹。

5-4 二元樹走訪 backup=current; if(current->data > val) current=current->left; else current=current->right; } if(backup->data >val) backup->left=newnode; backup->right=newnode; return root; btree search(btree ptr,int val) /*搜尋二元樹副程式*/ { while(1) if(ptr==NULL) /*沒找到就傳回NULL*/ return NULL; if(ptr->data==val) /*節點值等於搜尋值*/ return ptr; else if(ptr->data > val) /*節點值大於搜尋值*/ ptr=ptr->left;

5-4 二元樹走訪 ptr=ptr->right; } void inorder(btree ptr) /*中序走訪副程式*/ { if(ptr!=NULL) inorder(ptr->left); printf("[%2d] ",ptr->data); inorder(ptr->right); int main() int i,data,arr[]={7,1,4,2,8,13,12,11,15,9,5}; btree ptr=NULL; printf("[原始陣列內容]\n"); for (i=0;i<11;i++) ptr=creat_tree(ptr,arr[i]); /*建立二元樹*/ printf("[%2d] ",arr[i]); printf("\n"); printf("請輸入搜尋鍵值：\n");

5-4 二元樹走訪 scanf("%d",&data); if((search(ptr,data))!=NULL) /*搜尋二元樹*/ printf("二元樹中有此節點了!\n",data); else { ptr=creat_tree(ptr,data); inorder(ptr); } system("pause"); return 0;

5-4 二元樹走訪 二元樹節點的刪除則稍為複雜，可分為以下三種狀況： 刪除的節點為樹葉：只要將其相連的父節點指向NULL即可。 刪除的節點只有一棵子樹，如下圖刪除節點1，就將其右指標欄放到其父節點的左指標欄：

5-4 二元樹走訪 刪除的節點有兩棵子樹，如下圖刪除節點4，方式有兩種，雖然結果不同，但都可符合二元樹特性： 1.找出中序立即前行者(inorder immediate successor)，即是將欲刪除節點的左子樹最大者向上提，在此即為節點2，簡單來說，就是在該節點的左子樹，往右尋找，直到右指標為NULL，這個節點就是中序立即前行者。

5-4 二元樹走訪 2.找出中序立即後繼者(inorder immediate successor)，即是將欲刪除節點的右子樹最小者向上提，在此即為節點5，簡單來說，就是在該節點的右子樹，往左尋找，直到左指標為NULL，這個節點就是中序立即後繼者。 範例 5.4.7 請將32、24、57、28、10、43、72、62，依中序方式存入可放10個節點(node)之陣列內，試繪圖與說明節點在陣列中相關位置？如果插入資料為30，試繪圖及寫出其相關動作與位置變化？接著如再刪除的資料為32，試繪圖及寫出其相關動作與位置變化。

5-4 二元樹走訪 解答：

5-4 二元樹走訪 插入資料為30：

5-4 二元樹走訪 刪除的資料為32：

5-4 二元樹走訪 二元運算樹 建立的方法可根據以下二種規則： 現在我們嘗試來練習將A-B*(-C+-3.5)運算式，轉為二元運算樹，並求出此算術式的前序(prefix)與後序(postfix)表示法。  A-B*(-C+-3.5)  (A-(B*((-C)+(-3.5))))  考慮算術式中運算子的結合性與優先權，再適當地加上括號，其中樹葉一定是運算元，內部節點一定是運算子。 再由最內層的括號逐步向外，利用運算子當樹根，左邊運算元當左子樹，右邊運算元當右子樹，其中優先權最低的運算子做為此二元運算樹的樹根。

5-4 二元樹走訪 範例 5.4.8 請畫出出下列算術式的二元運算樹： (a+b)*d+e/(f+a*d)+c 解答：

5-4 二元樹走訪 範例 5.4.9 請問以下二元運算樹的中序、後序與前序的表示法為何？ 解答： 中序：A+B*C-D+E/F

5-4 二元樹走訪 範例 5.4.10 請設計一C程式，來計算以下兩中序式的值，並求得其前序式與後序式。 1. 6*3+9%5 #include <stdio.h> #include <stdlib.h> struct Node/*二元樹的節點宣告*/ { int value;/*節點資料*/ struct Node *left_Node;/*指向左子樹的指標*/ struct Node *right_Node;/*指向左右子樹的指標*/ }; typedef struct Node TreeNode;/*定義新的二元樹節點資料型態*/ typedef TreeNode *BinaryTree;/*定義新的二元樹鏈結資料型態*/ BinaryTree rootNode;//*二元樹的根節點的指標 */ BinaryTree rootNode2; /*將指定的值加入到二元樹中適當的節點*/ void Add_Node_To_Tree(int value) BinaryTree currentNode; BinaryTree newnode; int flag=0;/*用來紀錄是否插入新的節點*/ newnode=(BinaryTree) malloc(sizeof(TreeNode)); /*建立節點內容*/ newnode->value=value; newnode->left_Node=NULL; newnode->right_Node=NULL; /*如果為空的二元樹,便將新的節點設定為根節點*/ 5-4 二元樹走訪 範例 5.4.10 請設計一C程式，來計算以下兩中序式的值，並求得其前序式與後序式。 1. 6*3+9%5 2. 1*2+3%2+6/3+2*2

5-4 二元樹走訪 if(rootNode==NULL) rootNode=newnode; else { currentNode=rootNode;/*指定一個指標指向根節點*/ while(!flag) if (value<currentNode->value) { /*在左子樹*/ if(currentNode->left_Node==NULL) currentNode->left_Node=newnode; flag=1; } currentNode=currentNode->left_Node; { /*在右子樹*/ if(currentNode->right_Node==NULL) currentNode->right_Node=newnode;

5-4 二元樹走訪 currentNode=currentNode->right_Node; } BinaryTree create(char sequence[100],int index,int ArraySize) { BinaryTree tempNode; if ( sequence[index]==0 ||index >= ArraySize )/*作為出口條件*/ return NULL; else { tempNode=(BinaryTree)malloc(sizeof(TreeNode)); tempNode->value=(int)sequence[index]; tempNode->left_Node=NULL; tempNode->right_Node=NULL; /*建立左子樹*/ tempNode->left_Node = create(sequence, 2*index,ArraySize); /*建立右子樹*/ tempNode->right_Node = create(sequence, 2*index+1,ArraySize); return tempNode; /*preOrder(前序走訪)方法的程式內容*/ void preOrder(BinaryTree node)

5-4 二元樹走訪 { if ( node != NULL ) { printf("%c",(char)node->value); preOrder(node->left_Node); preOrder(node->right_Node); } /*inOrder(中序走訪)方法的程式內容*/ void inOrder(BinaryTree node) inOrder(node->left_Node); inOrder(node->right_Node); /*postOrder(後序走訪)方法的程式內容*/ void postOrder(BinaryTree node) postOrder(node->left_Node); postOrder(node->right_Node);

5-4 二元樹走訪 } /*判斷運算式如何運算的方法宣告內容*/ int condition(char oprator, int num1, int num2) { switch ( oprator ) { case '*': return ( num1 * num2 ); /*乘法請回傳num1 * num2*/ case '/': return ( num1 / num2 ); /*除法請回傳num1 / num2*/ case '+': return ( num1 + num2 ); /*加法請回傳num1 + num2*/ case '-': return ( num1 - num2 ); /*減法請回傳num1 - num2*/ case '%': return ( num1 % num2 ); /*取餘數法請回傳num1 % num2*/ return -1; /*傳入根節點,用來計算此二元運算樹的值*/ int answer(BinaryTree node) int firstnumber = 0; int secondnumber = 0; /*遞迴呼叫的出口條件*/ if ( node->left_Node == NULL && node->right_Node == NULL ) /*將節點的值轉換成數值後傳回*/ return node->value-48; else { firstnumber = answer(node->left_Node);/*計算左子樹運算式的值*/

5-4 二元樹走訪 secondnumber = answer(node->right_Node); /*計算右子樹運算式的值*/ return condition((char)node->value, firstnumber, secondnumber); } int main(void) { /* 第一筆運算式 */ char information1[] = {' ','+','*','%','6','3','9','5' }; /* 第二筆運算式 */ char information2[] = {' ','+','+','+','*','%','/','*', '1','2','3','2','6','3','2','2' }; rootNode=(BinaryTree) malloc(sizeof(TreeNode)); rootNode2=(BinaryTree) malloc(sizeof(TreeNode)); // create方法可以將二元樹的陣列表示法轉換成鏈結表示法 rootNode = create(information1,1,8); printf("====二元運算樹數值運算範例 1: ====\n"); printf("=================================\n"); printf("===轉換成中序運算式===: "); inOrder(rootNode); printf("\n===轉換成前序運算式===: "); preOrder(rootNode); printf("\n===轉換成後序運算式===: "); postOrder(rootNode); // 計算二元樹運算式的運算結果

5-4 二元樹走訪 printf("\n此二元運算樹,經過計算後所得到的結果值: "); printf("%d",answer(rootNode)); //建立第二棵二元搜尋樹物件 rootNode2 = create(information2,1,16); printf("\n\n"); printf("====二元運算樹數值運算範例 2: ====\n"); printf("=================================\n"); printf("===轉換成中序運算式===: "); inOrder(rootNode2); printf("\n===轉換成前序運算式===: "); preOrder(rootNode2); printf("\n===轉換成後序運算式===: "); postOrder(rootNode2); // 計算二元樹運算式的運算結果 printf("%d",answer(rootNode2)); printf("\n"); system("pause"); return 0; }

5-4 二元樹走訪 範例 5.4.11 請將A/B**C+D*E-A*C化為二元運算樹。 解答：

5-5 引線二元樹 二元樹轉為引線二元樹 引線二元樹的基本結構如下： 先將二元樹經由中序走訪方式依序排出，並將所有空鏈結改成引線。 如果引線鏈結是指向該節點的左鏈結，則將該引線指到中序走訪順序下前一個節點。 如果引線鏈結是指向該節點的右鏈結，則將該引線指到中序走訪順序下的後一個節點。 指向一個空節點，並將此空節點的右鏈結指向自己，而空節點的左子樹是此引線二元樹。 LBIT：左控制位元 LCHILD：左子樹鏈結 DATA：節點資料 RCHILD：右子樹鏈結 RBIT：右控制位元

5-5 引線二元樹 和鏈結串列所建立的二元樹不同是在於，為了區別正常指標或引線而加入的兩個欄位：LBIT及RBIT。 節點的宣告方式如下： 如果LCHILD為正常指標，則LBIT=1 如果LCHILD為引線，則LBIT=0 如果RCHILD為正常指標，則RBIT=1 如果RCHILD為引線，則RBIT=0 struct t_tree { int DATA,LBIT,RBIT; struct t_tree* LCHILD,RCHILD; }; typedef struct t_tree node; type node *tbtree;

5-5 引線二元樹 練習如何將下圖二元樹轉為引線二元樹： 步驟： 1.以中序追蹤二元樹：HDIBEAFCG

5-5 引線二元樹

5-5 引線二元樹 使用引線二元樹的優缺點： 優點： 缺點： 1.在二元樹做中序走訪時，不需要使用堆疊處理，但一般二元樹卻需要。 2.由於充份使用空鏈結，所以避免了鏈結閒置浪費的情形。另外中序走訪時的速度也較快，節省不少時間。 3.任一個節點都容易找出它的中序後繼者與中序前行者，在中序走訪時可以不需使用堆疊或遞迴。 1.在加入或刪除節點時的速度較一般二元樹慢。 2.引線子樹間不能共享。

5-5 引線二元樹 範例 5.5.1 試述如何對一二元樹作中序走訪不用到堆疊或遞迴？ 解答： 使用引線二元樹(thread binary tree) 即可不必使用堆疊或遞迴來進行中序走訪。因為右引線可以指向中序走訪的下一個節點，而左引線可指向中序走訪的前一個節點。

5-5 引線二元樹 範例 5.5.2 試設計一C程式，利用引線二元樹來追蹤某一節點X的中序前行者與中序後續者。 #include <stdio.h> #include <stdlib.h> struct Node { int value; int left_Thread; int right_Thread; struct Node *left_Node; struct Node *right_Node; }; typedef struct Node ThreadNode; typedef ThreadNode *ThreadBinaryTree; ThreadBinaryTree rootNode; //將指定的值加入到二元引線樹 void Add_Node_To_Tree(int value) { ThreadBinaryTree newnode; ThreadBinaryTree previous; newnode=(ThreadBinaryTree)malloc(sizeof(ThreadNode)); newnode->value=value; newnode->left_Thread=0; newnode->right_Thread=0; newnode->left_Node=NULL; newnode->right_Node=NULL; ThreadBinaryTree current; ThreadBinaryTree parent; 5-5 引線二元樹 範例 5.5.2 試設計一C程式，利用引線二元樹來追蹤某一節點X的中序前行者與中序後續者。

5-5 引線二元樹 previous=(ThreadBinaryTree)malloc(sizeof(ThreadNode)); previous->value=value; previous->left_Thread=0; previous->right_Thread=0; previous->left_Node=NULL; previous->right_Node=NULL; int pos; //設定引線二元樹的開頭節點 if(rootNode==NULL) { rootNode=newnode; rootNode->left_Node=rootNode; rootNode->right_Node=NULL; rootNode->left_Thread=0; rootNode->right_Thread=1; return; } //設定開頭節點所指的節點 current=rootNode->right_Node; if(current==NULL){ rootNode->right_Node=newnode; newnode->left_Node=rootNode; newnode->right_Node=rootNode; return ;

5-5 引線二元樹 parent=rootNode; //父節點是開頭節點 pos=0; //設定二元樹中的行進方向 while(current!=NULL) { if(current->value>value) { if(pos!=-1) { pos=-1; previous=parent; } parent=current; if(current->left_Thread==1) current=current->left_Node; else current=NULL; else { if(pos!=1) { pos=1; if(current->right_Thread==1) current=current->right_Node;

5-5 引線二元樹 } if(parent->value>value) { parent->left_Thread=1; parent->left_Node=newnode; newnode->left_Node=previous; newnode->right_Node=parent; else { parent->right_Thread=1; parent->right_Node=newnode; newnode->left_Node=parent; newnode->right_Node=previous; return ; //引線二元樹中序走訪 void trace() { ThreadBinaryTree tempNode; tempNode=rootNode; do { if(tempNode->right_Thread==0) tempNode=tempNode->right_Node; else

5-5 引線二元樹 { tempNode=tempNode->right_Node; while(tempNode->left_Thread!=0) tempNode=tempNode->left_Node; } if(tempNode!=rootNode) printf("[%d]\n",tempNode->value); } while(tempNode!=rootNode); int main(void) int i=0; int array_size=11; printf("引線二元樹經建立後,以中序追蹤能有排序的效果\n"); printf("第一個數字為引線二元樹的開頭節點,不列入排序\n"); int data1[]={0,10,20,30,100,399,453,43,237,373,655}; for(i=0;i<array_size;i++) Add_Node_To_Tree(data1[i]); printf("====================================\n"); printf("範例 1 \n"); printf("數字由小到大的排序順序結果為: \n"); trace(); int data2[]={0,101,118,87,12,765,65}; rootNode=NULL;/*將引線二元樹的樹根歸零*/

5-5 引線二元樹 array_size=7;/*第2個範例的陣列長度為7*/ for(i=0;i<array_size;i++) Add_Node_To_Tree(data2[i]); printf("====================================\n"); printf("範例 2 \n"); printf("數字由小到大的排序順序結果為: \n"); trace(); printf("\n"); system("pause"); return 0; }

5-5 引線二元樹 範例 5.5.3 請試繪出對應於下圖的引線二元樹。 解答： 由於中序走訪結果為EDFBACHGI，相對應的二元樹如下所示：

5-6 樹的二元樹表示法 樹化為二元樹 對於將一般樹狀結構轉化為二元樹，使用的方法稱為「CHILD-SIBLING」(leftmost-child-next-right-sibling)法則。以下是其執行步驟： 1.將節點的所有兄弟節點，用平行線連接起來。 2.刪掉所有與子點間的鏈結，只保留與最左子點的鏈結。 3.順時針轉45゜。

5-6 樹的二元樹表示法 範例 5.6.1 將右圖樹化為二元樹 解答： 將樹的各階層兄弟用平行線連接起來

5-6 樹的二元樹表示法 解答： 刪除掉所有子節點間的連結，只保留最左邊的子節點。 順時針旋轉45度。

5-6 樹的二元樹表示法 二元樹轉換成樹 如右圖所示： 這就是樹化為二元樹的反向步驟，方法也很簡單。首先是逆時針旋轉45度，如下圖所示：

5-6 樹的二元樹表示法 樹林化為二元樹 除了一棵樹可以轉化為二元樹外，其實好幾棵樹所形成的樹林也可以轉化成二元樹，步驟也很類似，如下所示： 以下圖樹林為範例 由左至右將每棵樹的樹根(root)連接起來。 仍然利用樹化為二元樹的方法操作。

5-6 樹的二元樹表示法 步驟1:將各樹的樹根由左至右連接。 步驟2：利用樹化為二元樹的原則。 步驟3：順時針旋轉45度。

5-6 樹的二元樹表示法 二元樹轉換成樹林 二元樹轉換成樹林的方法則是依照樹林轉化為二元樹的方法倒推回去，例如下圖二元樹：

5-6 樹的二元樹表示法 首先請把原圖逆時旋轉45度。 再依照左子樹為父子關係，右子樹為兄弟關係的原則。逐步劃分：

5-6 樹的二元樹表示法 樹與樹林的走訪 假設樹根為R，且此樹有n個節點，並可分成如下圖的m個子樹：分別是T1,T2,T3…Tm： 三種走訪方式的步驟如下： 中序走訪(Inorder traversal) 以中序法走訪T1。 拜訪樹根R。 再以中序法追蹤T2,T3,…Tm。

5-6 樹的二元樹表示法 樹林的走訪方式則由樹的走訪衍生過來，步驟如下： 前序走訪(Preorder traversal) 後序走訪(Postorder traversal) 樹林的走訪方式則由樹的走訪衍生過來，步驟如下： 中序走訪(Inorder traversal) 拜訪樹根R。 再以前序法依次拜訪T1,T2,T3,…Tm。 以後序法依次拜訪T1,T2,T3,…Tm。 拜訪樹根R。 如果樹林為空，則直接返回。 以中序走訪第一棵樹的子樹群。 中序走訪樹林中第一棵樹的樹根。 依中序法走訪樹林中其它的樹。

5-6 樹的二元樹表示法 前序走訪(Preorder traversal) 後序走訪(Postorder traversal) 如果樹林為空，則直接返回。 走訪樹林中第一棵樹的樹根。 以前序走訪第一棵樹的子樹群。 以前序法走訪樹林中其它的樹。 如果樹林為空，則直接返回。 以後序走訪第一棵樹的子樹。 以後序法走訪樹林中其它的樹。 走訪樹林中第一棵樹的樹根。

5-6 樹的二元樹表示法 範例 5.6.2 將下列樹林轉換成二元樹，並分別求出轉換前樹林與轉換後二元樹的中序、前序與後序走訪結果。 解答 步驟1：

5-6 樹的二元樹表示法 解答 步驟2： 步驟3： 樹林走訪： 中序走訪：EBCDAGHFI 前序走訪：ABECDFGHI 後序走訪：EBCDGHIFA 二元樹走訪： 後序走訪：EDCBHGIFA (請注意！轉換前後的後序走訪結果不同)

5-6 樹的二元樹表示法 範例 5.6.3 求下圖樹轉換成二元樹前後的中序、前序與後序走訪結果。 解答 樹林走訪： 中序走訪：DBHEAFCIG 前序走訪：ABDEHCFGI 後序走訪：DHEBFIGCA

5-6 樹的二元樹表示法 解答 轉換為二元樹如下圖： 二元樹走訪： 中序走訪：DBHEAFCIG 前序走訪：ABDEHCFGI 後序走訪：DHEBFIGCA

5-6 樹的二元樹表示法 決定唯一二元樹 在二元樹的三種走訪方法中，如果有中序與前序的走訪結果或者中序與後序的走訪結果，可由這些結果求得唯一的二元樹。 示範一個範例。例如二元樹的中序走訪為BAEDGF，前序走訪為ABDEFG。請畫出此唯一的二元樹。 解答 中序走訪：左子樹 樹根 右子樹 前序走訪：樹根 左子樹 右子樹

5-6 樹的二元樹表示法 解答 1. D為右子樹的節點 2. 3.

5-6 樹的二元樹表示法 範例 5.6.3 某二元樹的中序走訪為HBJAFDGCE，後序走訪為HJBFGDECA，請繪出此二元樹。 解答 中序走訪：左子樹 樹根 右子樹 後序走訪：左子樹 右子樹 樹根 1.

5-6 樹的二元樹表示法 解答 2. 3. 4.

5-7 最佳化二元搜尋樹 延伸二元樹 任何一個二元樹中，若具有n個節點，則有n-1個非空鏈結及n+1個空鏈結。 如果在每一個空鏈結加上一個特定節點，則稱為外節點，其餘的節點稱為內節點，且定義此種樹為「延伸二元樹」，另外定義外徑長＝所有外節點到樹根距離的總和，內徑長＝所有內節點到樹根距離的總和。

5-7 最佳化二元搜尋樹 以下例來說明(a)(b)兩圖，它們的延伸二元樹繪製： 代表外部節點

5-7 最佳化二元搜尋樹 (a) (b) 外徑長：(2+2+4+4+3+2)=17 內徑長：(1+1+2+3)=7 外徑長：(2+2+3+3+3+3)=16 內徑長：(1+1+2+2)=6

5-7 最佳化二元搜尋樹 以下討論(a)、(b)的加權外徑長： 對(a)來說： 對(b)來說： 2×3+4×3+5×2+15×1=43 2×2+4×2+5×2+15×2=52

5-7 最佳化二元搜尋樹 霍夫曼樹 如果有n個權值(q1,q2…qn)，且構成一個有n個節點的二元樹，每個節點外部節點權值為qi，則加權徑長度最小的就稱為「最佳化二元樹」或「霍夫曼樹」(Huffman Tree)。 接下來將說明，對一含權值的串列，該如何求其最佳化二元樹，步驟如下： 1.產生兩個節點，對資料中出現過的每一元素各自產生一樹葉節點，並賦予樹葉節點該元素之出現頻率。 2.令N為T1和T2的父親節點， T1和T2是T中出現頻率最低的兩個節點，令N節點的出現頻率等於T1和T2的出頻率總和。 3.消去步驟的兩個節點，插入N，再重複步驟1。

5-7 最佳化二元搜尋樹 利用以上的步驟來實作求取霍夫曼樹的過程 假設現在有五個字母BDACE的頻率分別為0.09、0.12、0.19、0.21和0.39，請說明霍夫曼樹建構之過程： 取出最小的0.09和0.12，合併成另一棵新的二元樹，其根節點的頻率為0.21：

5-7 最佳化二元搜尋樹 最後取出0.40和0.60的節點，合併成頻率為1.0的節點，至此二元樹即完成。 再取出0.19和0.21合併後，得到0.40的新二元樹 再出0.21和0.39的節點，產生頻率為0.6的新節點 最後取出0.40和0.60的節點，合併成頻率為1.0的節點，至此二元樹即完成。

5-8 平衡樹 平衡樹的定義 又稱之為AVL樹(是由Adelson-Velskii和Landis兩人所發明的)，本身也是一棵二元搜尋樹，在AVL樹中，每次在插入資料和刪除資料後，必要的時候會對二元樹作一些高度的調整動作，而這些調整動作就是要讓二元搜尋樹的高度隨時維持平衡。 T是一個非空的二元樹，Tl及Tr分別是它的左右子樹，若符合下列兩條件，則稱T是個高度平衡樹： 1. T1及Tr也是高度平衡樹。 2.｜h1-hr|≦１，h1及hr分別為T1與Tr的高度，也就是所有內部節點的左右子樹高度相差必定小於或等於1。

5-8 平衡樹 如下圖所示：

5-8 平衡樹 調整一二元搜尋樹成為一平衡樹 最重要是找出「不平衡點」，再依照以下四種不同旋轉型式，重新調整其左右子樹的長度。首先，令新插入的節點為N，且其最近的一個具有±2的平衡因子節點為A，下一層為B，再下一層C，分述如下： LL型

5-8 平衡樹 LR型 RR型 RL型

5-8 平衡樹 實作範例 下圖的二元樹原是平衡的，加入節點12後變為不平衡，請重新調整成平衡樹，但不可破壞原有的次序結構： 調整結果如下： LR

5-9 進階樹狀結構研究 決策樹 例如最典型的「8枚金幣」問題來闡釋決策樹的觀念，內容是假設有8枚金幣a、b、c、d、e、f、g、h且其中有一枚是偽造的，偽造金幣的特徵為重量稍輕或偏重。 如何使用決策樹方法，找出這枚偽造的錢幣；如果是以L表示輕於真品，H表示重於真品。第一次比較從8枚中任挑6枚a、b、c、d、e、f分2組來比較重量，則會有下列三種情形產生： (a+b+c)>(d+e+f) (a+b+c)=(d+e+f) (a+b+c)<(d+e+f)

5-9 進階樹狀結構研究 依照以上的步驟，畫出以下決策樹的圖形：

5-9 進階樹狀結構研究 B樹 是一種高度大於等於1的m階搜尋樹，它也是一種平衡樹概念的延伸，由Bayer和Mc Creight兩位專家所提出的。主要的特點包括有： 1.B樹上每一個節點都是m階節點。 2.每一個m階節點存放的鍵值最多為m-1個。 3.每一個m階節點分支度均小於等於m。 4.除非是空樹，否則樹根節點至少必須有兩個以上的子節點。 5.除了樹根及樹葉節點外，每一個節點最多不超過m個子節點，但至少包含┌m/2┐個子節點。 6.每個樹葉節點到樹根節點所經過的路徑長度皆一致，也就是說，所有的樹葉節點都必須在同一層(level)。

5-9 進階樹狀結構研究 7.當要增加樹的高度時，處理的作法就是將該樹根節點一分為二。 8.B樹其鍵值分別為k1、k2、k3、k4…km-1，則k1<k2<k3<k4…<km-1。 9.B樹的節點表示法為P0,1，k1，P1,2，k2…Pm-2,m-1，km-1，Pm-1,m。 其節點結構圖如下所示： 其中 k1<k2<k3…<km-1 1.P0,1指標所指向的子樹T1中的所有鍵值均小於k1。 2.P1,2指標所指向的子樹T2中的所有鍵值均大於等於k1且小於k2。 3.以此類推，Pm-1,m指標所指向的子樹Tm中所有鍵值均大於等於km-1。

5-9 進階樹狀結構研究 二元空間分割樹 是一種二元樹，每個節點有兩個子節點，也是一種遊戲空間分割的方法，通常被使用在平面的繪圖應用。 BSP Tree採取的方法就是在一開始將資料檔讀進來的時候，就將整個資料檔中的數據先建成一個二元樹的資料結構。如下圖所示： 二元樹示意圖

5-9 進階樹狀結構研究 四元樹與八元樹 是樹的每個節點擁有四個子節點。 許多遊戲場景的地面(terrian)就是以四元樹來做地劃分，以遞迴的方式，軸心一致的將地形依四個象限分成四個子區域。如下所示: 四元樹示意圖

5-9 進階樹狀結構研究 四元樹在2D平面與碰撞偵測相當有用，底下的圖形是可能對應的3D地形，分割的方式是以地形面的斜率(利用平面法向量來比較)來做依據: 地形與四元樹的對應關係

5-9 進階樹狀結構研究 八元樹(Octree) 定義就是如果不為空樹的話，樹中任一節點的子節點恰好只會有八個或零個，也就是子節點不會有0與8以外的數目。 八元樹的處理規則就是利用遞迴結構的方式來進行，在每個細分的層次上有著同樣規則的屬性。

本章結束 Q&A討論時間