Download presentation
Presentation is loading. Please wait.
1
樹狀結構 Trees
2
「樹」的定義 樹是一種由節點連結而成 由一個或多個節點所組成的有限集合 具有下列兩個性質的圖形（graph） 相連結(connected)：
節點之間至少必須有一個以上的連結。 非迴圈性(circuit-free)： 點與點之間不能形成無出口的迴圈。
4
樹的範例
5
非樹的範例
6
樹狀結構 (Tree) 樹為非線性之資料結構，資料與資料之間藉由分支(Branch)組成階層式(Hierarchical)之關係。
樹狀結構為一個或多個節點所構成之有限集合，並具有以下之特性： 有一個特定節點稱為樹根 (Root) 其餘節點為分成n個獨立之集合T1,T2,…Tn 其中各個集合為一樹狀結構 T1,T2,…,Tn稱為樹根(Root)之子樹(Sub-tree)
7
二元樹 (Binary Tree)
8
二元樹定義 是一個由有限個節點所組成的集合 可能是空集合，或者是由一個樹根及兩個互斥的二元樹稱為左子樹和右子樹所構成
又稱為Knuth樹，每個節點的分支度≦2 左邊的節點稱為左子樹(Left Child) 右邊的節點稱為右子樹(Right Child) 因其左右有次序之分，故又稱為有序樹(Ordered Tree)。
9
樹與二元樹比較 樹與二元樹主要的不同： 樹不可以為空集合，至少存在一個樹根 樹中每一個節點的分支度(Degree)d≧0
樹的子子樹之間沒有次序關係 而二元樹可以為空集合 而二元樹的每一個節點分支度為0≦d≦2 二元樹之間有次序關係
10
用鏈結串列表示 每個節點的結構如下： 優點：插入與刪除一個節點相當容易。 缺點：很難找到該節點的父點(Parent)。
其中DATA欄存放節點值。 LCHILD欄存放指向其左子樹的指標 RCHILD欄存放指向其右子樹的指標。 優點：插入與刪除一個節點相當容易。 缺點：很難找到該節點的父點(Parent)。 解決方式：在節點的結構上增加一欄PARENT，指向其父點的位置。 LCHILD DATA RCHILD
12
二元樹節點結構表示法 假設有一節點結構如下圖所示：
13
一個指標變數 tree 當作二元樹之樹根指標，其宣告如下：
其節點結構可定義如下： typedef struct tnode { //以結構體表示節點 char data ; //data儲存節點資料項目 struct tnode *left, *right; } TNODE; //儲存左右節點位址 //TNODE表新定義之節點結構資料型態 一個指標變數 tree 當作二元樹之樹根指標，其宣告如下： TNODE *tree； //tree為一個指標，指向一個二元樹之樹根節點
14
二元樹的特例 歪斜樹(Skewed Binary Tree)： 當一個二元樹的所有節點都只有左子點(Left Child)或只有右子點時稱之。
15
完滿二元樹(Full Binary Tree)： 一個二元樹含有的節點數最多時稱之，若階度(level)為k且含有2k-1個節點。
16
完整二元樹(Complete Binary Tree)： 一個二元樹的階度(level)為k，而其所含節點數少於2k-1個，但其節點的編號順序如同完滿二元樹一般時稱之。
17
嚴格二元樹(Strictly Binary Tree)： 若二元樹的每一個非終端節點均有非空的左右子樹時稱之。
向左二元樹(Leftist Binary Tree)： 若二元樹中每一個節點的左子樹節點數目均不少於它右子樹節點數目時稱之。
18
Binary Tree Traversals
二元樹之尋訪 Binary Tree Traversals
19
尋訪的方法 前序(Preorder)： 中序(Inorder) ： 後序(Postorder)： 樹根→左子樹→右子樹(DLR)
左子樹→樹根→右子樹(LDR) 後序(Postorder)： 左子樹→右子樹→樹根(LRD)
20
中序式尋訪(遞迴演算法) 若樹根節點不為空節點，則執行下列步驟： １.走訪左子樹(遞迴)； ２.走訪樹根； ３.走訪右子樹(遞迴)。
void InOrder (TNODE *p) { if ( p != NULL) { InOder(p->left); /*走訪左樹*/ printf(“%c”, p->data); /*走訪列印樹根節點*/ InOder(p->right); /*走訪右樹*/ }
21
後序式尋訪 (遞迴演算法) 若樹根節點不為空節點，則執行下列步驟： １.走訪左子樹(遞迴)； ２.走訪右子樹(遞迴)； ３.走訪樹根。
void PostOrder (TNODE *p) { if ( p != NULL) { PostOder(p->left); /*走訪左樹*/ PostOder(p->right); /*走訪右樹*/ printf(“%c”, p->data); /*走訪列印樹根節點*/ }
22
前序式尋訪(遞迴演算法) 若樹根節點不為空節點，則執行下列步驟： １.走訪樹根； ２.走訪左子樹(遞迴)； ３.走訪右子樹(遞迴)。
void PreOrder (TNODE *p) { if ( p != NULL) { printf(“%c”, p->data); /*走訪列印樹根節點*/ PreOder(p->left); /*走訪左樹*/ PreOder(p->right); /*走訪右樹*/ }
23
【範例一】 試寫出下圖之前序、中序及後序的尋訪順序。 B C E F I D G J H A L K
24
【解析】 前序尋訪： 根 左子樹 右子樹 A BCEIFJDGHKL － 中序尋訪： EICFJBGDKHL 後序尋訪：
IEJFCGKLHDB
25
【範例二】 試寫出下圖之前序、中序及後序的尋訪順序 ＊ ＋ － 4 y 2 3
26
【解析】 前序尋訪： 根 左子樹 右子樹 ± y ＊＋－2＊3y4－＊＋4y2y 中序尋訪： 2－3＊y＋4＊4＋y＊2－y 後序尋訪：
27
以二元樹排序 將原始資料依序加入二元樹中： 對任何節點而言 二元樹建立好之後，只要按中序式方式走訪即可得到排序後由小至大的資料。
其左子樹之值小於樹根的值 其右子樹之值大於樹根的值 二元樹建立好之後，只要按中序式方式走訪即可得到排序後由小至大的資料。
28
以二元樹排序之規則如下： 以第一個資料當作樹根 之後之資料與樹根比較 二元樹建立好之後，再以中序式方式走訪追蹤。
若小於樹根則成為樹根之左子樹 若大於樹根則成為樹根之右子樹 如此一直遞迴之進行。 二元樹建立好之後，再以中序式方式走訪追蹤。
29
【範例】 試以二元樹排序法來排序下列資料 37, 57, 23, 15, 32。
30
【解析】 建立二元樹
31
以中序式方式走訪 追蹤左子樹 拜訪樹根 追蹤右子樹 以中序式方式走訪結果： 左子樹 樹根 右子樹
32
引線二元樹 Thread Binary Tree
33
引線二元樹 為了儲存及節省Link欄的浪費，我們將樹化為二元樹 一個n節點的二元樹，其有2n個Link欄位，實際上只用n-1個
為了充分利用這些空的Link欄位，將空的Link換成一種叫引線(Thread)的指標，指到二元樹的其他節點，即是所謂的引線二元樹。
34
引線二元樹的資料結構 我們必須區別節點中的引線 link 和普通 link，因此每一個節點多了兩個flags(LBIT及RBIT)：
若新節點目前的位置不在根節點上，則與其上的父母節點比較。 如果父母節點的值比較大，則找到了新節點的正確位置 若LCHILD(P)為正常指標，則LBIT(P)=1 若LCHILD(P)為引線，則LBIT(P)=0 若RCHILD(P)為正常指標，則RBIT=1 若RCHILD(P)為引線，則RBIT=0
35
typedef enum {FALSE, TRUE} flag;
typedef struct threaded_tree *threaded_pointer; typedef struct threaded_tree { flag LeftThread; threaded_pointer LChild; char Data; threaded_pointer RChild; flag RightThread; };
36
引線二元樹的製作 我們用以下的步驟將二元樹改換成引線二元樹： 先求二元樹的中序追蹤結果。 將二元樹的所有空鏈結改成引數
若一個節點的左指標為空值的話，則將此左指標設成此節點的中序前節點（inorder predecessor）的位址。 若一個節點的右指標為空值的話，則將此右指標設成此節點的中序後節點（inorder successor）的位址。
37
【範例】 將下面的二元樹加上引線。 A B C E D
38
【解析】 中序追蹤結果如下： D B E A C 將所有空鏈結改成引數。
39
樹轉成二元樹
40
樹化為二元樹的方法 一般採用「Leftmost－＞Child－＞Right－＞Sibling」方式將樹化為二元樹， 其步驟如下：
將節點的所有兄弟用平線連接起來。 刪除所有與子點間的鏈結，祇保留與最左子點間的鏈結。 順時針旋轉45度。
41
【範例】將下面的樹轉換成二元樹 A D I H B E J K L F M C G
42
長子繼承，兄弟左右 A C F G B E D J H I K L M
43
順時針旋轉45度 A C F G B E D J H I K L M
44
二元搜尋樹 Binary Search Tree
45
定義 二元搜尋樹（binary search tree）可以是空集合
假使不是空集合，則樹中的每一節點均含有一鍵值(key value)，且具有下列性質： 在左子樹的所有鍵值均小於樹根的鍵值。 在右子樹的所有鍵值均大於樹根的鍵值。 左子樹和右子樹亦是二元搜尋樹。 每個鍵值都不相同。 中序遊走一個 binary search tree 所產生的 search key value序列是由小至大排列。 若一個 binary search tree 含有 n 個節點，則其高度h 滿足不等式：
47
基本運算及表示法 節點宣告 節點增加
48
節點宣告 Typedef { keyType Key; /* other fields */ } dataType;
typedef sruct node { dataType Data; struct node *Left; struct node *Right; } nodeType, *nodePtr;
49
節點增加 二元搜尋的加入很簡單，因二元搜尋樹的性質是左子樹的鍵值均小於樹根的鍵值，而右子樹的鍵值均大於樹根的鍵值。
加入某一鍵值只要逐一比較，依鍵值的大小往右或往左，即可找到此鍵值欲加入的適當位置
50
其演算的程序及步驟如下： 一次讀入一個數字，直到輸入結束。 如果是空樹，則新節點即為根節點。
如果不是空樹，將新節點資料與根節點比較，如果比較小的話，則往左子樹，否則往右子樹。 重複步驟３，直到空指標為止。 將新節點加到最後停留之處。
51
虛擬碼 Procedure Tree_INSERT(T,Z) Y ← 0 PARENT(Z) ← y If y = 0 then
x ← Root(T) While x ≠ 0 do y ← x if DATA(Z) < DATA(x) x ← LCHILD(x) else x ← RCHILD(x) end if end while PARENT(Z) ← y If y = 0 then ROOT(T) ← Z else if DATA(Z) < DATA(y) LCHILD(y) ← Z RCHILD(y) ← Z end if end TREE_INSERT
52
Ｃ語言：程式碼 #define NEW1(Type) ((Type *) malloc(sizeof(Type)))
Insert (nodePtr Tree, dataType NewItem) { nodePtr *p = &Tree; while (*p != NULL) { if (NewItem.Key < (*p)->Data.Key) p = &((*p)->Left); /*插入左子樹*/ else p = &((*p)->Right); /*插入右子樹*/ } //配置新節點記憶空間 *p = NEW1(nodeType); (*p)->Data = NewItem; (*p)->Left = NULL; (*p)->Right = NULL;
53
【範例】假設有一棵二元搜尋樹如下 50 40 65 45 30
54
今欲加入48 依上述規則加在鍵值45的右邊 因為48比50小，故往左邊 但比40大往右邊 最後又比45大，故加在45的右邊。 50 65
60 48 50 40 65 45 30
55
繼續加入90則為 48 60 90 50 40 65 45 30
56
節點的刪除 刪除某一節點時，若刪除的是樹葉節點，則直接刪除之，假若刪除的不是樹葉節點，則在左子樹找一最大的節點或在右子樹找一最小的節點。
57
【範例】 50 40 65 45 30
58
刪除50，則可用下列二種方法之一： 取右子樹最子的節點 60 40 65 45 30
59
或是取左子樹最子的節點 45 40 65 60 30
60
（Binary Expression Tree）
二元運算樹 （Binary Expression Tree）
61
定義 除了正負號之外，其他的運算子都是二元運算子 其中內部節點一定是運算子 左右子樹就是該運算子的二個運算元
這些運算元可能是純資料或是由資料加上運算子所組成的 外部節點則是單純資料值
63
建立二元運算樹 一棵運算樹的內部節點為運算子 外部節點則為純資料的運算元 通常運算子的資料型態為字元(＋、－、＊、/) 運算元的型態則為數值
64
如何將不同的算術式轉換為二元運算樹，其原則如下：
優先權最低的運算子當根 左右運算符號的優先權一樣時，先計算的運算子其優先權較高。例如括號內的優先權最高。
65
假設欲將Y = ((A+((B/C)-D))*(E*(F+G)))算術式，轉換成樹狀結構，建立一個二元運算樹，其結果如下圖所示：
＝ ＊ ＋ A － E F G Y D / C B
Similar presentations
