此外, 我還參考了下列書籍 :
- 資料結構-使用 C 語言 (松崗, 陳會安)
- 圖說演算法-使用 C 語言 (博碩, 吳燦銘 & 胡昭民)
- 啊哈! 圖解演算法必學基礎 (碁峰, 紀磊)
- 樹根 (Root) : 最上層節點 (無父節點) 為根節點
- 節點 (Node) : 每一筆資料即為一個節點
- 葉節點 (Leaf Node) : 沒有子節點的節點, 即終端節點
- 子樹 (Subtree) : 節點以下與該節點相連的結構
- 樹林 (Forest) : 去除樹根後的結構稱為樹林
樹狀結構有三個主要參數 :
- 階度 (Level) : 節點在樹狀結構之階層位置, 樹根之階度為 1.
- 高度 (Height) : 樹的最高階度稱為高度.
- 分支度 (Degree) : 一個節點的子樹個數稱為其分支度. 二元樹節點分支度最多為 2.
樹 (Tree) 其實是圖 (Graph) 的一種特例, 它是一種無迴路 (loopless) 的無向圖, 常見的應用是家譜, 組織架構, 目錄, 或者是檔案總管的資料夾等等. 樹的特徵如下 :
- 任意兩節點僅有一條路徑.
- N 個節點的樹剛好有 N-1 條邊
最常見的樹狀結構是二元樹, 摘要整理如下 :
一. 二元樹特徵 :
- 二元樹之每一節點分支度 (Degree) <= 2 (最多兩個子節點)
- 二元樹可以為空, 一般的樹不可為空且左右子樹無次序之分
- 非空二元樹具有根結點 (Root) 與左子樹和右子樹 (有次序之分)
- 二元樹最多只能有兩個子節點
二. 各種二元樹 :
- 斜曲二元樹 (skewed binary tree) :
只有左子樹之二元樹為左斜曲 (left-skewed), 而只有右子樹之二元樹為右斜曲 (left-skewed), 此種二元樹適合用鏈結串列實作, 不適合用一維陣列儲存, 因較浪費儲存空間. - 嚴格二元樹 (strictly binary tree) :
若二元樹的每個非終端節點都有非空的左右子樹稱為嚴格二元樹, 亦即每個有子樹的節點不會只有一個子樹, 一定有兩個子樹 (要嘛沒有子節點, 要嘛有兩個子節點). - 完滿二元樹 (strictly binary tree)
高度是 h 的二元樹, 若具有 2**h - 1 個節點, 稱為完滿二元樹, 亦即除最底下一層外, 每一節點均有兩個子節點. 完滿二元樹在第 k 階有 2**(k-1) 個節點. - 完整二元樹 (complete binary tree)
高度是 h 的二元樹, 若節點不是葉節點, 一定有兩個子節點, 稱為完整二元樹. 其節點數 n 滿足 2**(h - 1) < b <= 2**h - 1 之條件.
可見, 完滿二元樹一定是嚴格二元樹; 也一定是完整二元樹; 但完整二元樹不一定是完滿二元樹, 但. 三者關係如下 :
三. 二元樹的資料結構 :
二元樹的資料結構可以使用鏈結串列 (linked list) 或一維陣列表示, 鏈結串列適合用來處理斜曲樹; 而陣列則適合處理完滿樹. 例如下面的三階二元樹, 最多有 2**3-1=7 個節點 (完滿), 因此可宣告一個 A[7] 陣列來儲存節點, 其中 A[0] 不使用, 空缺的節點填入特殊值 (例如 0) :
可見以一維陣列實作二元樹時, 節點與子節點之索引有如下關係 :
- 左子樹索引是其父節點索引的 2 倍
- 右子樹索引是其父節點索引的 2 倍加 1
- 每個節點值不同
- 每個節點的值須大於左子樹之值, 小於右子樹之值
- 左右子樹也是二元樹
五. 二元樹的走訪 :
以陣列表示的二元樹可用下列三種方式走訪 :
- 前序追蹤 (MLR)
- 中序追蹤 (LMR)
- 後序追蹤 (LRM)
下面程式為改寫自 "動畫圖解資料結構第二版" 的完滿二元樹走訪 :
#include <stdio.h>
#include <stdlib.h>
#define Num 20
void CreateBinaryTree(int*, int);
void Postorder(int);
void Inorder(int);
void Preorder(int);
int data[Num]={0};
int BinaryTree[Num]={0};
int main(void) {
int n;
printf("請輸入節點個數：");
scanf("%d", &n);
printf("請輸入這 %d 個節點的內容：\n", n);
for (int i=0; i<n; i++) {
scanf(" %d", &data[i]);
}
CreateBinaryTree(data, n); //呼叫建立二元樹之副程式
printf("二元樹前序追蹤的結果：\n");
Preorder(1); //呼叫前序之副程式
printf("\n");
printf("二元樹中序追蹤的結果：\n");
Inorder(1); //呼叫中序之副程式
printf("\n");
printf("二元樹後序追蹤的結果：\n");
Postorder(1); //呼叫後序之副程式
printf("\n");
system("PAUSE");
return 0;
}
void CreateBinaryTree(int data[], int n) { //建立二元樹
int node=1, temp;
for (int i=0; i<Num; i++) {BinaryTree[i]=0;} //初值設定
for (int i=0; i<n; i++) {
BinaryTree[node]=data[i];
node=node + 1;
}
}
void Postorder(int node) { //後序追蹤
if (BinaryTree[node] != 0) {
Postorder(2*node); //遞迴左子樹
Postorder(2*node+1); //遞迴右子樹
if (BinaryTree[node] != 0) { //列印樹根
printf("%d ",BinaryTree[node]);
}
}
}
void Inorder(int node) { //中序追蹤
if (BinaryTree[node] != 0) {
Inorder(2*node); //遞迴左子樹
if (BinaryTree[node] != 0) { //列印樹根
printf("%d ", BinaryTree[node]);
}
Inorder(2*node+1); //遞迴右子樹
}
}
void Preorder(int node) { //前序追蹤
if (BinaryTree[node]!=0) {
if (BinaryTree[node]!=0) {
printf("%d ",BinaryTree[node]); //列印樹根
}
Preorder(2*node); //遞迴左子樹
Preorder(2*node+1); //遞迴右子樹
}
}
執行結果如下 :
請輸入節點個數：9
請輸入這 9 個節點的內容：
38
78
10
65
19
86
33
72
29
二元樹前序追蹤的結果：
38 78 65 72 29 19 10 86 33
二元樹中序追蹤的結果：
72 65 29 78 19 38 86 10 33
二元樹後序追蹤的結果：
72 29 65 19 78 86 33 10 38
請按任意鍵繼續 . . .
--------------------------------
Process exited with return value 0
Press any key to continue . . .
四. 二元搜尋樹 :
上面的範例僅僅是將資料依序填入陣列中, 如果填入時加入如下規則, 所建立的二元樹稱為二元搜尋樹 :
- 每個節點值不同
- 每個節點的值須大於左子樹之值, 小於右子樹之值
- 左右子樹也是二元樹
#include <stdio.h>
#include <string.h>
void CreateBTree(int btree[], int data[], int n) {
int i, j; //i=原始陣列索引, j=二元搜尋樹陣列索引
btree[1]=data[1]; //以第一個資料為二元樹根節點
for (i=2; i<=n; i++) { //從第二個資料開始拜訪原始陣列
j=1; //二元樹起始索引為根結點=1
while (btree[j] != 0) { //拜訪二元樹陣列直到找到空節點
if (data[i] > btree[j]) { //值較大往右子樹走
j=j*2 + 1; //右子樹節點索引
}
else {j=j*2;} //左子樹節點索引
} //找到二元樹空節點索引就跳出來
btree[j]=data[i]; //將原始陣列元素填入二元樹空節點
}
}
int main(void) {
int length=10;
int data[]={0,5,6,4,8,2,3,7,1,9}; //第一個索引用不到填 0
int btree[16]={0}; //預設 0 表示無任何節點
printf("原始陣列內容:\n");
for (int i=0; i<length; i++) { //顯示原始資料陣列內容
printf("[%d] : %d\n", i, data[i]);
}
printf("\n");
CreateBTree(btree, data, 9); //建立二元搜尋樹
printf("二元樹內容:\n");
for (int i=0; i<16; i++) { //顯示二元搜尋樹料陣列內容
printf("[%d] : %d\n", i, btree[i]);
}
printf("\n");
return 0;
}
執行結果如下 :
原始陣列內容:
[0] : 0
[1] : 5
[2] : 6
[3] : 4
[4] : 8
[5] : 2
[6] : 3
[7] : 7
[8] : 1
[9] : 9
二元樹內容:
[0] : 0
[1] : 5
[2] : 4
[3] : 6
[4] : 2
[5] : 0
[6] : 0
[7] : 8
[8] : 1
[9] : 3
[10] : 0
[11] : 0
[12] : 0
[13] : 0
[14] : 7
[15] : 9
--------------------------------
Process exited after 0.07975 seconds with return value 0
請按任意鍵繼續 . . .
沒有留言:
張貼留言