第六章二叉樹續(xù)ppt課件

1、1236.3 二叉樹的存儲構(gòu)造續(xù)二叉樹的存儲構(gòu)造續(xù)6.3 二叉樹的表示法二叉樹的表示法 二叉樹數(shù)組表示法二叉樹數(shù)組表示法 二叉樹構(gòu)造數(shù)組表示法二叉樹構(gòu)造數(shù)組表示法 二叉樹鏈表構(gòu)造表示法二叉樹鏈表構(gòu)造表示法46.3.1 二叉樹數(shù)組表示法二叉樹數(shù)組表示法 一顆高度為一顆高度為h的二叉樹，擁有最大的節(jié)點的二叉樹，擁有最大的節(jié)點數(shù)為數(shù)為2h-15 可以發(fā)現(xiàn)二叉樹有很好的順序性：可以發(fā)現(xiàn)二叉樹有很好的順序性： 左子樹是父節(jié)點乘以左子樹是父節(jié)點乘以2 右子數(shù)是父節(jié)點乘以右子數(shù)是父節(jié)點乘以2加加16.3.1 二叉樹數(shù)組表示法二叉樹數(shù)組表示法 經(jīng)過這樣的規(guī)那么，我們可以運用一位經(jīng)過這樣的規(guī)那么，我們可以運用一

2、位數(shù)組數(shù)組btree代表這顆樹，其長度是代表這顆樹，其長度是2MAX-1，MAX是最大能夠的層數(shù)。是最大能夠的層數(shù)。6 創(chuàng)建二叉樹結(jié)點數(shù)據(jù)的戰(zhàn)略有三個，如創(chuàng)建二叉樹結(jié)點數(shù)據(jù)的戰(zhàn)略有三個，如下所示：下所示： 將第一個要創(chuàng)建的元素插入成為跟結(jié)點將第一個要創(chuàng)建的元素插入成為跟結(jié)點； 將元素值與結(jié)點值進展比較，假設元素將元素值與結(jié)點值進展比較，假設元素值大于結(jié)點值，將此元素值送往結(jié)點的值大于結(jié)點值，將此元素值送往結(jié)點的右子結(jié)點，假設右子結(jié)點并不是空的，右子結(jié)點，假設右子結(jié)點并不是空的，需求反復比較，否那么創(chuàng)建結(jié)點將元素需求反復比較，否那么創(chuàng)建結(jié)點將元素值插入。值插入。 假設元素值小于結(jié)點值，將此元素送

3、往假設元素值小于結(jié)點值，將此元素送往結(jié)點的左子結(jié)點，假設左子結(jié)點不是空結(jié)點的左子結(jié)點，假設左子結(jié)點不是空的，需求反復比較，否那么創(chuàng)建結(jié)點將的，需求反復比較，否那么創(chuàng)建結(jié)點將元素值插入。元素值插入。7實例二叉查找樹：實例二叉查找樹： Binary Search Tree 二叉樹結(jié)點值輸入的數(shù)據(jù)順序是二叉樹結(jié)點值輸入的數(shù)據(jù)順序是5,6,4,8,2,3,7,1,9. 按照上述戰(zhàn)略創(chuàng)建二叉按照上述戰(zhàn)略創(chuàng)建二叉樹，如下所示樹，如下所示89/* = */* 程式實例程式實例: 7_3_1.c */* 二叉樹的數(shù)組表示法二叉樹的數(shù)組表示法 */* = */* - */* 建立二叉樹建立二叉樹 */* - *

4、/void createbtree(int *btree, int *data, int len) int level; /* 樹的階層樹的階層 */ int i; btree1 = data1; /* 建立根節(jié)點建立根節(jié)點 */ for ( i = 2; i btreelevel ) /* 是左或右子樹是左或右子樹 */ level = level * 2 + 1; /* 右子樹右子樹 */ else level = level * 2; /* 左子樹左子樹 */ btreelevel = datai; /* 存入節(jié)點數(shù)據(jù)存入節(jié)點數(shù)據(jù) */ 10/* - */* 主程式主程式: 建立數(shù)組的二

5、叉樹建立數(shù)組的二叉樹. */* - */void main() int btree16; /* 二叉樹數(shù)組二叉樹數(shù)組 */ /* 二叉樹節(jié)點數(shù)據(jù)二叉樹節(jié)點數(shù)據(jù) */ int data10 = 0, 5, 6, 4, 8, 2, 3, 7, 1, 9 ; int i; for ( i = 1; i 16; i+ ) /* 去除二叉樹數(shù)組去除二叉樹數(shù)組 */ btreei = 0; createbtree(btree,data,9); /* 建立二叉樹建立二叉樹 */ for ( i = 1; i 16; i+ ) /* 列出二叉樹內(nèi)容列出二叉樹內(nèi)容 */ printf(%2d: %d n,i,b

6、treei);結(jié)論的輸出圖形表示：結(jié)論的輸出圖形表示： 二叉樹的數(shù)組表示法可以運用在一切的二叉樹的數(shù)組表示法可以運用在一切的二叉樹。前面例子中的二叉樹的空間運二叉樹。前面例子中的二叉樹的空間運用率曾經(jīng)相當理想了，但是對于下面的用率曾經(jīng)相當理想了，但是對于下面的二叉樹，還是按照原來的方法就不理想二叉樹，還是按照原來的方法就不理想了。了。11產(chǎn)生的問題與處理方法產(chǎn)生的問題與處理方法 產(chǎn)生的問題產(chǎn)生的問題 假設運用二叉樹數(shù)組表示法，那么只運假設運用二叉樹數(shù)組表示法，那么只運用不到三分之一的數(shù)組元素，存儲空間用不到三分之一的數(shù)組元素，存儲空間浪費嚴重浪費嚴重 而且是順序表示，二叉樹結(jié)點的插入與而且是順

7、序表示，二叉樹結(jié)點的插入與刪除必需挪動相當多的元素才干完成。刪除必需挪動相當多的元素才干完成。 處理方法處理方法 可以運用下面各節(jié)的二叉樹表示法來處可以運用下面各節(jié)的二叉樹表示法來處理。理。126.3.2 二叉樹構(gòu)造數(shù)組表示法二叉樹構(gòu)造數(shù)組表示法 二叉樹的特征是每一個結(jié)點至多擁有兩二叉樹的特征是每一個結(jié)點至多擁有兩個子結(jié)點，所以可以聲明構(gòu)造存儲樹的個子結(jié)點，所以可以聲明構(gòu)造存儲樹的結(jié)點，這個結(jié)點至少擁有三個數(shù)據(jù)項，結(jié)點，這個結(jié)點至少擁有三個數(shù)據(jù)項，數(shù)據(jù)項存放結(jié)點數(shù)據(jù)，另外兩項存儲指數(shù)據(jù)項存放結(jié)點數(shù)據(jù)，另外兩項存儲指向左子樹和右子樹的數(shù)據(jù)索引，如以下向左子樹和右子樹的數(shù)據(jù)索引，如以下圖圖13二叉

8、樹運用的構(gòu)造聲明二叉樹運用的構(gòu)造聲明 struct tree int data; int left; int right; ; typedef struct tree treenode; treenode btree15;14 上述聲明最有一行的構(gòu)造數(shù)組就是存儲上述聲明最有一行的構(gòu)造數(shù)組就是存儲二叉樹的各結(jié)點。結(jié)點的數(shù)據(jù)安排是將二叉樹的各結(jié)點。結(jié)點的數(shù)據(jù)安排是將跟結(jié)點放在索引跟結(jié)點放在索引0，字段變量，字段變量left和和right分別指向跟結(jié)點左、右子樹的索引值，分別指向跟結(jié)點左、右子樹的索引值，假設沒有子樹變量假設沒有子樹變量left和和right為為-1. 例如：一顆二叉樹和其構(gòu)造數(shù)組表

9、示法例如：一顆二叉樹和其構(gòu)造數(shù)組表示法，如下圖，如下圖15 接著我們從跟結(jié)點來看這顆二叉樹。構(gòu)接著我們從跟結(jié)點來看這顆二叉樹。構(gòu)造數(shù)據(jù)索引造數(shù)據(jù)索引0表示這顆樹的樹根，先從左表示這顆樹的樹根，先從左子樹開場其字段子樹開場其字段left是是1，數(shù)據(jù)索引，數(shù)據(jù)索引1表示表示是其左子結(jié)點。是其左子結(jié)點。 再看右子樹，字段再看右子樹，字段right是是2，數(shù)據(jù)索引，數(shù)據(jù)索引2是其右子結(jié)點即數(shù)據(jù)索引是其右子結(jié)點即數(shù)據(jù)索引2，字段，字段left是是-1表示沒有左子結(jié)點表示沒有左子結(jié)點 字段字段right是是3表示數(shù)據(jù)索引表示數(shù)據(jù)索引3是其右子結(jié)是其右子結(jié)點，以此類推，可以跟蹤到二叉樹的各點，以此類推，可以

10、跟蹤到二叉樹的各個葉結(jié)點個葉結(jié)點,即字段即字段left和和right都是都是-116運用構(gòu)造數(shù)組創(chuàng)建二叉樹。運用構(gòu)造數(shù)組創(chuàng)建二叉樹。17/* = */* 程式實例: 7_3_2.c */* 二叉樹的構(gòu)造數(shù)組表示法 */* = */#include struct tree /* 樹的構(gòu)造宣告 */ int data; /* 節(jié)點數(shù)據(jù) */ int left; /* 指向左子樹的位置 */ int right; /* 指向右子樹的位置 */;typedef struct tree treenode; /* 樹的構(gòu)造新型態(tài) */treenode btree15; /* 宣告樹的構(gòu)造數(shù)組 */18/*

11、 - */* 建立二叉樹 */* - */void createbtree(int *data,int len) int level; /* 樹的階層 */ int pos; /* -1是左樹,1是右樹 */ int i; btree0.data = data0; /* 建立樹根節(jié)點 */ for ( i = 1; i btreelevel.data ) /* 右樹能否有下一階層 */ if ( btreelevel.right != -1 ) level = btreelevel.right; else pos = -1; /* 是右樹 */19else /* 左樹能否有下一階層 */ if

12、 ( btreelevel.left != -1 ) level = btreelevel.left; else pos = 1; /* 是左樹 */ if ( pos = 1 ) /* 建立節(jié)點左右位置 */ btreelevel.left = i; /* 鏈結(jié)左子樹 */ else btreelevel.right = i; /* 鏈結(jié)右子樹 */ 20/* - */* 主程式: 建立構(gòu)造數(shù)組的二叉樹狀構(gòu)造. */* 數(shù)字-1表示沒有下一階層. */* - */void main() /* 二叉樹節(jié)點數(shù)據(jù) */ int data10 = 5, 6, 4, 8, 2, 3, 7, 1, 9

13、; int i; for ( i = 0; i 15; i+ ) /* 去除樹狀構(gòu)造數(shù)組 */ btreei.data = 0; /* 設定初始內(nèi)容 */ btreei.left = -1; /* 設定初始內(nèi)容 */ btreei.right = -1; /* 設定初始內(nèi)容 */ createbtree(data,9); /* 建立二叉樹 */ printf( 左 數(shù)據(jù) 右n); printf(- n); for ( i = 0; i 15; i+ ) /* 列出二叉樹內(nèi)容 */ if ( btreei.data != 0 ) /* 能否是樹的節(jié)點 */ printf(%2d:%2d %2d

14、%2dn,i,btreei.left, btreei.data,btreei.right);輸出結(jié)果輸出結(jié)果21構(gòu)造數(shù)組表示二叉樹優(yōu)缺陷構(gòu)造數(shù)組表示二叉樹優(yōu)缺陷 優(yōu)點優(yōu)點 處理二叉樹插入、刪除結(jié)點時的大量挪處理二叉樹插入、刪除結(jié)點時的大量挪動數(shù)據(jù)的問題；動數(shù)據(jù)的問題； 由于二叉樹的創(chuàng)建靠字段由于二叉樹的創(chuàng)建靠字段left和和right銜接銜接，上述操作只需改動這兩個值即可。，上述操作只需改動這兩個值即可。 缺陷缺陷 需求估計二叉樹的結(jié)點個數(shù)，否那么定需求估計二叉樹的結(jié)點個數(shù)，否那么定義的結(jié)點數(shù)一旦超越聲明的構(gòu)造數(shù)組長義的結(jié)點數(shù)一旦超越聲明的構(gòu)造數(shù)組長度，將會產(chǎn)生未知的錯誤。度，將會產(chǎn)生未知的錯

15、誤。226.3.3 二叉樹鏈表構(gòu)造表示法二叉樹鏈表構(gòu)造表示法 二叉樹鏈表構(gòu)造表示法是運用動態(tài)內(nèi)存分配創(chuàng)二叉樹鏈表構(gòu)造表示法是運用動態(tài)內(nèi)存分配創(chuàng)建二叉樹。我們運用結(jié)點構(gòu)造的左、右指針變建二叉樹。我們運用結(jié)點構(gòu)造的左、右指針變量字段鏈接樹狀的父和子結(jié)點。量字段鏈接樹狀的父和子結(jié)點。 所以除了存儲結(jié)點的根本數(shù)據(jù)外，每一個二叉所以除了存儲結(jié)點的根本數(shù)據(jù)外，每一個二叉樹的結(jié)點至少應該擁有兩個字段放左子樹和右樹的結(jié)點至少應該擁有兩個字段放左子樹和右子樹的指針，如以下圖子樹的指針，如以下圖23 二叉樹運用的根本構(gòu)造聲明，二叉樹運用的根本構(gòu)造聲明， struct tree int data; struct t

16、ree *left; struct tree *right; ; typedef struct tree treenode; typedef treenode *btree; 上述聲明的上述聲明的data項是存儲二叉樹結(jié)點的項是存儲二叉樹結(jié)點的數(shù)據(jù)，字段數(shù)據(jù)，字段left和和right分別是指向左、右分別是指向左、右邊子樹的構(gòu)造指針。邊子樹的構(gòu)造指針。2425/* = */* 程式實例: 7_3_3.c */* 二叉樹的鏈結(jié)構(gòu)造表示法 */* = */#include struct tree /* 樹的構(gòu)造宣告 */ int data; /* 節(jié)點數(shù)據(jù) */ struct tree *left

17、; /* 指向左子樹的目的 */ struct tree *right; /* 指向右子樹的目的 */;typedef struct tree treenode; /* 樹的構(gòu)造新型態(tài) */typedef treenode *btree; /* 宣告樹節(jié)點目的型態(tài) */26/* - */* 插入二叉樹的節(jié)點 */* - */btree insertnode(btree root,int value) btree newnode; /* 樹根目的 */ btree current; /* 目前樹節(jié)點目的 */ btree back; /* 父節(jié)點目的 */ /* 建立新節(jié)點記憶體 */ newn

18、ode = ( btree ) malloc(sizeof(treenode); newnode-data = value; /* 建立節(jié)點內(nèi)容 */ newnode-left = NULL; /* 設定目的初值 */ newnode-right = NULL; /* 設定目的初值 */ if ( root = NULL ) /* 能否是根節(jié)點 */ return newnode; /* 傳回新節(jié)點位置 */ 27else current = root; /* 保管目前樹目的 */ while ( current != NULL ) back = current; /* 保管父節(jié)點目的 */

19、if ( current-data value ) /* 比較節(jié)點值 */ current = current-left; /* 左子樹 */ else current = current-right; /* 右子樹 */ if ( back-data value ) /* 接起父子的鏈結(jié) */ back-left = newnode; /* 左子樹 */ else back-right = newnode; /* 右子樹 */ return root; /* 傳回樹根目的 */28/* - */* 建立二叉樹 */* - */btree createbtree(int *data,int l

20、en) btree root = NULL; /* 樹根目的 */ int i; for ( i = 0; i left; printf(列印左子樹:n); while ( ptr != NULL ) /* 列印回路 */ printf(%2dn,ptr-data); /* 列印節(jié)點內(nèi)容 */ ptr = ptr-left; /* 左子節(jié)點 */ ptr = root-right; printf(列印右子樹:n); while ( ptr != NULL ) /* 列印回路 */ printf(%2dn,ptr-data); /* 列印節(jié)點內(nèi)容 */ ptr = ptr-right; /* 右

21、子節(jié)點 */ 30/* - */* 主程式: 建立鏈結(jié)的二叉樹且列印出來. */* - */void main() btree root = NULL; /* 樹根目的 */ /* 二叉樹節(jié)點數(shù)據(jù) */ int data10 = 5, 6, 4, 8, 2, 3, 7, 1, 9 ; root = createbtree(data,9); /* 建立二叉樹 */ printf(樹的節(jié)點內(nèi)容 n); printbtree(root); /* 列出二叉樹內(nèi)容 */ 輸出結(jié)果輸出結(jié)果31 程序闡明程序闡明 本程序并沒有完全輸出整個二叉樹本程序并沒有完全輸出整個二叉樹 函數(shù)函數(shù)printbtree只是

22、運用循環(huán)遍歷二只是運用循環(huán)遍歷二叉樹。叉樹。 所以顯示的只是二叉樹的一條分支，而所以顯示的只是二叉樹的一條分支，而無法輸出完好的二叉樹結(jié)點。無法輸出完好的二叉樹結(jié)點。 如需完好輸出整棵樹，就需求借助遞歸如需完好輸出整棵樹，就需求借助遞歸技巧，詳細闡明請參看下一節(jié)二叉樹的技巧，詳細闡明請參看下一節(jié)二叉樹的遍歷。遍歷。32336.4 二叉樹的遍歷續(xù)二叉樹的遍歷續(xù) 線性數(shù)據(jù)構(gòu)造的數(shù)組和鏈表都只能從頭線性數(shù)據(jù)構(gòu)造的數(shù)組和鏈表都只能從頭至尾或從尾至頭的遍歷。至尾或從尾至頭的遍歷。 但是二叉樹的遍歷就比較復雜但是二叉樹的遍歷就比較復雜 二叉樹的每一個結(jié)點都可以分成左右兩二叉樹的每一個結(jié)點都可以分成左右兩個

23、分支。假設把它視為一張公路圖，此個分支。假設把它視為一張公路圖，此時的每個結(jié)點都是岔路可以選擇往左或時的每個結(jié)點都是岔路可以選擇往左或往右走。往右走。 當然假設結(jié)點沒有左子樹或者右子樹，當然假設結(jié)點沒有左子樹或者右子樹，可以視為死路?？梢砸暈樗缆贰?如今把問題減少，無論在哪個結(jié)點面對如今把問題減少，無論在哪個結(jié)點面對的都是往左或往右的選擇，整個遍歷過的都是往左或往右的選擇，整個遍歷過程可以簡化成為繼續(xù)的處置選擇，直到程可以簡化成為繼續(xù)的處置選擇，直到?jīng)]有路可走。沒有路可走。 所以二叉樹的遍歷實踐上是一種遞歸的所以二叉樹的遍歷實踐上是一種遞歸的遍歷，但是由于遞歸函數(shù)中調(diào)用的陳列遍歷，但是由于遞歸

24、函數(shù)中調(diào)用的陳列順序不，可以分為三種不同的遍歷方式順序不，可以分為三種不同的遍歷方式，如下，如下34 中序遍歷方式中序遍歷方式Inorder Traversal 中根序遍歷方式中根序遍歷方式 前序遍歷方式前序遍歷方式Preorder Traversal 或稱為先根序遍歷方式或稱為先根序遍歷方式 后續(xù)遍歷方式后續(xù)遍歷方式Postorder Traversal 或稱為后根序遍歷方式或稱為后根序遍歷方式356.4.1 中序遍歷方式中序遍歷方式 中序遍歷是沿著樹的左方走，直到無法中序遍歷是沿著樹的左方走，直到無法繼續(xù)前進后處置結(jié)點，退回父節(jié)點依次繼續(xù)前進后處置結(jié)點，退回父節(jié)點依次此方法往右方走，假設右

25、方都無法前進此方法往右方走，假設右方都無法前進，再往上層退回。，再往上層退回。 所以以下圖的處置順序為：所以以下圖的處置順序為：1,2,3,4,5,6,7,8,936 中序遍歷的遞歸函數(shù)假設是中序遍歷的遞歸函數(shù)假設是inorder()，指針指針root是二叉樹指針，中序遍歷的遞是二叉樹指針，中序遍歷的遞歸步驟如下所示：歸步驟如下所示： 1 檢查能否可以繼續(xù)進展，即指針檢查能否可以繼續(xù)進展，即指針root不不等于等于NULL 2 假設可以繼續(xù)前進假設可以繼續(xù)前進,其處置方式如下：其處置方式如下： 遞歸調(diào)用遞歸調(diào)用inorderroot- left往左走。往左走。 處置目前結(jié)點處置目前結(jié)點 遞歸調(diào)

26、用遞歸調(diào)用inorderroot-right往右走往右走。 程序?qū)嵗绦驅(qū)嵗?7_4_1.c 創(chuàng)建一顆二叉樹，運用中序遍歷將結(jié)創(chuàng)建一顆二叉樹，運用中序遍歷將結(jié)點輸出。點輸出。37 這個程序創(chuàng)建的二叉樹構(gòu)造圖如下括這個程序創(chuàng)建的二叉樹構(gòu)造圖如下括號內(nèi)是假設結(jié)點內(nèi)存位置：號內(nèi)是假設結(jié)點內(nèi)存位置：38 這個程序運轉(zhuǎn)如下：這個程序運轉(zhuǎn)如下：6.4.2 前序遍歷方式前序遍歷方式 前序遍歷方式是每遍歷到一個結(jié)點就立前序遍歷方式是每遍歷到一個結(jié)點就立刻處置結(jié)點。遍歷的順序是先向著樹的刻處置結(jié)點。遍歷的順序是先向著樹的左方走直到無法前進后，才轉(zhuǎn)往右方走左方走直到無法前進后，才轉(zhuǎn)往右方走 所以以下圖的處置順序為

27、：所以以下圖的處置順序為：5,4,2,1,3,6,8,7,939 前序遍歷的遞歸函數(shù)假設是前序遍歷的遞歸函數(shù)假設是perorder()，輸入的參數(shù)是數(shù)指針輸入的參數(shù)是數(shù)指針root是二叉樹指針是二叉樹指針，前序遍歷的遞歸步驟如下所示：，前序遍歷的遞歸步驟如下所示： 1 檢查能否曾經(jīng)到達葉結(jié)點，也就是指針檢查能否曾經(jīng)到達葉結(jié)點，也就是指針root等于等于NULL 2 假設不是葉結(jié)點表示可以繼續(xù)走假設不是葉結(jié)點表示可以繼續(xù)走,其處其處置方式如下：置方式如下： 處置目前結(jié)點處置目前結(jié)點 遞歸調(diào)用遞歸調(diào)用preorderroot- left往左走往左走。 遞歸調(diào)用遞歸調(diào)用preorderroot-ri

28、ght往右走往右走。 上述的操作和中序遍歷只是處置結(jié)點和上述的操作和中序遍歷只是處置結(jié)點和遞歸調(diào)用順序上的差別。遞歸調(diào)用順序上的差別。40程序?qū)嵗绦驅(qū)嵗?7_4_2.c 創(chuàng)建一顆二叉樹，運用前序遍歷將結(jié)創(chuàng)建一顆二叉樹，運用前序遍歷將結(jié)點輸出。點輸出。樹的構(gòu)造為：樹的構(gòu)造為：41程序輸出結(jié)果為：6.4.3 后序遍歷方式后序遍歷方式 后序遍歷方式剛好和前序遍歷方式相反，它是后序遍歷方式剛好和前序遍歷方式相反，它是等到結(jié)點的兩個子結(jié)點都遍歷過后才運轉(zhuǎn)處置等到結(jié)點的兩個子結(jié)點都遍歷過后才運轉(zhuǎn)處置。 所以以下圖的處置順序為：所以以下圖的處置順序為：1,3,2,4,7,9,8,6,542 后序遍歷的遞歸

29、函數(shù)假設是后序遍歷的遞歸函數(shù)假設是postorder()，輸入的參數(shù)是數(shù)指針，輸入的參數(shù)是數(shù)指針root是二叉樹指是二叉樹指針，后序遍歷的遞歸步驟如下所示：針，后序遍歷的遞歸步驟如下所示： 1 檢查能否曾經(jīng)到達葉結(jié)點，也就是指針檢查能否曾經(jīng)到達葉結(jié)點，也就是指針root等于等于NULL 2 假設不是葉結(jié)點表示可以繼續(xù)走假設不是葉結(jié)點表示可以繼續(xù)走,其處其處置方式如下：置方式如下： 遞歸調(diào)用遞歸調(diào)用postorderroot- left往左走往左走。 遞歸調(diào)用遞歸調(diào)用postorderroot-right往右往右走。走。 處置目前結(jié)點處置目前結(jié)點43程序?qū)嵗绦驅(qū)嵗?7_4_3.c 創(chuàng)建一顆二叉

30、樹，運用后序遍歷將結(jié)創(chuàng)建一顆二叉樹，運用后序遍歷將結(jié)點輸出。點輸出。樹的構(gòu)造為：樹的構(gòu)造為：44程序輸出結(jié)果為：6.5 二叉樹的遞歸創(chuàng)建方法二叉樹的遞歸創(chuàng)建方法 二叉樹的遞歸創(chuàng)建方法和上節(jié)二叉樹的二叉樹的遞歸創(chuàng)建方法和上節(jié)二叉樹的遍歷非常類似。遍歷非常類似。 但是為了能從數(shù)組直接取的二叉樹的結(jié)但是為了能從數(shù)組直接取的二叉樹的結(jié)點數(shù)據(jù)，數(shù)據(jù)的安排就是運用點數(shù)據(jù)，數(shù)據(jù)的安排就是運用6.3.1節(jié)的節(jié)的二叉樹數(shù)組表示法。二叉樹數(shù)組表示法。 假設說這個程序是數(shù)組表示法轉(zhuǎn)換成鏈假設說這個程序是數(shù)組表示法轉(zhuǎn)換成鏈表構(gòu)造的二叉樹表示法，那也沒有錯。表構(gòu)造的二叉樹表示法，那也沒有錯。45 程序?qū)嵗绦驅(qū)嵗?7_

31、5.c 運用遞歸方法創(chuàng)建二叉樹，然后運用中運用遞歸方法創(chuàng)建二叉樹，然后運用中序遍歷方式將二叉樹的結(jié)點輸出出來。序遍歷方式將二叉樹的結(jié)點輸出出來。 程序輸出結(jié)果如下：程序輸出結(jié)果如下：466.6 二叉樹的查找方式二叉樹的查找方式 參考參考6.4 節(jié)的二叉樹遍歷我們可以設計遞節(jié)的二叉樹遍歷我們可以設計遞歸函數(shù)在二叉樹內(nèi)查詢指定的數(shù)據(jù)的結(jié)歸函數(shù)在二叉樹內(nèi)查詢指定的數(shù)據(jù)的結(jié)點。點。 整個查找過程和二叉樹遍歷幾乎完全一整個查找過程和二叉樹遍歷幾乎完全一樣。樣。47 例如：一棵二叉樹，如以下圖所示。例如：一棵二叉樹，如以下圖所示。48 上圖的二叉樹稱為上圖的二叉樹稱為“二叉查找樹二叉查找樹(Binary

32、Search Trees), 其特性為：其特性為： 每一個結(jié)點的值都不同，也就是整棵樹每一個結(jié)點的值都不同，也就是整棵樹中的每一個結(jié)點都擁有不同的值。中的每一個結(jié)點都擁有不同的值。 每一個結(jié)點的數(shù)據(jù)大于左子樹結(jié)點假每一個結(jié)點的數(shù)據(jù)大于左子樹結(jié)點假設有的話的數(shù)據(jù)，但是小于右子樹結(jié)設有的話的數(shù)據(jù)，但是小于右子樹結(jié)點假設有的話的數(shù)據(jù)。點假設有的話的數(shù)據(jù)。 左、右兩部分的子樹，也是一棵二叉查左、右兩部分的子樹，也是一棵二叉查找樹。找樹。 假設二叉樹的結(jié)點數(shù)據(jù)曾經(jīng)按照上述的假設二叉樹的結(jié)點數(shù)據(jù)曾經(jīng)按照上述的規(guī)那么進展陳列，二叉樹的查找就非常規(guī)那么進展陳列，二叉樹的查找就非常簡單。例如簡單。例如 在上述二

33、叉樹內(nèi)查詢結(jié)點數(shù)據(jù)在上述二叉樹內(nèi)查詢結(jié)點數(shù)據(jù)8，第一步，第一步與樹根與樹根5進展比較，由于比較大，結(jié)點必進展比較，由于比較大，結(jié)點必在二叉樹的右子樹。在二叉樹的右子樹。 接著喝右子樹的結(jié)點接著喝右子樹的結(jié)點6進展比較，結(jié)果還進展比較，結(jié)果還是比較大，所以繼續(xù)向右子樹走。是比較大，所以繼續(xù)向右子樹走。 此時結(jié)點數(shù)據(jù)是此時結(jié)點數(shù)據(jù)是8 ， 找到了。找到了。 這次查找處置總共破費三次的比較就找這次查找處置總共破費三次的比較就找到了查詢的結(jié)點，假設運用遍歷的方式到了查詢的結(jié)點，假設運用遍歷的方式，必需經(jīng)過遍歷左子樹后才干找到，其，必需經(jīng)過遍歷左子樹后才干找到，其運轉(zhuǎn)效率的差別就非常的明顯。運轉(zhuǎn)效率的差

34、別就非常的明顯。49 程序?qū)嵗撼绦驅(qū)嵗?_6.c 運用遞歸的方式創(chuàng)建二叉查找樹。接著運用遞歸的方式創(chuàng)建二叉查找樹。接著輸入查詢的值，程序可以分別運用遍歷輸入查詢的值，程序可以分別運用遍歷和二叉查找樹方式運轉(zhuǎn)查找，最后將結(jié)和二叉查找樹方式運轉(zhuǎn)查找，最后將結(jié)果輸出果輸出 程序運轉(zhuǎn)結(jié)果如下程序運轉(zhuǎn)結(jié)果如下50 程序闡明：程序闡明： 程序函數(shù)程序函數(shù)btreefind9( ) 是二叉查找樹的查是二叉查找樹的查找，函數(shù)找，函數(shù)btreesearch( )是遞歸的遍歷查是遞歸的遍歷查找。找。 其中遍歷查找的操作和第其中遍歷查找的操作和第6.4 節(jié)一樣。節(jié)一樣。 二叉查找樹的查找是運用循環(huán)比較結(jié)點二叉查

35、找樹的查找是運用循環(huán)比較結(jié)點，看看結(jié)點能否找到，假設沒有找到，看看結(jié)點能否找到，假設沒有找到，在比較其大小，以決議從左子樹或右子在比較其大小，以決議從左子樹或右子樹繼續(xù)查找。樹繼續(xù)查找。516.7 二叉樹內(nèi)結(jié)點的刪除二叉樹內(nèi)結(jié)點的刪除 如今有一顆二叉樹圖形，如下所示如今有一顆二叉樹圖形，如下所示52 上述圖形符合上述圖形符合6.6節(jié)二叉查找樹的數(shù)據(jù)陳列節(jié)二叉查找樹的數(shù)據(jù)陳列方式，假設需求刪除一個結(jié)點，而且在刪方式，假設需求刪除一個結(jié)點，而且在刪除后，依然滿足二叉查找樹的數(shù)據(jù)陳列戰(zhàn)除后，依然滿足二叉查找樹的數(shù)據(jù)陳列戰(zhàn)略。此時刪除操作分為三種情況，如下所略。此時刪除操作分為三種情況，如下所示：示：

36、三種情況分別為：三種情況分別為： 結(jié)點沒有左子樹結(jié)點沒有左子樹 結(jié)點沒有右子樹結(jié)點沒有右子樹 結(jié)點有左右子樹結(jié)點有左右子樹53情況情況1： 結(jié)點沒有左子樹結(jié)點沒有左子樹 如今如今 有一棵沒有左子樹的二叉樹，如以有一棵沒有左子樹的二叉樹，如以下圖所示。下圖所示。54 結(jié)點結(jié)點5,6,9都沒有左子樹。假設在此情況下刪除結(jié)點，都沒有左子樹。假設在此情況下刪除結(jié)點，按結(jié)點的位置有三種處置方式，如下所示：按結(jié)點的位置有三種處置方式，如下所示： 1 刪除跟結(jié)點：刪除跟結(jié)點也就是結(jié)點刪除跟結(jié)點：刪除跟結(jié)點也就是結(jié)點5，此時只需求將跟結(jié)點指針指向其右子，此時只需求將跟結(jié)點指針指向其右子樹結(jié)點，如下所示：樹結(jié)點

37、，如下所示：55 2 刪除葉結(jié)點：刪除葉結(jié)點： 假設刪除的結(jié)點是葉結(jié)假設刪除的結(jié)點是葉結(jié)點也就是結(jié)點點也就是結(jié)點9，此時只需將父結(jié)點指向，此時只需將父結(jié)點指向NULL,如以下圖所示：如以下圖所示：56 3 刪除中間結(jié)點：假設刪除的結(jié)點是刪除中間結(jié)點：假設刪除的結(jié)點是6，此時只需將父結(jié)點指向右子結(jié)點即可，此時只需將父結(jié)點指向右子結(jié)點即可，如以下圖所示：如以下圖所示：57 上述葉結(jié)點和中間結(jié)點的刪除可以合并上述葉結(jié)點和中間結(jié)點的刪除可以合并處置，由于葉結(jié)點的指針都是指向處置，由于葉結(jié)點的指針都是指向NULL,只需將其父結(jié)點指向子結(jié)點只需將其父結(jié)點指向子結(jié)點.58情況情況2： 結(jié)點沒有右子樹結(jié)點沒有

38、右子樹 如今如今 有一棵沒有右子樹的二叉樹，如以有一棵沒有右子樹的二叉樹，如以下圖所示。下圖所示。59 結(jié)點結(jié)點5,4,1都沒有右子樹。假設在此情況下刪除結(jié)點，都沒有右子樹。假設在此情況下刪除結(jié)點，需求思索跟結(jié)點、葉結(jié)點和中間結(jié)點的情況。它和第需求思索跟結(jié)點、葉結(jié)點和中間結(jié)點的情況。它和第一種情況只需左指針和右指針的差別。一種情況只需左指針和右指針的差別。情況情況3： 結(jié)點有左右子樹結(jié)點有左右子樹 假設二叉樹是這種情況，其處置不會由假設二叉樹是這種情況，其處置不會由于結(jié)點的位置而不同，但是處置的過程于結(jié)點的位置而不同，但是處置的過程就比較復雜。就比較復雜。60 察看上述二叉樹，假設需求刪除跟結(jié)

39、點5.我們假設能找到一個結(jié)點也是在結(jié)點3和結(jié)點7之間，然后將它取代成為跟結(jié)點的位置。 這樣整棵二叉樹并不需求太多的搬動就可以完成結(jié)點的刪除操作。 例如：結(jié)點4正符合上述的需求，等到刪除結(jié)點5后，其構(gòu)造如以下圖所示.61 那么真正刪除的結(jié)點是原來的結(jié)點4，然后將原來跟結(jié)點內(nèi)容5交換為4，就完成了刪除的操作。 問題是如何找到符合條件的結(jié)點4，其實從二叉查找樹的特性可以發(fā)現(xiàn)符合條件的結(jié)點有兩個，分別是原來的結(jié)點4和6. 他們是從跟結(jié)點5的左子結(jié)點3不斷從右子樹走的葉結(jié)點和右子結(jié)點7不斷往左子樹走的葉子結(jié)點。62 如今我們運用從左子結(jié)點開場尋覓交換如今我們運用從左子結(jié)點開場尋覓交換的結(jié)點，假設刪除的結(jié)

40、點是的結(jié)點，假設刪除的結(jié)點是5，從結(jié)點，從結(jié)點5的左子結(jié)點的左子結(jié)點3開場往右子樹找，直到到達開場往右子樹找，直到到達葉結(jié)點，找到的是葉結(jié)點葉結(jié)點，找到的是葉結(jié)點4. 接著刪除此葉結(jié)點，其方法和情況接著刪除此葉結(jié)點，其方法和情況1、2一樣，最后取代原結(jié)點一樣，最后取代原結(jié)點5成為成為4. 假設刪除的是結(jié)點假設刪除的是結(jié)點3，此時左子結(jié)點，此時左子結(jié)點2并并沒有右子結(jié)點，所以符合條件的就是結(jié)沒有右子結(jié)點，所以符合條件的就是結(jié)點點2.刪除的操作就成為刪除一個沒有右子刪除的操作就成為刪除一個沒有右子樹的結(jié)點樹的結(jié)點2，然后將原結(jié)點，然后將原結(jié)點3的值取代成的值取代成為為2.其完好的圖形為：其完好的圖

41、形為：6364程序?qū)嵗撼绦驅(qū)嵗?_7.c 運用遞歸創(chuàng)建一棵二叉樹，然后輸入一運用遞歸創(chuàng)建一棵二叉樹，然后輸入一個結(jié)點值后，運用二叉查找方式尋覓結(jié)個結(jié)點值后，運用二叉查找方式尋覓結(jié)點，假設找到，就調(diào)用刪除函數(shù)將結(jié)點點，假設找到，就調(diào)用刪除函數(shù)將結(jié)點刪除，最后輸出刪除的結(jié)果。原二叉樹刪除，最后輸出刪除的結(jié)果。原二叉樹為如以下圖形：為如以下圖形：656.8 二叉樹的復制二叉樹的復制 在二叉樹的運用上經(jīng)常需求備份原來的在二叉樹的運用上經(jīng)常需求備份原來的二叉樹，可以運用遞歸的方法復制二叉二叉樹，可以運用遞歸的方法復制二叉樹。樹。 復制函數(shù)運用和二叉樹遍歷類似的遞歸復制函數(shù)運用和二叉樹遍歷類似的遞歸調(diào)

42、用。調(diào)用。66程序?qū)嵗撼绦驅(qū)嵗?_8.c 運用遞歸方式創(chuàng)建二叉樹，然后備份原運用遞歸方式創(chuàng)建二叉樹，然后備份原來的二叉樹，最后將原來的二叉樹和備來的二叉樹，最后將原來的二叉樹和備份的二叉樹都輸出出來。份的二叉樹都輸出出來。 程序闡明：函數(shù)程序闡明：函數(shù)copybtree( )先創(chuàng)建左子先創(chuàng)建左子樹，然后創(chuàng)建右子樹。樹，然后創(chuàng)建右子樹。676.9 線索二叉樹線索二叉樹 在重新思索前面闡明的二叉樹鏈表構(gòu)造在重新思索前面闡明的二叉樹鏈表構(gòu)造表示法，可以看出左右指針指向表示法，可以看出左右指針指向NULL的情況比實踐有運用的情形還多。的情況比實踐有運用的情形還多。 所以所以A.J.Perlis與與

43、C.Thronton兩位就把這兩位就把這些空的指針運用線索方式取代，稱為些空的指針運用線索方式取代，稱為“線索二叉樹線索二叉樹Threaded Binary Tree 例如：如今有一棵二叉樹，以下圖所示例如：如今有一棵二叉樹，以下圖所示：68 上述二叉樹中序遍歷的結(jié)果，如下所示上述二叉樹中序遍歷的結(jié)果，如下所示 1,2,3,4,5,6,7,8,9 線索的運用方法是當右子樹是空的時，線索的運用方法是當右子樹是空的時，將指針指向中序遍歷時的下一個結(jié)點。將指針指向中序遍歷時的下一個結(jié)點。 左子樹為空時，就指向中序遍歷的前一左子樹為空時，就指向中序遍歷的前一個結(jié)點。如下圖：個結(jié)點。如下圖：69 上圖的

44、虛線就是線索。葉結(jié)點上圖的虛線就是線索。葉結(jié)點3沒有右子樹，沒有右子樹，所以右線索指向中序遍歷的下一個結(jié)點所以右線索指向中序遍歷的下一個結(jié)點4. 同時也沒有左子樹，所以左線索指向中序遍歷同時也沒有左子樹，所以左線索指向中序遍歷的前一個結(jié)點的前一個結(jié)點2， 其他各個結(jié)點的處置方式一樣。其他各個結(jié)點的處置方式一樣。 除了結(jié)點除了結(jié)點1和和9的這兩條線索剛好是中序遍歷的的這兩條線索剛好是中序遍歷的第一個和最后一個結(jié)點，此時線索無法設置，第一個和最后一個結(jié)點，此時線索無法設置，處理的方法是運用頭結(jié)點，后面會詳細闡明。處理的方法是運用頭結(jié)點，后面會詳細闡明。70 線索二叉樹的結(jié)點構(gòu)造，除了原有的二線索二叉樹的