2018年6月7日 星期四

C 語言學習筆記 : 二元樹

今天看完 "動畫圖解資料結構第二版" 第六章的樹狀結構,  這本書真的很不錯, 以大量圖表扼要說明, 還有 CD-ROM 電子書輔助. 不過書中使用類似 Pascal 的虛擬語言來表示演算法, 而用六種程式語言實作的範例則是放在光碟裡.

此外, 我還參考了下列書籍 :
  1. 資料結構-使用 C 語言 (松崗, 陳會安)
  2. 圖說演算法-使用 C 語言 (博碩, 吳燦銘 & 胡昭民)
  3. 啊哈! 圖解演算法必學基礎 (碁峰, 紀磊)
樹狀結構主要有下列成分組成 :
  1. 樹根 (Root) : 最上層節點 (無父節點) 為根節點
  2. 節點 (Node) : 每一筆資料即為一個節點
  3. 葉節點 (Leaf Node) : 沒有子節點的節點, 即終端節點
  4. 子樹 (Subtree) : 節點以下與該節點相連的結構
  5. 樹林 (Forest) : 去除樹根後的結構稱為樹林




樹狀結構有三個主要參數 :
  1. 階度 (Level) : 節點在樹狀結構之階層位置, 樹根之階度為 1. 
  2. 高度 (Height) : 樹的最高階度稱為高度. 
  3. 分支度 (Degree) : 一個節點的子樹個數稱為其分支度. 二元樹節點分支度最多為 2.

樹 (Tree) 其實是圖 (Graph) 的一種特例, 它是一種無迴路 (loopless) 的無向圖, 常見的應用是家譜, 組織架構, 目錄, 或者是檔案總管的資料夾等等. 樹的特徵如下 :
  1. 任意兩節點僅有一條路徑.
  2. N 個節點的樹剛好有 N-1 條邊

最常見的樹狀結構是二元樹, 摘要整理如下 :

一. 二元樹特徵 : 
  1. 二元樹之每一節點分支度 (Degree) <= 2 (最多兩個子節點)
  2. 二元樹可以為空, 一般的樹不可為空且左右子樹無次序之分
  3. 非空二元樹具有根結點 (Root) 與左子樹和右子樹 (有次序之分)
  4. 二元樹最多只能有兩個子節點

二. 各種二元樹 :
  1. 斜曲二元樹 (skewed binary tree) :
    只有左子樹之二元樹為左斜曲 (left-skewed), 而只有右子樹之二元樹為右斜曲 (left-skewed), 此種二元樹適合用鏈結串列實作, 不適合用一維陣列儲存, 因較浪費儲存空間. 
  2. 嚴格二元樹 (strictly binary tree) :
    若二元樹的每個非終端節點都有非空的左右子樹稱為嚴格二元樹, 亦即每個有子樹的節點不會只有一個子樹, 一定有兩個子樹 (要嘛沒有子節點, 要嘛有兩個子節點).
  3. 完滿二元樹 (strictly binary tree)
    高度是 h 的二元樹, 若具有 2**h - 1 個節點, 稱為完滿二元樹, 亦即除最底下一層外, 每一節點均有兩個子節點. 完滿二元樹在第 k 階有 2**(k-1) 個節點. 
  4. 完整二元樹 (complete binary tree)
    高度是 h 的二元樹, 若節點不是葉節點, 一定有兩個子節點, 稱為完整二元樹. 其節點數 n 滿足 2**(h - 1) &lt b &lt= 2**h - 1 之條件.    

可見, 完滿二元樹一定是嚴格二元樹; 也一定是完整二元樹; 但完整二元樹不一定是完滿二元樹, 但. 三者關係如下 :

嚴格二元樹 <= 完整二元樹 <= 完滿二元樹






三. 二元樹的資料結構 : 

二元樹的資料結構可以使用鏈結串列 (linked list) 或一維陣列表示, 鏈結串列適合用來處理斜曲樹; 而陣列則適合處理完滿樹. 例如下面的三階二元樹, 最多有 2**3-1=7 個節點 (完滿), 因此可宣告一個 A[7] 陣列來儲存節點, 其中 A[0] 不使用, 空缺的節點填入特殊值 (例如 0) :




可見以一維陣列實作二元樹時, 節點與子節點之索引有如下關係 :
  1. 左子樹索引是其父節點索引的 2 倍 
  2. 右子樹索引是其父節點索引的 2 倍加 1
利用這兩個規律即可在陣列中建立二元樹, 若加上下列規則, 則可建立二元搜尋樹 :
  1. 每個節點值不同
  2. 每個節點的值須大於左子樹之值, 小於右子樹之值
  3. 左右子樹也是二元樹
以 28, 23, 35, 41, 22, 23 這組資料為例, 其二元搜尋樹如下 :





五. 二元樹的走訪 : 

以陣列表示的二元樹可用下列三種方式走訪 :
  1. 前序追蹤 (MLR)
  2. 中序追蹤 (LMR)
  3. 後序追蹤 (LRM)
其中 M 表示 Middle (樹根), L 表示 Left (左子樹), R 表示 Right (右子樹).

下面程式為改寫自 "動畫圖解資料結構第二版" 的完滿二元樹走訪 :

#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 . . .



四. 二元搜尋樹 : 

上面的範例僅僅是將資料依序填入陣列中, 如果填入時加入如下規則, 所建立的二元樹稱為二元搜尋樹 : 
  1. 每個節點值不同
  2. 每個節點的值須大於左子樹之值, 小於右子樹之值
  3. 左右子樹也是二元樹
範例程式如下 :

#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
請按任意鍵繼續 . . .

沒有留言 :