1

Size: px

Start display at page:

Download "1"

琦底谢
6 years ago
Views:

1 基本練習題 1. 請將下面的二元樹表示成一維陣列 A B C D E F G 答 : [0] [1] [2] [3] [4] [5] [6] [7] [11] A B C D E F G 2. 將上題的二元樹表示成二維陣列答 : [0] [1] [2] [0] A 1 2 [1] B 3 0 [2] C 4 5 [3] D 0 0 [4] E 6 0 [5] F 0 0 [6] G 將第 1 題的二元樹表示成鏈結節點答 : A B C D E F G

2 4. 若輸入資料為 ABD0E000C0FG00H00, 請建立二元樹答 : A B C D F E G H 5. 有一棵二元樹如下 : A B C D E F G H I J A. 請作前序走訪, 列出走訪節點的順序 B. 請作中序走訪, 列出走訪節點的順序 C. 請作後序走訪, 列出走訪節點的順序答 : A. 前序走訪順序 :A B D G E H C F I J B. 中序走訪順序 :G D B E H A C I F J C. 後序走訪順序 :G D H E B I J F C A 6. 若輸入資料為 :61, 23, 40, 71, 88, 32, 47, 56, 62, 38 請建立二元搜尋樹答 :

3 同上題, 同樣的資料但順序改為 71, 88, 61, 32, 47, 56, 38, 62, 40, 23, 請建立二元搜尋樹, 並且與上題作比較答 : 兩棵樹顯然是不同的二元樹雖然有同樣的資料, 但是如果順序不同, 將會造成不同的二元搜尋樹 8. 同第 6 題, 若搜尋鍵值為 47, 請列出比較的過程答 : 1. 鍵值 47 和樹根資料 61 相比 47 比 61 小, 因此往左子樹 2. 鍵值 47 和資料 23 相比,47 比 23 大, 往右子樹 3. 鍵值 47 和資料 40 相比,47 比 40 大, 往右子樹 4. 鍵值 47 和資料 47 相比, 相等, 搜尋成功 9. 同第 6 題, 若刪除節點 40, 請畫出刪除後的二元搜尋樹答 :

4 進階練習題 1. 若輸入資料為 :61, 23, 40, 71, 88, 32, 47, 56, 62, 38 請建立 AVL 樹答 : 同上題, 若刪除節點 40, 請畫出刪除後的 AVL 樹答 :

5 3. 輸入資料同第 1 題, 請建立 2 3 樹答 : 高度為 k 的二元樹, 最少有幾個節點? 最多有幾個節點? 答 : 最少有 k 個節點 ( 每階只有一個 ) 最多有 2 k - 1 個節點 ( 完滿二元樹 ) 5. 具有 n 個節點的二元樹, 高度最多為何? 高度最少為何? 答 : 高度最高為 n( 每階只有一個 ) 高度最少為 lg n + 1 個節點 ( 完整二元樹 ) 6. 高度為 h 的 d 元樹, 至多可包含多少節點? 請推導之答 : 第 1 階最多 1 個, 第 2 階最多 d 個, 第 3 階最多 d 2 (d 3-1 ) 個,, 第 i 階最多 d i-1 個, h i= 1 d i 1 = 1 + d + d d h-1 = d h 請比較完滿二元樹完整二元樹正規二元樹之異同答 : 完滿二元樹 (full binary tree): 高度為 k, 而且總節點數為 2 k -1 的二元樹完整二元樹 ( complete binary tree): 第 k 階滿了才能排到第 k+1 階, 並且每一階的節點都是往左靠亦即, 如果我們由樹根開始編號 0 號, 由上而下, 由左而右地編號, 一階滿了再往下一階編號, 因為中間沒有空號, 所以稱為完整二元樹正規二元樹 (formal binary tree): 所有內部節點都正好有兩個子節點完滿二元樹一定是完整二元樹, 也一定是正規二元樹反之不然 8. 請將下面的二元樹表示成引線二元樹 ( 引線以虛線表示 )

6 A B C D E F G 答 : H J A B C D E F G H J 9. 何謂二元搜尋樹?AVL 樹? 答 : AVL 樹 : 對所有內部節點而言, 其左子樹高度和右子樹高度, 相差的絕對值小於等於 1 二元搜尋樹 : 對所有內部節點而言, 其左子樹所有節點的資料值, 都小於此節點的資料值, 它的右子樹所有節點的資料值, 都大於它的資料值 10. 何謂 m 元搜尋樹? B 樹? 答 : m 元搜尋樹 : 與二元搜尋樹類似, 但最多可有 m 個鏈結, 亦即每個節點最多有 m 個子樹, 同時符合下列性質 : 1. K1 < K2 < < Ki < K i+1 < < Kn, 亦即鍵值遞增排列 2. L0 所指的子樹的所有節點, 鍵值都小於 K1, L1 所指的子樹的所有節點, 鍵值都介於 K1 和 K2 之間,Li 所指的子樹的所有節點, 鍵值都介於 Ki 和 K i+1 之間 Ln 所指的子樹的所有節點, 鍵值都大於 Kn B 樹是符合下列性質的 m 元搜尋樹 :

7 1. 每個節點至多有 m 個子樹 2. 樹根至少有 2 個子樹, 除非它也是樹葉 3. 除了樹根和樹葉之外, 其餘的內部節點, 至少有 m / 2 子樹 4. 所有的樹葉都在同一階, 亦即從樹根到任一個樹葉所經過的路徑長度均相同 11. 何謂 2 3 樹?2 3 4 樹? 紅黑樹? 答 : 2 3 樹 : 就是 3 階的 B 樹 ( B tree of order 3 ) 因此在 2 3 樹上的每個節點最多有 2 個鍵值 3 個指標具有 1 個鍵值 (2 個指標 ) 的節點稱為 2-node (2- 節點 ), 具有 2 個鍵值 (3 個指標 ) 的節點稱為 3-node (3- 節點 ) 樹 : 就是 4 階的 B 樹 ( B-tree of order 4 ) 因此在樹上的每個節點最多有 3 個鍵值 4 個指標具有 1 個鍵值 (2 個指標 ) 的節點稱為 2-node (2- 節點 ), 具有 2 個鍵值 (3 個指標 ) 的節點稱為 3-node (3- 節點 ), 具有 3 個鍵值 (4 個指標 ) 的節點稱為 4-node (4- 節點 ) 紅- 黑樹 : 是樹的二元樹表示法每個節點有 2 個指標, 並且每個指標有 2 種形式 : 紅指標及黑指標在畫出紅- 黑樹時, 通常以實線表示黑指標, 以虛線表示紅指標 12. 若要編碼一篇文章, 字母及出現頻率分別為 :A / 8, B / 31, C / 12, D / 21, E / 5, F / 23 A. 請畫出 Huffman 樹 B. 各字母的編碼為何? C. 若有一篇 5000 字的文章, 共需多少位元? D. 若原來每個字母均需 3 個位元, 則編碼後壓縮率為多少? 答 : A B D 21 F C A 8 E 5

8 B. A 的編碼 = 0000 B 的編碼 = 01 C 的編碼 = 001 D 的編碼 = 10 E 的編碼 = 0001 F 的編碼 = 11 C. 5000/100*(8*4 + 31* *3 + 21*2 + 5*4 + 23*2 )= D. ( )/15000 *100% = 20 % 程式題 1. 請寫一個完整程式 : A. 從檔案或鍵盤輸入資料建立一棵二元樹 B. 對此二元樹做前序中序及後序走訪, 列出走訪節點的順序答 : #include <stdio.h> #include <conio.h> #include <stdlib.h> typedef struct Tnode struct Tnode *left_c; char data; struct Tnode *right_c; NODE; NODE *tree; FILE *fin; NODE *crt_bt(); void preorder(),inorder(),postorder(); void main(void) if ((fin=fopen("tree.dat","r"))==null) printf("tree.dat Not Found!"); exit(1);

9 tree=crt_bt(); fclose(fin); printf("\n 前序走訪結果 => "); preorder(tree); printf("\n 中序走訪結果 => "); inorder(tree); printf("\n 後序走訪結果 => "); postorder(tree); printf("\n"); NODE *crt_bt() NODE *ptr; char data; fscanf(fin,"%c",&data); if(data == '0') return (NULL); ptr=(node *)malloc(sizeof(node)); ptr->data=data; ptr->left_c=crt_bt(); ptr->right_c=crt_bt(); return(ptr); void visit(node *p) printf("%c",p->data); void visit2(node *p) printf("%c",p->data);

10 free(p); void preorder(node *p) if(p!= NULL) visit(p); preorder(p->left_c); preorder(p->right_c); void inorder(node *p) if(p!= NULL) inorder(p->left_c); visit(p); inorder(p->right_c); void postorder(node *p) if(p!= NULL) postorder(p->left_c); postorder(p->right_c); visit2(p); 2. 寫一函式, 在引線二元樹上作中序走訪答 : #include <stdio.h>

11 #include <malloc.h> #define THREAD 1 #define POINTER 0 #define TRUE 1 #define FALSE 0 #define LEFT 1 #define RIGHT 0 typedef struct tagnode char left_thread; struct tagnode *left_c; int data; char right_thread; struct tagnode *right_c; tnode; void TBTCreate(); void TBTInsert(); tnode *InorderSuccessor(tNODE *); void TBTInorder(tNODE *); void visit(); void main(void) tnode ThreadBT; ThreadBT.left_thread=THREAD; ThreadBT.right_thread=POINTER; ThreadBT.right_c = ThreadBT.left_c = &ThreadBT; TBTCreate(&ThreadBT); printf("the nodes of a Threaded Binary Tree are (inorder) :\n"); TBTInorder(&ThreadBT); printf("\n"); void visit(tnode *p) printf(" %d ",p->data);

12 tnode *InorderSuccessor(tNODE *p) if (p->right_thread == THREAD) p=p->right_c; p=p->right_c; while (p->left_thread == POINTER) p=p->left_c; return(p); void TBTInorder(tNODE *TBT) tnode *p=tbt; while ( (p=inordersuccessor(p))!= TBT) visit(p); int TestLeaf(tNODE *p,int Direction) if (Direction ==LEFT ) if (p->left_thread == THREAD) return TRUE; return FALSE; if (p->right_thread == THREAD) return TRUE; return FALSE;

13 void TBTInsert(tNODE *TBT,tNODE *p) tnode *r=tbt->left_c; int Dir,FlagLeaf=FALSE; if (r==tbt) // only Head r->left_thread =POINTER; r->left_c = p; p->right_c = r; return; FlagLeaf=FALSE; do if (p->data < r->data) Dir = LEFT; if (!TestLeaf(r,Dir)) r=r->left_c; FlagLeaf=TRUE; Dir =RIGHT; if (!TestLeaf(r,Dir)) r=r->right_c; FlagLeaf=TRUE; while (!FlagLeaf ); if ( Dir == LEFT ) p->right_c = r; p->left_c = r->left_c; r->left_c = p; r->left_thread = POINTER;

14 p->left_c = r; p->right_c = r->right_c; r->right_c = p; r->right_thread = POINTER; void TBTCreate(tNODE *TBT) FILE *filedata; int data; tnode *p; filedata=fopen("tbt.dat","r"); while(fscanf(filedata,"%d",&data)!= EOF) p=(tnode *)malloc(sizeof(tnode)); p->left_thread = p->right_thread = THREAD; p->data=data; TBTInsert(TBT,p); 3. 請寫一個完整程式 : A. 從檔案讀入資料建立二元搜尋樹 B. 提供插入刪除搜尋等功能, 供使用者選擇答 : #include <stdio.h> #include <stdlib.h> typedef struct ttnode struct ttnode *left_c; int data; struct ttnode *right_c; tnode;

15 tnode *lista; tnode *bst_create(),*bst_insert(),*bst_search(),*bst_delete(); void inorder(); void visit(); void main(void) tnode *p; int choose,data; lista=bst_create(); while(1) printf("\nbst 中序 : "); inorder(lista); printf("\n(1) 插入資料 \n(2) 搜尋資料 \n(3) 刪除資料 \n(0) 結束 =>"); scanf("%d",&choose); switch(choose) case 0: case 1: case 2: exit(0); /* 結束程式 */ printf(" 請輸入欲加入之資料 =>"); scanf("%d",&data); if(bst_search(lista,data)!= NULL) printf("!!! 資料已存在!!!"); p=malloc(sizeof(tnode)); p->data=data; lista=bst_insert(lista,p); printf("@ 加入成功!"); break;

16 case 3: printf(" 請輸入欲搜尋之資料 =>"); scanf("%d",&data); if(bst_search(lista,data) == NULL) printf("!!! 找不到資料!!!"); 找到!"); break; printf(" 請輸入欲刪除之資料 =>"); scanf("%d",&data); default: if(bst_delete(lista,data) == NULL) printf("!!! 刪除位置錯誤失敗!!!"); 刪除完成!"); break; printf(" 選項錯誤 "); void visit(tnode *p) printf("%d ",p->data); void inorder(tnode *p) if(p!= NULL) inorder(p->left_c); visit(p); inorder(p->right_c);

17 tnode *bst_insert(tnode *t,tnode *p) tnode *r,*q; char direction; p->left_c=p->right_c=null; if(t == NULL) t=p; q=t; while(q!= NULL) if(p->data < q->data) direction=1; r=q; q=q->left_c; if(p->data > q->data) direction=0; r=q; q=q->right_c; return(t); if (direction==1) r->left_c=p; r->right_c=p; return(t); tnode *bst_create(void)

18 FILE *filedata; int data; tnode *t,*p; filedata=fopen("bst.dat","r"); t=null; while( fscanf(filedata,"%d",&data)!= EOF) p=malloc(sizeof(tnode)); p->data=data; t=bst_insert(t,p); return(t); tnode *bst_search(tnode *t,int key) while(t!= NULL) if(key == t->data) return(t); if(key < t->data) t=t->left_c; t=t->right_c; return(null); tnode *bst_delete(tnode *p,int key) int found=0,direction=0; tnode *r,*q,*s,*t;

19 r=q=s=null; t=p; while(p!=null &&!found) if(key == p->data) found=1; if(key < p->data) direction=1; r=p; p=p->left_c; direction=0; r=p; p=p->right_c; if(p == NULL) return(null); if(r == NULL) if(p->right_c == NULL) return(p->left_c); if(p->left_c == NULL) return(p->right_c); if(p->right_c == NULL) if(direction == 1) r->left_c=p->left_c; r->right_c=p->left_c; if(p->left_c == NULL)

20 if(direction == 1) r->left_c=p->right_c; r->right_c=p->right_c; s=p; q=p->left_c; while(q->right_c!= NULL) s=q; q=q->right_c; p->data=q->data; if(p == s) s->left_c=q->left_c; s->right_c=q->left_c; return(t);

Tree

Tree 樹狀結構 Tree 講師 : 洪安大綱樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree) 課堂練習 2 樹樹 (Tree) 是一種模擬現實生活中樹幹和樹枝的資料結構, 屬於一種階層架構的非線性資料結構, 例如 : 家族族譜, 決策模型 3 樹的基本術語樹的樹根稱為根節點 (Root), 在根節點之下是樹的樹枝, 擁有 0 到 n 個