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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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