Trees 授課者:驕芸.

Presentation on theme: "Trees 授課者:驕芸."— Presentation transcript:

1 Trees 授課者:驕芸

2 Outline Tree Binary Tree Delete Nodes from Binary Tree
Thread Binary Tree

3 Tree 定義:由一個或多個節點構成的有限集合。 特性: 常用術語: 有一特定節點稱為樹根(Root)
其餘的節點之集合稱為子樹(Subtree) 常用術語: Root:沒有父節點的節點 Leaf:沒有子節點的節點 Sibling:同一個父節點的所有子節點 Ancestors:從該節點至root所經過的所有節點 Degree(分支度):該節點所擁有的子節點數 Non-terminal Node:非樹葉的節點, 即degree>=1的節點

4 Tree 術語: Level(階層):樹根的階層為1，若某節點的階層為i，則子節點的階層就為i+1
Height(高度或深度):一棵樹所具有的最大階層. level 1 2 3 A B C D E F G

5 Binary Tree 節點個數是有限的，且可以沒有節點。 二元樹可以分為兩個子樹稱為左子樹與右子樹。
左、右子樹亦是二元樹。 又稱為有序樹，每一個節點之degree<=2，左右有次序之分。 表示法: 陣列 結構陣列 鏈結結構(hw1)

6 Binary Tree表示法---陣列 左子樹是父節點乘以2 右子樹是父節點乘以2+1 演算法步驟: 1.將第一個元素插入為 根節點。
儲存位置 左子樹是父節點乘以2 右子樹是父節點乘以2+1 演算法步驟: 1.將第一個元素插入為 根節點。 2.將插入的元素與節點值比較，若大於大於節點值，將此元素送往節點的右子樹，若右子樹不是空的，則需要重複比較，否則建立節點且將元素值插入。 3.若小於節點值，將此元素送往節點的左子樹，類似上述法。 level 1 2 3 [1] [3] [2] [4] [5] [6]

7 Binary Tree陣列表示法---範例
將下列資料依序輸入一個二元樹，則建立的二元樹如下圖: 15,6,4,8,23,77,1,19 (1) 15 (2) (3) 6 23 (4) (5) (6) (7) 4 8 19 77 (8) 1

8 Binary Tree陣列表示法---程式碼
#include<stdio.h> #include<stdlib.h> void createbtree(int *btree,int *data,int len) { int level; /*樹的階層*/ int i; btree[1] = data[0]; /*建立根節點*/ for ( i = 2; i <= len; i++ ) /*用迴路建立其 它節點*/ { level = 1; /*從階層1開始*/ while ( btree[level] != 0 ) /*是否有子樹*/ if ( data[i-1] > btree[level] ) /*是左或右子 樹*/ level = level * 2 + 1; /*右子樹*/ else level = level * 2; /*左子樹*/ } btree[level] = data[i-1]; /*存入節點資料*/ int main() { int btree[16]; /* 二元樹陣列*/ /* 二元樹節點資料 */ int data[8]={15,6,4,8,23,77,1,19}; int i; for( i = 1; i < 16; i++ ) /*清除二元樹陣列*/ btree[i]=0; createbtree(btree,data,8); /*建立二 元樹*/ for( i =1; i <16;i++) /*列出二元樹內容*/ printf("%2d: [%d] \n",i,btree[i]); system("pause"); return 0; } btree[16], 宣告為16的原因: 因為此binary tree是四層, 所以最多會有2^4-1=15個節點 因為節點建立從index為1開始, 會浪費掉1個空間

9 Binary Tree表示法---結構陣列
每個節點至多擁有兩個子節點與一個資料欄位. 結構宣告如下圖所示: struct tree { int data; int left; int right; }; typedef struct tree treenode; treenode btree[15]; left data right

10 結構陣列表示法 index left data right 1 15 2 -1 6 23 3 77 (0) 15 (1) (2) 6 23
1 15 2 -1 6 23 3 77 (0) 15 (1) (2) 6 23 (3) 77 Index為0表示樹根 Left欄位是-1,表示沒有左子樹 Right欄位是-1,表示沒有右子樹

11 Binary Tree結構陣列表示法---程式碼1/2
for(i=1;i<len;i++) /*用迴路建立其它節點*/ { btree[i].data = data[i]; /* 建立節點內容*/ level=0; /*從樹根開始*/ pos=0; /*設定pos值*/ while(pos==0) /*用迴路找節點位置*/ { /*比較是左或右子樹*/ if(data[i]>btree[level].data ) { /*右樹是否有下一階層*/ if(btree[level].right!=-1) level = btree[level].right; else pos = -1; /*是右子樹*/ } { /*左樹是否有下一階層*/ if ( btree[level].left != -1 ) level = btree[level].left; pos = 1; /*是左子樹*/ if ( pos == 1 ) /*建立節點左右位置*/ btree[level].left = i; /*鏈結左子樹*/ btree[level].right = i; /*鏈結右子樹*/ #include <stdlib.h> struct tree /*樹的結構宣告*/ { int data; /*節點資料*/ int left; /*指向左子樹的位置*/ int right; /*指向右子樹的位置 */ }; typedef struct tree treenode; /*樹的結構新型 態*/ treenode btree[15]; /*宣告樹的結構陣列*/ void createbtree(int *data,int len) int level; /*樹的階層*/ int pos; /* -1是右樹,1是左樹 */ int i; btree[0].data = data[0]; /* 建立樹根節點*/

12 Binary Tree結構陣列表示法---程式碼2/2
void main() { /* 二元樹節點資料 */ int data[8] = {15,6,4,8,23,77,1,19}; int i; for ( i = 0; i < 15; i++ ) /*清除樹狀結構陣列*/ { btree[i].data = 0; /*設定初始內容*/ btree[i].left = -1; /*設定初始內容*/ btree[i].right = -1; /*設定初始內容*/ } createbtree(data,8); /*建立二元樹*/ printf(" 左 資料 右\n"); printf(" \n"); for ( i = 0; i < 15; i++ ) /*列出二元樹內容*/ if ( btree[i].data != 0 ) /*是否是樹的節點*/ printf("%2d:[%2d] [%2d] [%2d]\n",i,btree[i].left, btree[i].data,btree[i].right); system("pause");

13 Binary Tree表示法---鏈結結構
使用動態記憶體配置建立二元樹。 使用節點結構的左、右指標欄位來表示父和子節點。 結構宣告如右圖所示: struct tree { int data; struct tree *left; struct tree *right; }; typedef struct tree treenode; typedef treenode *btree; data left right

14 鏈結結構表示法 15 15,6,23,77 6 23 null null null 77 null null

15 Delete Nodes from Binary Tree
刪除節點後,依然滿足二元樹的資料排列原則,可分三種情況: 1.節點沒有左子樹 2.節點沒有右子樹 3.節點有左和右子樹

16 節點沒有左子樹 沒有左子樹的二元樹 刪除根節點: 刪除葉節點: 刪除中間節點: 改變根節點的指標 將其父節點指向null root root
5 6 9 18 7 null null null null

17 節點沒有右子樹 沒有右子樹的二元樹 刪除根節點: 刪除葉節點: 刪除中間節點: 改變根節點的指標 將其父節點指向null root 10 8
5 7 6 null null null null

18 節點有左和右子樹1/2 刪除根節點: 在左右子樹中,找尋一個節點,可使整棵二元樹搬移動作最少者.
root 刪除根節點: 在左右子樹中,找尋一個節點,可使整棵二元樹搬移動作最少者. Ex.刪除節點6, 可在節點4與8的範圍中, 找尋一節點, 即可找尋4的右子樹或8的左子樹, 以樹葉節點尤佳. 6 8 4 3 5 9 7 1 null 20 null null null null null null null

19 節點有左和右子樹2/2 刪除沒有左節點或沒有右節點的節點: Ex.刪除節點4 root 5 8 4 3 null 9 7 1 20 null

20 Thread Binary Tree 充分利用空的鏈結欄位，使其指到其他的節點，這些指標稱為thread，而這種二元樹就稱為Thread Binary Tree. 當右子樹為空的，將指標指向中序走訪的下一個節點。 當左子樹為空的，將指標指向中序走訪的前一個節點。

21 Thread Binary Tree範例 Binary Tree Thread Binary Tree 5 5 4 6 4 6 2 8 2
1 3 1 3 7 9 7 9 中序走訪的結果:1, 2, 3, 4, 5, 6, 7, 8, 9

22 Thread Binary Tree宣告 struct thread_tree { int data; int leftthread;
int rightthread; struct tree *left; struct tree *right; }; typedef struct thread_tree treenode; typedef treenode *thread; leftthread data rightthread left right

23 開頭結點 1 5 4 1 1 6 2 8 1 7 1 1 3 1 9