树与二元树ppt课件

《树与二元树ppt课件》由会员分享，可在线阅读，更多相关《树与二元树ppt课件（73页珍藏版）》请在金锄头文库上搜索。

1、第第7章章 樹與二元樹樹與二元樹Trees and Binary Trees7-1 樹的根本觀念7-2 二元樹的基礎7-3 二元樹的表示法7-4 二元樹的走訪7-5 二元搜尋樹7-6 引線二元樹7-7 樹的二元樹表示法7-8 二元樹的應用 - 運算式處理7-1 樹的根本觀念樹的根本觀念-說明說明樹樹TreesTrees是一種模擬現實生活中樹幹和樹是一種模擬現實生活中樹幹和樹枝的資料結構，屬於一種階層架構的非線性資料枝的資料結構，屬於一種階層架構的非線性資料結構，例如：家族族譜，如下圖所示：結構，例如：家族族譜，如下圖所示：7-1 樹的根本觀念樹的根本觀念-架構架構1樹的樹根稱為根節點樹的樹根稱

2、為根節點 RootRoot ，在根節點之下，在根節點之下是樹的樹枝，擁有是樹的樹枝，擁有0 0到到n n個子節點個子節點 ChildrenChildren ，即樹的分支即樹的分支 BranchBranch ，節點，節點A A是樹的根節點，是樹的根節點，B B、C C、D.D.和和H H是節點是節點A A的子節點，即樹枝，如的子節點，即樹枝，如下圖所示：下圖所示：7-1 樹的根本觀念樹的根本觀念-架構架構2在樹枝下還可以擁有下一層樹枝，在樹枝下還可以擁有下一層樹枝，I I和和J J是是B B的子節的子節點，點，K K、L L和和MM是是E E的子節點，節點的子節點，節點B B是是I I和和J J

3、的父的父節點節點 ParentParent ，節點，節點E E是是K K、L L和和MM的父節點，節的父節點，節點點I I和和J J擁有共同父節點，稱為兄弟節點擁有共同父節點，稱為兄弟節點 SiblingsSiblings ，K K、L L和和M M 是兄弟節點，是兄弟節點，B B、CC和和H H節節點也是兄弟節點，如下圖所示：點也是兄弟節點，如下圖所示：7-1 樹的根本觀念樹的根本觀念-定義定義定義定義 7.1 7.1：樹的節點個數是一或多個有限集合，且：樹的節點個數是一或多個有限集合，且：(1) (1) 存在一個節點稱為根節點。存在一個節點稱為根節點。(2) (2) 在根節點下的節點分成在

4、根節點下的節點分成n = 0 n = 0 個沒有交集的多個個沒有交集的多個子集合子集合t1t1、t2, tnt2, tn，每一個子集合也是一棵樹，而，每一個子集合也是一棵樹，而這些樹稱為根節點的子樹這些樹稱為根節點的子樹 SubtreeSubtree 。樹在各節點之間不可以有迴圈，或不連結的左、右子樹在各節點之間不可以有迴圈，或不連結的左、右子樹，如下圖所示：樹，如下圖所示：7-1 樹的根本觀念樹的根本觀念-相關術語相關術語1n n元樹：樹的一個節點最多擁有元樹：樹的一個節點最多擁有n n個子節點。個子節點。二元樹二元樹Binary TreesBinary Trees：樹的節點最多只需兩個：樹

5、的節點最多只需兩個子節點。子節點。根節點根節點RootRoot：沒有父節點的節點是根節點。：沒有父節點的節點是根節點。例如：節點例如：節點A A。葉節點葉節點LeafLeaf：節點沒有子節點的節點稱為葉：節點沒有子節點的節點稱為葉節點。例如：節點節點。例如：節點I I、J J、C C、D D、K K、L L、MM、F F、GG和和H H。祖先節點祖先節點AncenstorsAncenstors：指某節點到根節點之：指某節點到根節點之間所經過的一切節點，都是此節點的祖先節點。間所經過的一切節點，都是此節點的祖先節點。7-1 樹的根本觀念樹的根本觀念-相關術語相關術語2非終端節點非終端節點Non-

6、terminal NodesNon-terminal Nodes：除了葉節：除了葉節點之外的其它節點稱為非終端節點。例如：節點點之外的其它節點稱為非終端節點。例如：節點A A、B B和和E E是非終端節點。是非終端節點。分支度分支度DregreeDregree：指每個節點擁有的子節點數。：指每個節點擁有的子節點數。例如：節點例如：節點B B的分支度是的分支度是2 2，節點，節點E E的分支度是的分支度是3 3。階層階層LevelLevel：假设樹根是：假设樹根是1 1，其子節點是，其子節點是2 2，依，依序可以計算出樹的階層數。例如：上述圖例的節序可以計算出樹的階層數。例如：上述圖例的節點點A

7、 A階層是階層是1 1，B B、C C到到H H是階層是階層2 2，I I、J J到到MM是階層是階層3 3。樹高樹高HeightHeight：樹高又稱為樹深：樹高又稱為樹深DepthDepth，指，指樹的最大階層數。例如：上述圖例的樹高是樹的最大階層數。例如：上述圖例的樹高是3 3。7-2 二元樹的基礎二元樹的基礎-定義定義樹依不同分支度可以區分成很多種，在資料結構樹依不同分支度可以區分成很多種，在資料結構中最廣泛运用的樹狀結構是二元樹中最廣泛运用的樹狀結構是二元樹Binary Binary TreesTrees，二元樹是指樹中的每一個節點，二元樹是指樹中的每一個節點NodesNodes最多

8、只能擁有最多只能擁有2 2個子節點，即分支度小於個子節點，即分支度小於或等於或等於2 2。二元樹的定義如下所示：二元樹的定義如下所示：定義定義 7.2 7.2：二元樹的節點個數是一個有限集合，或：二元樹的節點個數是一個有限集合，或是沒有節點的空集合。二元樹的節點可以分成兩是沒有節點的空集合。二元樹的節點可以分成兩個沒有交集的子樹，稱為左子樹個沒有交集的子樹，稱為左子樹Left Left SubtreeSubtree和右子樹和右子樹Right SubtreeRight Subtree。7-2 二元樹的基礎二元樹的基礎-圖例圖例左子樹左子樹右子樹右子樹二元樹二元樹7-2 二元樹的基礎二元樹的基礎-

9、歪斜樹歪斜樹左邊這棵樹沒有右子樹，右邊這棵樹沒有左子樹，左邊這棵樹沒有右子樹，右邊這棵樹沒有左子樹，雖然擁有一样節點，但是這是兩棵不同的二元樹，雖然擁有一样節點，但是這是兩棵不同的二元樹，因為一切節點都是向左子樹或右子樹歪斜，稱為因為一切節點都是向左子樹或右子樹歪斜，稱為歪斜樹歪斜樹Skewed TreeSkewed Tree，如下圖所示：，如下圖所示：7-2 二元樹的基礎二元樹的基礎-完滿二元樹完滿二元樹(說明說明)假设二元樹的樹高是h且二元樹的節點數是2h-1，滿足此條件的樹稱為完滿二元樹Full Binary Tree，如下圖所示：7-2 二元樹的基礎二元樹的基礎-完滿二元樹完滿二元樹(

10、節點數節點數)因為二元樹的每一個節點有因為二元樹的每一個節點有2 2個子節點，二元樹樹個子節點，二元樹樹高是高是3 3，也就是有，也就是有3 3個階層個階層 LevelLevel ，各階層，各階層( (以以L L表表示階層示階層) )的節點數為的節點數為 2 (L-1) 2 (L-1) ，如下所示：，如下所示：第第1 1階：階： 2 (L-1) = 2 (1-1) = 20 = 1 2 (L-1) = 2 (1-1) = 20 = 1第第2 2階：第階：第1 1階節點數的階節點數的2 2倍，倍，1*2 = 2 (2-1) = 21*2 = 2 (2-1) = 2第第3 3階：第階：第2 2階節

11、點數的階節點數的2 2倍，倍，2*2 = 2 (3-1) = 42*2 = 2 (3-1) = 4以此類推，可以得到每一階層的最大節點數是：以此類推，可以得到每一階層的最大節點數是：2 2 (L-1)(L-1)，L L是階層數，整棵二元樹的節點數一共是：是階層數，整棵二元樹的節點數一共是：20+21+22 = 720+21+22 = 7個，即個，即23-123-1，可以得到：，可以得到：20+21+22+.+2 (h-1) = 2h-120+21+22+.+2 (h-1) = 2h-1，h h是樹高是樹高7-2 二元樹的基礎二元樹的基礎-完好二元樹完好二元樹假设二元樹的節點不是葉節點，一定擁有

12、假设二元樹的節點不是葉節點，一定擁有2 2個子節個子節點，不過節點總數缺乏點，不過節點總數缺乏2h-12h-1，其中，其中h h是樹高，而且是樹高，而且其節點編號是對應一样高度完滿二元樹的至其節點編號是對應一样高度完滿二元樹的至2h-2h-1 1的節點編號，滿足此條件稱為完好二元樹的節點編號，滿足此條件稱為完好二元樹Complete Binary TreeComplete Binary Tree，如下圖所示：，如下圖所示：7-3 二元樹的表示法二元樹的表示法7-3-1 二元樹陣列表示法7-3-2二元樹結構陣列表示法7-3-3 二元樹鏈結表示法7-3 二元樹的表示法二元樹的表示法二元樹在實作上有

13、多種方法可以建立二元樹，常用的方法有三種，如下所示：二元樹陣列表示法。二元樹結構陣列表示法。二元樹鏈結表示法。7-3-1 二元樹陣列表示法二元樹陣列表示法-說明說明1完滿二元樹是一棵樹高完滿二元樹是一棵樹高h h擁有擁有2h-12h-1個節點的二元樹，個節點的二元樹，這是二元樹在樹高這是二元樹在樹高h h所能擁有的最大節點數，換句所能擁有的最大節點數，換句話說，只需配置話說，只需配置2h-12h-1個元素，我們就可以儲存樹個元素，我們就可以儲存樹高高h h的二元樹，如下圖所示：的二元樹，如下圖所示：7-3-1 二元樹陣列表示法二元樹陣列表示法-說明說明2二元樹的節點編號擁有循序性，根節點1的子

14、節點是節點2和節點3，節點2是4和5，依此類推可以得到節點編號的規則，如下所示：左子樹是父節點編號乘以2。右子樹是父節點編號乘以2加1。7-3-1 二元樹陣列表示法二元樹陣列表示法-標頭檔標頭檔01: /* 01: /* 程式範例程式範例: Ch7-3-1.h */: Ch7-3-1.h */02: #define MAX_LENGTH 16 /* 02: #define MAX_LENGTH 16 /* 最大陣列尺寸最大陣列尺寸 */ */03: int btreeMAX_LENGTH; /* 03: int btreeMAX_LENGTH; /* 二元樹陣列宣告二元樹陣列宣告 */ */0

15、4: /* 04: /* 笼统資料型態的操作函數宣告笼统資料型態的操作函數宣告 */ */05: extern void createBTree(int len, int *array);05: extern void createBTree(int len, int *array);06: extern void printBTree();06: extern void printBTree();7-3-1 二元樹陣列表示法二元樹陣列表示法-建立二建立二元樹元樹(規則規則)函數createBTree( )讀取一維陣列的元素建立二元樹，其建立的規則，如下所示：將第1個陣列元素插入成為二元樹的根

16、節點。將陣列元素值與二元樹的節點值比較，假设元素值大於節點值，將元素值插入成為節點的右子節點，假设右子節點不是空的，重覆比較節點值，直到找到插入位置後，將元素值插入二元樹。假设元素值小於節點值，將元素值插入成為節點的左子節點，假设左子節點不是空的，繼續重覆比較，以便將元素值插入二元樹。7-3-1 二元樹陣列表示法二元樹陣列表示法-建立二建立二元樹元樹(圖例圖例)維陣列值依序為維陣列值依序為: 5: 5、6 6、4 4、8 8、2 2、3 3、7 7、1 1、9 9建立二元樹如下，括號內是陣列的索引值，建立二元樹如下，括號內是陣列的索引值，7-3-1 二元樹陣列表示法二元樹陣列表示法-顯示二顯示

17、二元樹元樹函數printBTree( )：顯示二元樹函數printBTree()走訪btree 陣列，將元素值不是-1的元素都顯示出來。7-3-1 二元樹陣列表示法二元樹陣列表示法-問題問題一棵歪斜樹的二元樹陣列表示法运用不到三分之一棵歪斜樹的二元樹陣列表示法运用不到三分之一的陣列元素一的陣列元素4/164/16，因為二元樹的節點是以循序，因為二元樹的節點是以循序方式儲存在陣列中，假设需求插入或刪除節點，方式儲存在陣列中，假设需求插入或刪除節點，都需求在陣列中搬移大量元素，如下圖所示：都需求在陣列中搬移大量元素，如下圖所示：7-3-2二元樹結構陣列表示法二元樹結構陣列表示法-說說明明在二元樹的

18、每一個節點可以运用在二元樹的每一個節點可以运用C C語言的結構來語言的結構來儲存，整棵二元樹运用一個結構陣列，每一個結儲存，整棵二元樹运用一個結構陣列，每一個結構是一個節點，运用結構陣列儲存整棵二元樹，構是一個節點，运用結構陣列儲存整棵二元樹，datadata是節點資料，运用是節點資料，运用leftleft和和rightright成員變數的索引成員變數的索引值指向子節點的索引值，如為值指向子節點的索引值，如為-1-1表示沒有子節點，表示沒有子節點，如下圖所示：如下圖所示：7-3-2二元樹結構陣列表示法二元樹結構陣列表示法-標標頭檔頭檔01: /* 01: /* 程式範例程式範例: Ch7-3-

19、2.h */: Ch7-3-2.h */02: #define MAX_LENGTH 16 /* 02: #define MAX_LENGTH 16 /* 最大陣列尺寸最大陣列尺寸 */ */03: struct Node /* 03: struct Node /* 二元樹的結構宣告二元樹的結構宣告 */ */04: int data; /* 04: int data; /* 節點資料節點資料 */ */05: int left; /* 05: int left; /* 指向左子樹的位置指向左子樹的位置 */ */06: int right; /* 06: int right; /* 指向右子

20、樹的位置指向右子樹的位置 */ */07: ;07: ;08: typedef struct Node TreeNode; /* 08: typedef struct Node TreeNode; /* 樹的節點新型態樹的節點新型態 */ */09: TreeNode btreeMAX_LENGTH; 09: TreeNode btreeMAX_LENGTH; 10: /* 10: /* 笼统資料型態的操作函數宣告笼统資料型態的操作函數宣告 */ */11: extern void createBTree(int len, int *array);11: extern void createB

21、Tree(int len, int *array);12: extern void printBTree();12: extern void printBTree();7-3-2二元樹結構陣列表示法二元樹結構陣列表示法-圖圖例例例如：維陣列值依序為: 5、6、4、8、2、3、7、1、9的二元樹以結構陣列表示法，如下圖所示：7-3-3 二元樹鏈結表示法二元樹鏈結表示法-說明說明二元樹鏈結表示法是运用動態記憶體配置來建立二元樹，類似結構陣列表示法的節點結構，只是成員變數改成兩個指向左和右子樹的指標，如下圖所示：7-3-3 二元樹鏈結表示法二元樹鏈結表示法-標頭檔標頭檔01: /* 01: /* 程

22、式範例程式範例: Ch7-3-3.h */: Ch7-3-3.h */02: struct Node /* 02: struct Node /* 二元樹的節點宣告二元樹的節點宣告 */ */03: int data; /* 03: int data; /* 儲存節點資料儲存節點資料 */ */ 04: struct Node *left; /* 04: struct Node *left; /* 指向左子樹的指標指向左子樹的指標 */ */05: struct Node *right; /* 05: struct Node *right; /* 指向右子樹的指標指向右子樹的指標 */ */06

23、: ;06: ;07: typedef struct Node TNode; /* 07: typedef struct Node TNode; /* 二元樹節點的新型態二元樹節點的新型態 */ */08: typedef TNode *BTree; /* 08: typedef TNode *BTree; /* 二元樹鏈結的新型態二元樹鏈結的新型態 */ */09: BTree head = NULL; /* 09: BTree head = NULL; /* 二元樹根節點的指標二元樹根節點的指標 */ */10: /* 10: /* 笼统資料型態的操作函數宣告笼统資料型態的操作函數宣告 *

24、/ */11: extern void createBTree(int len, int *array);11: extern void createBTree(int len, int *array);12: extern void insertBTreeNode(int d);12: extern void insertBTreeNode(int d);13: extern int isBTreeEmpty();13: extern int isBTreeEmpty();14: extern void printBTree(); 14: extern void printBTree();

25、15: extern void inOrder(BTree ptr);15: extern void inOrder(BTree ptr);16: extern void printInOrder();16: extern void printInOrder();17: extern void preOrder(BTree ptr);17: extern void preOrder(BTree ptr);18: extern void printPreOrder();18: extern void printPreOrder();19: extern void postOrder(BTree

26、ptr);19: extern void postOrder(BTree ptr);20: extern void printPostOrder();20: extern void printPostOrder();7-3-3 二元樹鏈結表示法二元樹鏈結表示法-建立二建立二元樹元樹1函數函數createBTree( )createBTree( )运用运用forfor迴圈走訪參數的陣列元迴圈走訪參數的陣列元素，依序呼叫素，依序呼叫insertBTreeNode()insertBTreeNode()函數將一個一個函數將一個一個陣列元素的節點插入二元樹。首先是二元樹的根陣列元素的節點插入二元樹。首先

27、是二元樹的根節點節點5 5，leftleft和和rightright指標指向指標指向NULLNULL，如下圖所示：，如下圖所示：7-3-3 二元樹鏈結表示法二元樹鏈結表示法-建立二建立二元樹元樹2第二次呼叫第二次呼叫insertBTreeNode()insertBTreeNode()函數插入元素函數插入元素6 6，鏈結至右子樹。第三次呼叫插入元素鏈結至右子樹。第三次呼叫插入元素4 4成為左子樹。成為左子樹。等到執行完等到執行完createBTree()createBTree()函數的函數的forfor迴圈後，建立迴圈後，建立的二元樹，如下圖所示：的二元樹，如下圖所示：7-3-3 二元樹鏈結表示

28、法二元樹鏈結表示法-顯示二顯示二元樹元樹函數printBTree()：顯示二元樹函數printBTree()运用while迴圈分別走訪二元樹的左右分支，不過這個函數並沒有辦法顯示二元樹的全部節點資料。7-4 二元樹的走訪二元樹的走訪7-4-1 中序走訪方式7-4-2 前序走訪方式7-4-3 後序走訪方式7-4 二元樹的走訪二元樹的走訪-說明說明陣列和單向鏈結串列都只能從頭至尾或從尾至頭陣列和單向鏈結串列都只能從頭至尾或從尾至頭執行單向走訪執行單向走訪TraverseTraverse，不過二元樹的，不過二元樹的每一個節點都擁有指向左和右每一個節點都擁有指向左和右2 2個子節點的指標，個子節點的指

29、標，所以走訪可以有兩條路徑。例如：一棵二元樹，所以走訪可以有兩條路徑。例如：一棵二元樹，如下圖所示：如下圖所示：7-4 二元樹的走訪二元樹的走訪-種類種類二元樹的走訪過程是持續決定向左或向右走，直到沒路可走。很明顯的！二元樹的走訪是一種遞迴走訪，按照遞迴函數中呼叫的陈列順序不同，可以分成三種走訪方式，如下所示：中序走訪方式Inorder Traversal。前序走訪方式Preorder Traversal。後序走訪方式Postorder Traversal。7-4-1 中序走訪方式中序走訪方式-說明說明中序走訪是沿著二元樹的左方往下走，直到無法繼續前進後，顯示節點，退回到父節點顯示父節點，然後

30、繼續往右走，假设右方都無法前進，顯示節點，再退回到上一層。按照中序走訪第7-4節的二元樹，其顯示的節點順序，如下所示：1,2,3,4,5,6,7,8,9在上述中序走訪節點順序中，可以看出根節點5是位在正中間，之前都是左子樹的節點，之後都是右子樹的節點。7-4-1 中序走訪方式中序走訪方式-演算法演算法中序走訪的遞迴函數inOrder()运用二元樹指標ptr進行走訪，中序走訪的步驟，如下所示：Step 1：檢查能否可以繼續前進，即指標ptr不等於NULL。Step 2：假设可以前進，其處理方式如下所示：(1) 遞迴呼叫inOrder(ptr-left)向左走。(2) 處理目前的節點，顯示節點資料

31、。(3) 遞迴呼叫inOrder(ptr-right)向右走。7-4-1 中序走訪方式中序走訪方式-遞迴呼叫遞迴呼叫7-4-2 前序走訪方式前序走訪方式-說明說明前序走訪方式是走訪到的二元樹節點，就立刻顯示節點資料，走訪的順序是先向樹的左方走直到無法前進後，才轉往右方走。按照前序走訪第7-4節的二元樹，其顯示的節點順序，如下所示：5,4,2,1,3,6,8,7,9在上述前序走訪節點順序中，可以看出根節點5一定是第1個，左右子樹的根節點一定在其它節點之前。7-4-2 前序走訪方式前序走訪方式-演算法演算法前序走訪的遞迴函數preOrder()运用二元樹指標ptr進行走訪，前序走訪的步驟，如下所示

32、：Step 1：先檢查能否已經到達葉節點，也就是指標ptr等於NULL。Step 2：假设不是葉節點表示可以繼續走，其處理方式如下所示：(1) 處理目前的節點，顯示節點資料。(2) 遞迴呼叫preOrder(ptr-left)向左走。(3) 遞迴呼叫preOrder(ptr-right)向右走。7-4-2 前序走訪方式前序走訪方式-遞迴呼叫遞迴呼叫7-4-3 後序走訪方式後序走訪方式-說明說明後序走訪方式剛好和前序走訪相反，它是等到節點的2個子節點都走訪過後才執行處理，顯示節點資料。按照後序走訪第7-4節的二元樹，其顯示的節點順序，如下所示：1,3,2,4,7,9,8,6,5在上述後序走訪節點

33、順序中，可以看出根節點5是最後1個，而且左右子樹的根節點一定在其它節點之後。7-4-3 後序走訪方式後序走訪方式-演算法演算法後序走訪的遞迴函數postOrder()运用二元樹指標ptr進行走訪，後序走訪的步驟，如下所示：Step 1：先檢查能否已經到達葉節點，就是指標ptr等於NULL。Step 2：假设不是葉節點表示可以繼續走，其處理方式如下所示：(1) 遞迴呼叫postOrder(ptr-left)向左走。(2) 遞迴呼叫postOrder(ptr-right)向右走。(3) 處理目前的節點，顯示節點資料。7-4-3 後序走訪方式後序走訪方式-遞迴呼叫遞迴呼叫7-5 二元搜尋樹二元搜尋樹

34、7-5-1 二元搜尋樹的節點搜尋7-5-2 二元搜尋樹的節點刪除7-5 二元搜尋樹二元搜尋樹-說明說明二元搜尋樹Binary Search Trees是一種二元樹，其節點資料的陈列擁有一些特性，如下所示：二元樹的每一個節點值都不一样，在整棵二元樹中的每一個節點都擁有不同值。每一個節點的資料大於左子節點假设有的話的資料，但是小於右子節點假设有的話的資料。節點的左、右子樹也是一棵二元搜尋樹。7-5 二元搜尋樹二元搜尋樹-說明說明例如：在第7-3節建立的二元樹就是一棵二元搜尋樹，如下圖所示：7-5-1 二元搜尋樹的節點搜尋二元搜尋樹的節點搜尋-說說明明二元搜尋樹的節點搜尋非常簡單，因為右子節點二元搜

35、尋樹的節點搜尋非常簡單，因為右子節點的值一定大於左子節點，所以只需從根節點開始的值一定大於左子節點，所以只需從根節點開始比較，就知道搜尋值是位在右子樹或左子樹，繼比較，就知道搜尋值是位在右子樹或左子樹，繼續往子節點進行比較，就可以找出能否擁有指定續往子節點進行比較，就可以找出能否擁有指定的節點值。的節點值。例如：在第例如：在第7-57-5節的二元搜尋樹找尋節點資料節的二元搜尋樹找尋節點資料8 8，第一步與樹根第一步與樹根5 5比較，因為比較大，所以節點在右比較，因為比較大，所以節點在右子樹，接著和右子樹的節點子樹，接著和右子樹的節點6 6比較，還是比較大，比較，還是比較大，所以繼續向右子樹走，

36、然後是節點所以繼續向右子樹走，然後是節點8 8，只需三次比，只需三次比較就可以找到搜尋值。較就可以找到搜尋值。7-5-1 二元搜尋樹的節點搜尋二元搜尋樹的節點搜尋-實實作作在在C C程式是运用程式是运用whilewhile迴圈配合迴圈配合ptrptr指標指向根節指標指向根節點點headhead進行各子節點資料的比較，以便執行二進行各子節點資料的比較，以便執行二元搜尋樹的搜尋，如下所示：元搜尋樹的搜尋，如下所示：while ( ptr != NULL ) while ( ptr != NULL ) if ( ptr-data = d ) if ( ptr-data = d ) return pt

37、r; return ptr; else else if ( ptr-data d ) ptr = ptr-left; if ( ptr-data d ) ptr = ptr-left; else ptr = ptr-right; else ptr = ptr-right; 上述上述whilewhile迴圈的迴圈的if if條件判斷能否找到，假设節點條件判斷能否找到，假设節點值比搜尋值大，值比搜尋值大，ptr = ptr-leftptr = ptr-left向左子樹找，否則，向左子樹找，否則，ptr = ptr-rightptr = ptr-right向右子樹找。向右子樹找。7-5-2 二元搜尋

38、樹的節點刪除二元搜尋樹的節點刪除-情情況況1情況1：刪除葉節點葉節點是指沒有左和右子節點的節點，例如：刪除二元搜尋樹的葉節點1和9，如下圖所示：if ( parent-left = ptr )if ( parent-left = ptr ) parent-left = NULL; parent-left = NULL;elseelse parent-right = NULL; parent-right = NULL;7-5-2 二元搜尋樹的節點刪除二元搜尋樹的節點刪除-情情況況2(根節點根節點)情況2：刪除節點沒有左子樹根節點：刪除根節點5，只需將根節點指標指向其右子樹節點，如下圖所示： he

39、ad = head-right;7-5-2 二元搜尋樹的節點刪除二元搜尋樹的節點刪除-情情況況2(中間節點中間節點)刪除中間節點：假设刪除的是中間節點刪除中間節點：假设刪除的是中間節點2 2和和6 6，這，這兩個節點都沒有左子樹，此時是將刪除節點的父兩個節點都沒有左子樹，此時是將刪除節點的父節點指向其右子節點即可，如下圖所示：節點指向其右子節點即可，如下圖所示： if ( parent-left = ptr )if ( parent-left = ptr ) parent-left = ptr-right; parent-left = ptr-right;else parent-right =

40、 ptr-right;else parent-right = ptr-right;7-5-2 二元搜尋樹的節點刪除二元搜尋樹的節點刪除-情情況況3情況3：刪除節點沒有右子樹假设節點沒有右子樹，在此情況刪除節點，依節點的位置一樣可以分成二種：根節點和中間節點，節點刪除和情況2类似，只是左指標和右指標的交換。7-5-2 二元搜尋樹的節點刪除二元搜尋樹的節點刪除-情情況況4(說明說明1)情況情況4 4：刪除節點擁有左子樹和右子樹：刪除節點擁有左子樹和右子樹刪除節點假设擁有左子樹和右子樹，其處理方式並刪除節點假设擁有左子樹和右子樹，其處理方式並不會因刪除節點的位置而不同。例如：一棵二元不會因刪除節點的

41、位置而不同。例如：一棵二元搜尋樹，如下圖所示：搜尋樹，如下圖所示：7-5-2 二元搜尋樹的節點刪除二元搜尋樹的節點刪除-情情況況4(說明說明2)在二元搜尋樹刪除節點在二元搜尋樹刪除節點6 6，它是父節點，它是父節點9 9的左子樹，的左子樹，假设可以找到節點位在節點假设可以找到節點位在節點2 2和節點和節點8 8之間，將它之間，將它取代成刪除節點的位置，如此並不需求搬移太多取代成刪除節點的位置，如此並不需求搬移太多節點，就可以完成節點刪除。節點，就可以完成節點刪除。例如：刪除節點例如：刪除節點6 6事實上是刪除原來的葉節點事實上是刪除原來的葉節點5 5，因為刪除操作是交換這兩個節點來完成。因為刪

42、除操作是交換這兩個節點來完成。從二元搜尋樹的特性可以看出符合條件的交換節從二元搜尋樹的特性可以看出符合條件的交換節點有兩個，如下所示：點有兩個，如下所示：節點節點5 5：從節點：從節點6 6的左子節點的左子節點2 2不断從右子樹走到的不断從右子樹走到的葉葉( (無右子無右子) )節點為止。節點為止。節點節點7 7：從節點：從節點6 6的右子節點的右子節點8 8不断往左子樹走到的不断往左子樹走到的葉葉( (無左子無左子) )節點為止。節點為止。7-5-2 二元搜尋樹的節點刪除二元搜尋樹的節點刪除-情情況況4(實作實作)筆者运用第一種方式找出符合條件的節點，即節筆者运用第一種方式找出符合條件的節點

43、，即節點點5 5，程式碼如下所示：，程式碼如下所示：parent = ptr;parent = ptr;child = ptr-left;child = ptr-left;while ( child-right!=NULL ) while ( child-right!=NULL ) parent = child; parent = child; child = child-right; child = child-right; 上述上述parentparent是父節點，是父節點，ptrptr是刪除節點，是刪除節點，childchild是子是子節點，在先走到左子節點後，运用節點，在先走到左子節點

44、後，运用whilewhile迴圈往右迴圈往右子節點走，直到葉節點。子節點走，直到葉節點。7-6 引線二元樹引線二元樹-說明說明二元樹鏈結表示法假设擁有n個節點，因為每個節點有左、右2個指標，所以整棵二元樹有2*n個指標，其中指向NULL的比指向節點的還多。換句話說，善用這些NULL指標，就可以幫助我們走訪二元樹。引線二元樹Threaded Binary Trees是將一些原來指向NULL的指標改為指向其他節點，以便提供協助來進行中序走訪二元樹。7-6 引線二元樹引線二元樹-圖例圖例7-6 引線二元樹引線二元樹-建立建立(說明說明)右引線二元搜尋樹右引線二元搜尋樹Right Threaded B

45、inary Right Threaded Binary Search TreesSearch Trees是一種常用的引線二元樹，我們是一種常用的引線二元樹，我們可以在只添加一個欄位的情況下，以右指標的引可以在只添加一個欄位的情況下，以右指標的引線來幫助我們中序走訪二元搜尋樹，如下圖所示：線來幫助我們中序走訪二元搜尋樹，如下圖所示：7-6 引線二元樹引線二元樹-建立建立(節點結構節點結構)在節點結構除了原二元樹欄位外，為了區分引線和指標，額外添加欄位來標示指標的用途，如下所示：struct TNode int data; struct TNode *left; struct TNode *rig

46、ht; int isThread;typedef struct TNode RTNode;typedef RTNode *RTBTree;7-6 引線二元樹引線二元樹-建立建立(新增左子節點新增左子節點)當插入的新節點是左子節點時，只需將右引線指向其父節點parent，如下圖所示：parent-left-right = parent;parent-left-isThread = 1;7-6 引線二元樹引線二元樹-建立建立(新增右子節點新增右子節點)當插入的新節點是右子節點時，插入新節點newnode的右引線指向其父節點parent右引線原來所指的節點，如下所示：newnode-right =

47、parent-right;newnode-isThread = 1;parent-right = newnode;parent-isThread = 0;7-6 引線二元樹引線二元樹-中序走訪中序走訪首先從根節點開始，沿著左子樹的路徑往下走到首先從根節點開始，沿著左子樹的路徑往下走到葉葉( (無左子結點之無左子結點之) )節點，即中序走訪的開始節點，節點，即中序走訪的開始節點，然後运用右指標是引線或指標來進行中序走訪，然後运用右指標是引線或指標來進行中序走訪，如下所示：如下所示：任何節點的右指標不是引線，需求從右子節點為任何節點的右指標不是引線，需求從右子節點為起點，沿著左子樹的路徑往下走直到

48、左指標為起點，沿著左子樹的路徑往下走直到左指標為NULLNULL為止。例如：節點為止。例如：節點6 6的右指標不是引線，由的右指標不是引線，由其右子節點其右子節點8 8開始，沿著左子樹方向走，走到節點開始，沿著左子樹方向走，走到節點7 7時，符合左指標為時，符合左指標為NULLNULL，找到的是中序走訪的，找到的是中序走訪的節點節點7 7。假设任何節點的右指標是引線，引線所指的節點假设任何節點的右指標是引線，引線所指的節點是下一個中序走訪的節點。例如：節點是下一個中序走訪的節點。例如：節點1 1的右指標的右指標是引線，所以下一個中序走訪的節點是節點是引線，所以下一個中序走訪的節點是節點2 2。

49、請重覆上述操作直到右指標為請重覆上述操作直到右指標為NULLNULL為止，就完成為止，就完成右引線二元搜尋樹的中序走訪。右引線二元搜尋樹的中序走訪。7-7 樹的二元樹表示法樹的二元樹表示法-說明說明二元樹在樹狀結構佔有非常重要的位置，這是因二元樹在樹狀結構佔有非常重要的位置，這是因為一切樹都可以經過轉換，將它轉換成二元樹。為一切樹都可以經過轉換，將它轉換成二元樹。例如：例如：n n元樹狀結構的每個節點擁有元樹狀結構的每個節點擁有n n個分支，處個分支，處理不同數分支的節點都需求設計不同表示方法的理不同數分支的節點都需求設計不同表示方法的程式碼，例如：二元樹需求程式碼，例如：二元樹需求2 2個指

50、標，三個分支需個指標，三個分支需求求3 3個指標，以此類推。個指標，以此類推。不只如此，不只如此，n n元樹的元樹的NULLNULL指標問題比二元樹更加指標問題比二元樹更加嚴重，因為葉節點將擁有分支數個數的嚴重，因為葉節點將擁有分支數個數的NULLNULL指標，指標，所以我們可以將樹先轉換成二元樹，直接运用二所以我們可以將樹先轉換成二元樹，直接运用二元樹表示法來建立樹狀結構。元樹表示法來建立樹狀結構。7-7 樹的二元樹表示法樹的二元樹表示法-過程過程1例如：一棵樹，如下圖所示：7-7 樹的二元樹表示法樹的二元樹表示法-過程過程2將樹轉換成二元樹，也就是將將樹轉換成二元樹，也就是將n n個分支變

51、成個分支變成2 2個分個分支，只需把每個擁有同一個父節點的兄弟節點，支，只需把每個擁有同一個父節點的兄弟節點，將這些兄弟節點鏈結起來，保管最左邊的父子鏈將這些兄弟節點鏈結起來，保管最左邊的父子鏈結，將其它父子鏈結都打斷，就可以產生一棵二結，將其它父子鏈結都打斷，就可以產生一棵二元樹，如下圖所示：元樹，如下圖所示：7-7 樹的二元樹表示法樹的二元樹表示法-過程過程3接著將鏈結方向調整一下，就可以得到一棵二元樹，如下圖所示：7-8 二元樹的應用二元樹的應用 - 運算式處理運算式處理(說明說明)從樹的觀念而言，樹可以處理各種階層關係的問題，例如：賽程表和家族族譜等，假设將資料建立成二元搜尋樹，就成為

52、一種很好的資料搜尋方法。運算式處理可以运用堆疊執行轉換和求值，現在我們可以改為二元樹來處理運算式，建立運算式二元樹。7-8 二元樹的應用二元樹的應用 - 運算式處理運算式處理(建立運算式二元樹建立運算式二元樹1)例如：將中序運算式轉換成二元樹，如下所示：例如：將中序運算式轉換成二元樹，如下所示：5*6+4*35*6+4*3上述中序運算式的運算元是二元樹的葉節點，運上述中序運算式的運算元是二元樹的葉節點，運算子是非終端節點，因為考量運算子的優先順序，算子是非終端節點，因為考量運算子的優先順序，乘號大於加號，所以前後兩個乘號運算子先處理，乘號大於加號，所以前後兩個乘號運算子先處理，可以建立成二棵二

53、元樹，如下圖所示：可以建立成二棵二元樹，如下圖所示：7-8 二元樹的應用二元樹的應用 - 運算式處理運算式處理(建立運算式二元樹建立運算式二元樹2)接著處理低優先順序的加號，就完成運算式二元樹，如下圖所示：7-8 二元樹的應用二元樹的應用 - 運算式處理運算式處理(建立運算式二元樹建立運算式二元樹3)一棵沒有依據算子優先順序建立的運算式二元樹，如下圖所示：7-8 二元樹的應用二元樹的應用 - 運算式處理運算式處理(運算式二元樹的計算運算式二元樹的計算)運算式二元樹只需從葉節點開始計算各子節點的值，然後依序往上就可以計算出整棵運算式二元樹的值，如下所示：有優先順序的二元樹：425*6 = 304

54、*3 = 1230+12 = 42不考慮優先順序的二元樹：1506+4 = 105*10 = 5050 *3 = 1507-8 二元樹的應用二元樹的應用 - 運算式處理運算式處理(運算式二元樹的走訪運算式二元樹的走訪)运用中序走訪運算式二元樹，可以得到中序運算运用中序走訪運算式二元樹，可以得到中序運算式，如下所示：式，如下所示：有優先順序的二元樹：有優先順序的二元樹：5*6+4*35*6+4*3不考慮優先順序的二元樹：不考慮優先順序的二元樹：5*6+4*35*6+4*3运用前序走訪這兩棵二元樹，可以得到前序運算运用前序走訪這兩棵二元樹，可以得到前序運算式，如下所示：式，如下所示：有優先順序的二

55、元樹：有優先順序的二元樹：+*56*43+*56*43不考慮優先順序的二元樹：不考慮優先順序的二元樹：*5+643*5+643後序走訪的結果，如下所示：後序走訪的結果，如下所示：有優先順序的二元樹：有優先順序的二元樹：56*43+56*43+不考慮優先順序的二元樹：不考慮優先順序的二元樹：564+*3*564+*3*本章結束本章結束複習複習(一一)1. 1. 何謂二元樹何謂二元樹Binary TreesBinary Trees? ?2. 2. 何謂完滿二元樹何謂完滿二元樹Full Binary TreeFull Binary Tree? ?3. 3. 何謂歪斜樹何謂歪斜樹Skewed TreeSkewed Tree? ?4. 4. 何謂完好二元樹何謂完好二元樹Complete Binary TreeComplete Binary Tree? ?5. 5. 二元搜尋樹二元搜尋樹Binary Search TreesBinary Search Trees特特性為何性為何? ?6. 6. 何謂引線二元樹何謂引線二元樹Threaded Binary Threaded Binary TreesTrees? ?7. 7. 如何將普通的樹轉換成二元樹如何將普通的樹轉換成二元樹? ?