第七章 二叉樹及其應(yīng)用

1、第第7 7章章 1 7.1 二叉樹的概念 7.2 二叉樹的存儲(chǔ) 7.3 二叉樹的遍歷 7.4 線索二叉樹 7.5 二叉樹的應(yīng)用1基本算法 7.6 二叉樹的應(yīng)用2哈夫曼樹 7.7 二叉樹的應(yīng)用3二叉排序樹 7.8 二叉樹的應(yīng)用3堆和堆排序 第第7 7章章 2 7.1.1 什么是二叉樹 7.1.2 特殊的二叉樹 7.1.3 二叉樹的性質(zhì) 第第7 7章章 3 二叉樹的定義 二叉樹是由二叉樹是由n(n0)個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)組成組成的有限集的有限集合，合，其中其中： ， a bc de f g h ij 第第7 7章章 4 二叉樹的形態(tài) 空樹 單結(jié)點(diǎn)二叉樹 a 右子樹不空的 二叉樹 左子樹不空的 二叉樹 左右

2、子樹均不空的二叉樹 第第7 7章章 5 二叉樹的基本術(shù)語(yǔ)： 若一個(gè)結(jié)點(diǎn)有子樹，則該結(jié)點(diǎn)為父結(jié)點(diǎn)（也稱若一個(gè)結(jié)點(diǎn)有子樹，則該結(jié)點(diǎn)為父結(jié)點(diǎn)（也稱 ）。）。 ：若某結(jié)點(diǎn)有左子樹，則其左子樹的根為該結(jié)：若某結(jié)點(diǎn)有左子樹，則其左子樹的根為該結(jié) 點(diǎn)的左孩子；若其有右子樹，則其右子樹的根為該結(jié)點(diǎn)點(diǎn)的左孩子；若其有右子樹，則其右子樹的根為該結(jié)點(diǎn) 的右孩子。的右孩子。 a bc de f g h ij 結(jié)點(diǎn)結(jié)點(diǎn)a a為結(jié)點(diǎn)為結(jié)點(diǎn)b b、c c的父結(jié)點(diǎn)的父結(jié)點(diǎn) b b為為a a的左孩子，的左孩子， c c是是a a的右孩子；的右孩子； 第第7 7章章 6 同一個(gè)結(jié)點(diǎn)的孩子。同一個(gè)結(jié)點(diǎn)的孩子。 延伸父子關(guān)系可得到祖

3、先結(jié)點(diǎn)和后代結(jié)點(diǎn)關(guān)系。延伸父子關(guān)系可得到祖先結(jié)點(diǎn)和后代結(jié)點(diǎn)關(guān)系。 根結(jié)點(diǎn)的層次為根結(jié)點(diǎn)的層次為1 1，其余結(jié)點(diǎn)的層次是其父結(jié)點(diǎn)，其余結(jié)點(diǎn)的層次是其父結(jié)點(diǎn) 的層次加的層次加1 1。 二叉樹中結(jié)點(diǎn)的最大層次數(shù)。二叉樹中結(jié)點(diǎn)的最大層次數(shù)。 a bc de f g h ij 該二叉樹的深度為該二叉樹的深度為4 4； 第第7 7章章 7 一個(gè)結(jié)點(diǎn)的孩子數(shù)目是這個(gè)結(jié)點(diǎn)的度。一個(gè)結(jié)點(diǎn)的孩子數(shù)目是這個(gè)結(jié)點(diǎn)的度。 ：度為：度為0 0的結(jié)點(diǎn)。的結(jié)點(diǎn)。 二叉樹中結(jié)點(diǎn)的最大的度。二叉樹中結(jié)點(diǎn)的最大的度。 a bc de f g h ij a a、b b、c c的度均為的度均為2 2； e e、f f、g g的度均為的

4、度均為1 1； d d、h h、i i、j j的度為的度為0.0. 第第7 7章章 8 注意：對(duì)于結(jié)點(diǎn)數(shù)注意：對(duì)于結(jié)點(diǎn)數(shù)11的二叉樹，有且僅有一個(gè)結(jié)點(diǎn)為的二叉樹，有且僅有一個(gè)結(jié)點(diǎn)為 二叉樹的根，其余結(jié)點(diǎn)均為孩子結(jié)點(diǎn)，且有左右之二叉樹的根，其余結(jié)點(diǎn)均為孩子結(jié)點(diǎn)，且有左右之 分分左孩子、右孩子。左孩子、右孩子。 具有三個(gè)結(jié)點(diǎn)的二叉樹具有三個(gè)結(jié)點(diǎn)的二叉樹 a bc b a c a b c a b cc a b 第第7 7章章 9 二叉樹的邏輯結(jié)構(gòu) （1 1）二叉樹中任一結(jié)點(diǎn)（除根結(jié)點(diǎn)外）只有一個(gè)）二叉樹中任一結(jié)點(diǎn)（除根結(jié)點(diǎn)外）只有一個(gè) 父結(jié)點(diǎn)；父結(jié)點(diǎn)； （2 2）二叉樹中任一結(jié)點(diǎn)（除葉子結(jié)點(diǎn)外）最多

5、有）二叉樹中任一結(jié)點(diǎn)（除葉子結(jié)點(diǎn)外）最多有2 2 個(gè)孩子結(jié)點(diǎn)；個(gè)孩子結(jié)點(diǎn)； （3 3）結(jié)點(diǎn)間為非線性關(guān)系。）結(jié)點(diǎn)間為非線性關(guān)系。 第第7 7章章 10 7.1.1 什么是二叉樹 7.1.2 兩種特殊的二叉樹 7.1.3 二叉樹的性質(zhì) 第第7 7章章 11 滿二叉樹是滿足如下條件的二叉樹： 任一非葉子結(jié)點(diǎn)均有兩個(gè)孩子；任一非葉子結(jié)點(diǎn)均有兩個(gè)孩子； 對(duì)于二叉樹的任對(duì)于二叉樹的任一一層，若該層上有一個(gè)結(jié)點(diǎn)有層，若該層上有一個(gè)結(jié)點(diǎn)有 孩子，則該層上所有結(jié)點(diǎn)均有孩子。孩子，則該層上所有結(jié)點(diǎn)均有孩子。 滿二叉樹的每層都有最大結(jié)點(diǎn)數(shù)。滿二叉樹的每層都有最大結(jié)點(diǎn)數(shù)。 mn a bc d e f g jhik

6、lp 第第7 7章章 12 1 23 45 67 可不可以說(shuō)，所有非葉子結(jié)點(diǎn)均有兩個(gè)孩子 的二叉樹為滿二叉樹？ 第第7 7章章 13 在滿二叉樹的最下層從右到左連續(xù)地刪除若干在滿二叉樹的最下層從右到左連續(xù)地刪除若干 個(gè)結(jié)點(diǎn)所得到的二叉樹。個(gè)結(jié)點(diǎn)所得到的二叉樹。 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)； 滿二叉樹必為完全二叉樹，滿二叉樹必為完全二叉樹， 而完全二叉樹不而完全二叉樹不 一定是滿二叉樹。一定是滿二叉樹。 a bc d e f g jhik l 第第7 7章章 14 例：滿二叉樹和完全二叉樹 1 23 11 45 891213 67 101415 1

7、 23 11 45 8912 67 10 1 23 456 第第7 7章章 15 7.1.1 什么是二叉樹 7.1.2 兩種特殊的二叉樹 7.1.3 二叉樹的性質(zhì) 第第7 7章章 16 性質(zhì)性質(zhì)1 1：在二叉樹的第在二叉樹的第i i層上至多有層上至多有2 2i-1 i-1個(gè)結(jié)點(diǎn)（ 個(gè)結(jié)點(diǎn)（i 0i 0） 用數(shù)學(xué)歸納法。用數(shù)學(xué)歸納法。 當(dāng)當(dāng)i i=1=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此 時(shí)時(shí)2 2i-1 i-1=2 =20 0=1=1，結(jié)論成立。，結(jié)論成立。 假設(shè)假設(shè)i=ki=k時(shí)結(jié)論成立，即第時(shí)結(jié)論成立，即第k k層上結(jié)點(diǎn)總層上結(jié)點(diǎn)總 數(shù)最多為數(shù)最多為2 2k-1

8、k-1個(gè)。 個(gè)。 因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為2 2，則第，則第k+1k+1 層的結(jié)點(diǎn)總數(shù)最多為第層的結(jié)點(diǎn)總數(shù)最多為第k k層上結(jié)點(diǎn)最大數(shù)的層上結(jié)點(diǎn)最大數(shù)的2 2倍，即倍，即 2 22 2k-1 k-1=2 =2(k+1)-1 (k+1)-1，故結(jié)論成立。 ，故結(jié)論成立。 第第7 7章章 17 性質(zhì)性質(zhì)2 2：深度為深度為k k的二叉樹至多有的二叉樹至多有2 2k k-1-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k 0k 0） 因?yàn)樯疃葹橐驗(yàn)樯疃葹閗 k的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是 將二叉樹將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為每層上結(jié)點(diǎn)的最大值相

9、加，所以深度為k k的二的二 叉樹的結(jié)點(diǎn)總數(shù)至多為叉樹的結(jié)點(diǎn)總數(shù)至多為 k i k i ki i 11 1 122層上的最大結(jié)點(diǎn)個(gè)數(shù)第 故結(jié)論成立。故結(jié)論成立。 第第7 7章章 18 性質(zhì)性質(zhì)3：對(duì)任一棵非空的二叉樹：對(duì)任一棵非空的二叉樹t，如果其葉子數(shù)為，如果其葉子數(shù)為n0 ，度為，度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則：，則： n0 = n2 +1 設(shè)設(shè) 總結(jié)點(diǎn)數(shù)為總結(jié)點(diǎn)數(shù)為n，度為，度為1的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n1. 則則 ： n = n1 + n2 + n0 又又 度為度為1的結(jié)點(diǎn)有的結(jié)點(diǎn)有1個(gè)孩子，度為個(gè)孩子，度為2的結(jié)點(diǎn)有的結(jié)點(diǎn)有2個(gè)孩子個(gè)孩子. 故故 二叉樹中孩子結(jié)點(diǎn)的總數(shù)為二叉樹中孩

10、子結(jié)點(diǎn)的總數(shù)為n1 + 2n2 二叉樹中只有根結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子二叉樹中只有根結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子 總結(jié)點(diǎn)數(shù)總結(jié)點(diǎn)數(shù) n = n1 + 2n2 + 1 即：即：n1 +2n2 + 1 = n1 + n2 + n0 n0 = n2 +1 第第7 7章章 19 已知葉子數(shù)為20，10個(gè)結(jié)點(diǎn)有一個(gè)左孩子，15個(gè) 結(jié)點(diǎn)有一個(gè)右孩子，求該二叉樹的總結(jié)點(diǎn)數(shù)。 n0 = 20 n1 = 10 + 15 = 25 由于 n0 = n2 + 1 則：n2 = n0 1= 19 n = n0 + n1 + n2 = 20 + 25 + 19 = 64 第第7 7章章 20 性質(zhì)性質(zhì)4： 有有 n 個(gè)結(jié)點(diǎn)的完

11、全二叉樹個(gè)結(jié)點(diǎn)的完全二叉樹( n 0 )的高度為的高度為 +1 假設(shè)一棵高度為假設(shè)一棵高度為h的二叉樹有的二叉樹有n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)， 根據(jù)性質(zhì)根據(jù)性質(zhì)2，有，有 n2h1 從而從而 hlog2(n+1) 所以所以 h +1 n 2 log n 2 log 第第7 7章章 21 性質(zhì)性質(zhì)5：若對(duì)滿二叉樹或完全二叉樹按照若對(duì)滿二叉樹或完全二叉樹按照“從上到下，從上到下， 每層從左到右，根結(jié)點(diǎn)編號(hào)為每層從左到右，根結(jié)點(diǎn)編號(hào)為1”的方式編號(hào)，則編號(hào)的方式編號(hào)，則編號(hào) 為為 i 的結(jié)點(diǎn)，它的兩個(gè)孩子結(jié)點(diǎn)的編號(hào)分別為的結(jié)點(diǎn)，它的兩個(gè)孩子結(jié)點(diǎn)的編號(hào)分別為 2i 和和 2i +1，它的父結(jié)點(diǎn)的編號(hào)為，它的父結(jié)

12、點(diǎn)的編號(hào)為 i /2 。 a bc d e f g jhik l 1 2 3 4 56 7 8 9 10 11 12 第第7 7章章 22 有有100100個(gè)結(jié)點(diǎn)的完全二叉樹有多少個(gè)葉子結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)的完全二叉樹有多少個(gè)葉子結(jié)點(diǎn)？ 第第100100個(gè)結(jié)點(diǎn)的編號(hào)為個(gè)結(jié)點(diǎn)的編號(hào)為100100，其父結(jié)點(diǎn)的編號(hào)為，其父結(jié)點(diǎn)的編號(hào)為5050， 且其父結(jié)點(diǎn)的右兄弟（編號(hào)為且其父結(jié)點(diǎn)的右兄弟（編號(hào)為5151）沒有孩子，即為葉）沒有孩子，即為葉 子；所以，葉子結(jié)點(diǎn)的編號(hào)從子；所以，葉子結(jié)點(diǎn)的編號(hào)從5151至至100100，葉子結(jié)點(diǎn)有，葉子結(jié)點(diǎn)有5050 個(gè)。個(gè)。 第第7 7章章 23 7.1 二叉樹的概念 7.

13、2 二叉樹的存儲(chǔ) 7.3 二叉樹的遍歷 7.4 線索二叉樹 7.5 二叉樹的應(yīng)用1基本算法 7.6 二叉樹的應(yīng)用2哈夫曼樹 7.7 二叉樹的應(yīng)用3二叉排序樹 7.8 二叉樹的應(yīng)用3堆和堆排序 第第7 7章章 24 7.2.1 二叉樹的順序存儲(chǔ) 7.2.2 二叉樹的鏈接存儲(chǔ) 7.2.3 二叉樹的建立 第第7 7章章 25 將一棵二叉樹中的結(jié)點(diǎn)，按它們?cè)谕耆鏄渲袑⒁豢枚鏄渲械慕Y(jié)點(diǎn)，按它們?cè)谕耆鏄渲?的編號(hào)順序，依次存儲(chǔ)在一維數(shù)組的編號(hào)順序，依次存儲(chǔ)在一維數(shù)組btn+1中；即編號(hào)為中；即編號(hào)為 i 的結(jié)點(diǎn)存儲(chǔ)在數(shù)組中下標(biāo)為的結(jié)點(diǎn)存儲(chǔ)在數(shù)組中下標(biāo)為 i 的元素中。的元素中。 這樣，根據(jù)性質(zhì)這

14、樣，根據(jù)性質(zhì)5可知編號(hào)為可知編號(hào)為 i 的結(jié)點(diǎn)，其左孩子的結(jié)點(diǎn)，其左孩子 下標(biāo)為下標(biāo)為2i ，其右孩子下標(biāo)為，其右孩子下標(biāo)為2i +1，其父結(jié)點(diǎn)的下標(biāo)為，其父結(jié)點(diǎn)的下標(biāo)為 i/2。 第第7 7章章 26 a bc de fg 例：如下二叉樹的順序存儲(chǔ)。例：如下二叉樹的順序存儲(chǔ)。 abt12 1234567891011 先對(duì)二叉樹中結(jié)點(diǎn)進(jìn)行先對(duì)二叉樹中結(jié)點(diǎn)進(jìn)行 編號(hào)編號(hào); 將二叉樹存儲(chǔ)在數(shù)組將二叉樹存儲(chǔ)在數(shù)組 bt12中。中。 bcdef g 第第7 7章章 27 二叉樹順序存儲(chǔ)的特點(diǎn)： 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中，無(wú)需附加任何信結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中，無(wú)需附加任何信 息就能在這種順序存

15、儲(chǔ)結(jié)構(gòu)里找到每個(gè)結(jié)點(diǎn)的雙親和孩息就能在這種順序存儲(chǔ)結(jié)構(gòu)里找到每個(gè)結(jié)點(diǎn)的雙親和孩 子。子。 浪費(fèi)空間，適于存儲(chǔ)滿二叉樹和完全二叉樹。浪費(fèi)空間，適于存儲(chǔ)滿二叉樹和完全二叉樹。 第第7 7章章 28 7.2.1 二叉樹的順序存儲(chǔ) 7.2.2 二叉樹的鏈接存儲(chǔ) 7.2.3 二叉樹的建立 第第7 7章章 29 對(duì)于任意的二叉樹來(lái)說(shuō)，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，對(duì)于任意的二叉樹來(lái)說(shuō)，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子， 一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)點(diǎn)至少包括三個(gè) 域：數(shù)據(jù)域、域：數(shù)據(jù)域、 左孩子域和右孩子：左孩子域和右孩子： lchilddatarchild 其中，其中，lc

16、hild域指向該結(jié)點(diǎn)的左孩子，域指向該結(jié)點(diǎn)的左孩子，data域記錄該結(jié)域記錄該結(jié) 點(diǎn)的信息，點(diǎn)的信息，rchild域指向該結(jié)點(diǎn)的右孩子。域指向該結(jié)點(diǎn)的右孩子。 第第7 7章章 30 結(jié)點(diǎn)類型描述為： typedef struct node datatype data ; struct node *lchild , *rchild ; bitree ; 若定義一個(gè) bitree 類型的指針變量 t，存放根結(jié)點(diǎn) 的地址，則稱 t 為根指針。 這時(shí)，一個(gè)二叉鏈表由根指針 t 唯一確定，稱 二叉二叉 鏈表鏈表 t 第第7 7章章 31 例：例：右圖二叉樹的二叉鏈表 a bc de f g h a c

17、g d b ef h 第第7 7章章 32 二叉樹的鏈?zhǔn)酱鎯?chǔ)中，有時(shí)，為了便于找到父結(jié)點(diǎn)，二叉樹的鏈?zhǔn)酱鎯?chǔ)中，有時(shí)，為了便于找到父結(jié)點(diǎn)， 可以增加一個(gè)可以增加一個(gè)parent域，域， parent域指向該結(jié)點(diǎn)的父結(jié)域指向該結(jié)點(diǎn)的父結(jié) 點(diǎn)。點(diǎn)。 該結(jié)點(diǎn)結(jié)構(gòu)如下：該結(jié)點(diǎn)結(jié)構(gòu)如下： lchilddataparentrchild typedef struct node datatype data; struct node *lchild, *rchild, *parent; jd; 第第7 7章章 33 a b cd ef g a b c d e f g 第第7 7章章 34 不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹

18、的操作也不同。不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹的操作也不同。 如要找某個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，在三叉鏈表中很容易實(shí)如要找某個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，在三叉鏈表中很容易實(shí) 現(xiàn)；在二叉鏈表中則需從根指針出發(fā)一一查找?，F(xiàn)；在二叉鏈表中則需從根指針出發(fā)一一查找。 可見，在具體應(yīng)用中，需要根據(jù)二叉樹的形態(tài)和需可見，在具體應(yīng)用中，需要根據(jù)二叉樹的形態(tài)和需 要進(jìn)行的操作來(lái)決定二叉樹的存儲(chǔ)結(jié)構(gòu)。要進(jìn)行的操作來(lái)決定二叉樹的存儲(chǔ)結(jié)構(gòu)。 第第7 7章章 35 7.2.1 二叉樹的順序存儲(chǔ) 7.2.2 二叉樹的鏈接存儲(chǔ) 7.2.3 二叉樹的建立 第第7 7章章 36 按完全二叉樹的層次順序，依次輸入結(jié)點(diǎn)信息建立 二叉鏈表。 依次輸入結(jié)點(diǎn)信息，

19、若其不是虛結(jié)點(diǎn)，則建立一 個(gè)新結(jié)點(diǎn)。 若新結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)；否則 將新結(jié)點(diǎn)作為孩子鏈接到它的父結(jié)點(diǎn)上。 重復(fù) 、 ，直至輸入信息“”時(shí)為止。 第第7 7章章 37 為使新結(jié)點(diǎn)能正確地與其父結(jié)點(diǎn)鏈接，可設(shè)置一個(gè)為使新結(jié)點(diǎn)能正確地與其父結(jié)點(diǎn)鏈接，可設(shè)置一個(gè) 隊(duì)列，該隊(duì)列是一個(gè)指針類型的數(shù)組，保存已輸入隊(duì)列，該隊(duì)列是一個(gè)指針類型的數(shù)組，保存已輸入 的結(jié)點(diǎn)的地址。的結(jié)點(diǎn)的地址。 且且 front 指向當(dāng)前與其孩子結(jié)點(diǎn)建指向當(dāng)前與其孩子結(jié)點(diǎn)建 立鏈接的父結(jié)點(diǎn)，立鏈接的父結(jié)點(diǎn)，rear 指向當(dāng)前輸入的結(jié)點(diǎn)。指向當(dāng)前輸入的結(jié)點(diǎn)。 第第7 7章章 38 若若rear 為偶數(shù)，則該結(jié)點(diǎn)為父結(jié)點(diǎn)的

20、左孩子；若為偶數(shù)，則該結(jié)點(diǎn)為父結(jié)點(diǎn)的左孩子；若 rear 為奇數(shù)，則為父結(jié)點(diǎn)的右孩子。若父結(jié)點(diǎn)或孩為奇數(shù)，則為父結(jié)點(diǎn)的右孩子。若父結(jié)點(diǎn)或孩 子結(jié)點(diǎn)為虛結(jié)點(diǎn)，則無(wú)需鏈接。子結(jié)點(diǎn)為虛結(jié)點(diǎn)，則無(wú)需鏈接。 若父結(jié)點(diǎn)與其兩個(gè)孩子結(jié)點(diǎn)鏈接完畢，則做出隊(duì)操若父結(jié)點(diǎn)與其兩個(gè)孩子結(jié)點(diǎn)鏈接完畢，則做出隊(duì)操 作：作：front +1 . 初始值：初始值：front = 1; rear = 0 ; 第第7 7章章 39 bitree *q 0 1 2 3 4 as rear+1; 該結(jié)點(diǎn)地址入隊(duì)該結(jié)點(diǎn)地址入隊(duì) 若若rear1則該結(jié)點(diǎn)為根則該結(jié)點(diǎn)為根 front b s rear為偶數(shù)則為左孩子為偶數(shù)則為左孩子 rea

21、r為奇數(shù)則為右孩子為奇數(shù)則為右孩子 ch=getchar( ); s=null; if(ch!=) s=malloc( ); s-data=ch; s-lchild=s-rchild=null; rear+; qrear=s; if(rear=1) root=s if(s else qfront-rchild=s; if(rear%2=1 ) front+; c front 第第7 7章章 40 具體的算法如下：具體的算法如下： bitree *qmaxsize; /隊(duì)列隊(duì)列q為指針類型為指針類型 bitree *creatree( ) /建立二叉樹，返回根指針建立二叉樹，返回根指針 char

22、 ch; int front, rear; bitree *root, *s; root =null; /置空二叉樹置空二叉樹 front = 1; rear = 0; /置空隊(duì)列置空隊(duì)列 ch = getchar ( ); /輸入第一個(gè)字符輸入第一個(gè)字符 while ( ch!=#) /不是結(jié)束符號(hào)時(shí)繼續(xù)不是結(jié)束符號(hào)時(shí)繼續(xù) s=null; /如果輸入的是虛結(jié)點(diǎn)，則無(wú)需為虛結(jié)點(diǎn)申請(qǐng)空間如果輸入的是虛結(jié)點(diǎn)，則無(wú)需為虛結(jié)點(diǎn)申請(qǐng)空間 第第7 7章章 41 if ( ch ! =) /表示虛結(jié)點(diǎn)，不是虛結(jié)點(diǎn)時(shí)建立新結(jié)點(diǎn)表示虛結(jié)點(diǎn)，不是虛結(jié)點(diǎn)時(shí)建立新結(jié)點(diǎn) s = malloc( sizeof ( bit

23、ree) ); s-data=ch; s-lchild=s-rchild=null; rear+; qrear=s; /將虛結(jié)點(diǎn)指針將虛結(jié)點(diǎn)指針null或新結(jié)點(diǎn)地址入隊(duì)或新結(jié)點(diǎn)地址入隊(duì) if (rear = =1) root=s; /輸入的第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)輸入的第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn) else if (s else qfront-rchild=s; 第第7 7章章 42 if ( rear %2= =1 ) front+; /結(jié)點(diǎn)結(jié)點(diǎn)* qfront的兩個(gè)孩子已處理完畢的兩個(gè)孩子已處理完畢f(xié)ront+1 ch = getchar( ); return root; 第第7 7章章 43 7.1 二

24、叉樹的概念 7.2 二叉樹的存儲(chǔ) 7.3 二叉樹的遍歷 7.4 線索二叉樹 7.5 二叉樹的應(yīng)用1基本算法 7.6 二叉樹的應(yīng)用2哈夫曼樹 7.7 二叉樹的應(yīng)用3二叉排序樹 7.8 二叉樹的應(yīng)用3堆和堆排序 第第7 7章章 44 7.3.1 二叉樹遍歷的概念 7.3.2 二叉樹遍歷的遞歸算法 7.3.3 二叉樹遍歷的非遞歸算法 第第7 7章章 45 二叉樹的遍歷 對(duì)一個(gè)二叉樹，按某種次序訪問其中每個(gè)結(jié)點(diǎn)對(duì)一個(gè)二叉樹，按某種次序訪問其中每個(gè)結(jié)點(diǎn) 一次且僅一次的過(guò)程稱為二叉樹的遍歷。一次且僅一次的過(guò)程稱為二叉樹的遍歷。 二叉樹的遍歷算法是二叉樹各種運(yùn)算的基礎(chǔ)。二叉樹的遍歷算法是二叉樹各種運(yùn)算的基礎(chǔ)

25、。 第第7 7章章 46 遍歷過(guò)程的實(shí)現(xiàn)分析 1、 若二叉樹若二叉樹 t 為空，則遍歷結(jié)束。為空，則遍歷結(jié)束。 2、 否則，假設(shè)二叉樹的形態(tài)如圖所示，且左右子否則，假設(shè)二叉樹的形態(tài)如圖所示，且左右子 樹能分別遍歷，則整個(gè)二叉樹可按如下樹能分別遍歷，則整個(gè)二叉樹可按如下6種次序分種次序分 別遍歷出來(lái)：別遍歷出來(lái)： lr 第第7 7章章 47 (1) 訪問根，遍歷左子樹，遍歷右子樹（記做訪問根，遍歷左子樹，遍歷右子樹（記做dlr）。）。 (2) 訪問根，遍歷右子樹，遍歷左子樹（記做訪問根，遍歷右子樹，遍歷左子樹（記做drl）。）。 (3) 遍歷左子樹，訪問根，遍歷右子樹（記做遍歷左子樹，訪問根，遍

26、歷右子樹（記做ldr）。）。 (4) 遍歷左子樹，遍歷右子樹，訪問根（記做遍歷左子樹，遍歷右子樹，訪問根（記做lrd）。）。 (5) 遍歷右子樹，訪問根，遍歷左子樹（記做遍歷右子樹，訪問根，遍歷左子樹（記做rdl）。）。 (6) 遍歷右子樹，遍歷左子樹，訪問根（記做遍歷右子樹，遍歷左子樹，訪問根（記做rld）。）。 lr 第第7 7章章 48 我們稱我們稱 d l r（根左右）、（根左右）、 d r l 為為 先（根）序遍歷 l d r（左根右）、（左根右）、 r d l 為為 中（根）序遍歷 l r d（左右根）、（左右根）、 r l d 為為 后（根）序遍歷 先左后右先左后右 先右后左先右

27、后左 第第7 7章章 49 關(guān)于左右子樹的遍歷，可采取與整個(gè)二叉樹相關(guān)于左右子樹的遍歷，可采取與整個(gè)二叉樹相 同的方式來(lái)實(shí)現(xiàn)遍歷。同的方式來(lái)實(shí)現(xiàn)遍歷。 lr 下面，我們看具體的例子： 第第7 7章章 50 a d b c d l r a d l r d l r b d c d l r 第第7 7章章 51 a d b c l d r b l d r l d r a d c l d r 第第7 7章章 52 a d b c l r d l r d l r d a d c l r d b 第第7 7章章 53 思考題：寫出下圖二叉樹的遍歷順序 a bc de f g h 先序：先序： a b d

28、g c e h f 中序：中序：dg b a eh c f 后序：后序：gd b he f c a 第第7 7章章 54 已知二叉樹的先序和中序序列，構(gòu)造出相應(yīng)的二叉樹 先序：先序：abcdefghij 中序：中序：cdbfeaihgj 分析：分析：。 1、由先序知根為、由先序知根為a，則由中序知左子樹為，則由中序知左子樹為cdbf, 右子樹為右子樹為ihgj a c d b f ei h g j 第第7 7章章 55 先序：先序：abcdefghij 中序：中序：cdbfeaihgj 2 2、再分別在左、右子樹的序列中找出根、左子樹序列、再分別在左、右子樹的序列中找出根、左子樹序列、 右子樹

29、序列。右子樹序列。 a c d b f e i h g j b c df e g i hj 第第7 7章章 56 先序：先序：a bcdef ghij 中序：中序：cdbfe a ihgj c df ei hj a bg c d e f h i a bg c e h j fd i 第第7 7章章 57 7.3.1 二叉樹遍歷的概念 7.3.2 二叉樹遍歷的遞歸算法 7.3.3 二叉樹遍歷的非遞歸算法 第第7 7章章 58 先序遍歷（dlr）遞歸描述： 若二叉樹為空，若二叉樹為空， 則操作結(jié)束，則操作結(jié)束， 否則依次執(zhí)行如下否則依次執(zhí)行如下3 個(gè)操作：個(gè)操作： (1) 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)；

30、(2) 先序遍歷左子樹；先序遍歷左子樹； (3) 先序遍歷右子樹。先序遍歷右子樹。 這里，若t為根指針，則遍歷左右子樹時(shí)，是分別遍 歷以t-lchild 和t-rchild 為根指針的子樹。 由于各子樹的遍歷和整個(gè)二叉樹的遍歷方式相同， 因此，各子樹的遍歷可遞歸調(diào)用二叉樹的遍歷算法。 第第7 7章章 59 先序遍歷遞歸算法如下： preorder ( bitree *t) if ( t ) visite ( t ); preorder ( t-lchild ) ; preorder ( t-rchild ) ; 第第7 7章章 60 主程序主程序 pre( t ) 返回 返回 pre(t r)

31、; 返回 返回 pre(t r); a cb d t b visite(b); pre(t l); b t a visite(a); pre(t l); a t d printf(d); pre(t l); d t c visite(c); pre(t l); c 返回 t 左是空返回左是空返回 pre(t r); t 左是空返回左是空返回 t 右是空返回右是空返回 t 左是空返回左是空返回 t 右是空返回右是空返回 pre(t r); 先序序列：a b d c 第第7 7章章 61 中序遍歷遞歸算法中序遍歷遞歸算法 inorder ( t ) inorder ( bitree *t) if

32、( t ) inorder ( t-lchild ) ; visite ( t ); inorder ( t-rchild ) ; 第第7 7章章 62 后序遍歷遞歸算法后序遍歷遞歸算法 postorder ( t ) postorder ( bitree *t) if ( t ) postorder ( t-lchild ) ; postorder ( t-rchild ) ; visite ( t ); 第第7 7章章 63 7.3.1 二叉樹遍歷的概念 7.3.2 二叉樹遍歷的遞歸算法 7.3.3 二叉樹遍歷的非遞歸算法 第第7 7章章 64 討論：討論：對(duì)如圖所示的二叉樹對(duì)如圖所示的二

33、叉樹t，令，令p=t; （1）訪問根，輸出）訪問根，輸出p-data；令；令p=t-lchild 的非遞歸算法： a d b c t p p 第第7 7章章 65 （2）訪問根的左子樹）訪問根的左子樹p： 訪問訪問*p ，輸出，輸出p-data 再訪問以再訪問以*p為根的左、右子樹為根的左、右子樹 a d b c p 第第7 7章章 66 解決的方法： 使用一個(gè)棧，將遍歷過(guò)的結(jié)點(diǎn)的地址使用一個(gè)棧，將遍歷過(guò)的結(jié)點(diǎn)的地址p p依次入棧，依次入棧， 并同時(shí)訪問并同時(shí)訪問* *p p（p p為棧頂元素）的左孩子；當(dāng)訪問過(guò)棧為棧頂元素）的左孩子；當(dāng)訪問過(guò)棧 頂元素的右孩子后，將其出棧。頂元素的右孩子后，

34、將其出棧。 上例的二叉樹的非遞歸先序遍歷算法過(guò)程描述如下： 第第7 7章章 67 a d b c t p visite(p); / push(p); /a的地址入棧的地址入棧 p=棧頂棧頂-lchid; / visite(p); / push(p); /b b的地址入棧的地址入棧 p=棧頂棧頂-lchid; / p=null； / p=棧頂棧頂-rchid; / pop(top) / visite(p); / push(p); /d d的地址入棧的地址入棧 棧s top a的地址的地址 p b的地址的地址top p p d的地址的地址 d無(wú)左、右孩子，則d的地址出棧； p=棧頂棧頂-rchid

35、; / p c的地址的地址 建空棧s；p=t; p入棧 輸出 棧頂-data；p=棧頂-lchild p=棧頂-rchild；pop( )； p!=null 棧空 p= =null 結(jié)束 第第7 7章章 68 的非遞歸算法： 在搜索線經(jīng)過(guò)根時(shí)不訪問根，而先訪問根的左在搜索線經(jīng)過(guò)根時(shí)不訪問根，而先訪問根的左 子樹？利用棧結(jié)構(gòu)。子樹？利用棧結(jié)構(gòu)。 1 1、將根入棧，若其有左子樹，則再將左子樹的根入棧。、將根入棧，若其有左子樹，則再將左子樹的根入棧。 2 2、否則，訪問該結(jié)點(diǎn)，并將棧中結(jié)點(diǎn)依次出棧并訪問、否則，訪問該結(jié)點(diǎn)，并將棧中結(jié)點(diǎn)依次出棧并訪問; ; 3 3、若棧為空，則訪問最后一次出棧的結(jié)點(diǎn)的

36、右子樹、若棧為空，則訪問最后一次出棧的結(jié)點(diǎn)的右子樹, ,若若 其右子樹不空，重復(fù)其右子樹不空，重復(fù)1 1、2 2、3 3 。 4 4、否則，遍歷結(jié)束。、否則，遍歷結(jié)束。 第第7 7章章 69 后序遍歷的非遞歸算法較為復(fù)雜后序遍歷的非遞歸算法較為復(fù)雜, , 不僅在搜索線不僅在搜索線 , , 而且在后根遍而且在后根遍 歷它的左子樹之后歷它的左子樹之后, , 搜索線搜索線 。因此。因此, , 在搜索線第二次經(jīng)根結(jié)點(diǎn)時(shí)不能讓棧頂元素在搜索線第二次經(jīng)根結(jié)點(diǎn)時(shí)不能讓棧頂元素 （根）出棧（根）出棧, , 而是依據(jù)棧頂元素所表示的根去后根遍歷而是依據(jù)棧頂元素所表示的根去后根遍歷 它的右子樹它的右子樹; ; 搜

37、索線搜索線時(shí)時(shí), , 將其出棧將其出棧, , 并且并且。 的非遞歸算法： 第第7 7章章 70 對(duì)棧頂?shù)拿恳粋€(gè)元素，要訪問它的左右孩子對(duì)棧頂?shù)拿恳粋€(gè)元素，要訪問它的左右孩子 后，才將其出棧。后，才將其出棧。 要與棧頂元素接觸兩次后，才訪問該元素。這樣，要與棧頂元素接觸兩次后，才訪問該元素。這樣， 可設(shè)置一個(gè)可設(shè)置一個(gè)輔助變量用來(lái)記錄接觸該元素的次數(shù)。輔助變量用來(lái)記錄接觸該元素的次數(shù)。 第第7 7章章 71 7.1 二叉樹的概念 7.2 二叉樹的存儲(chǔ) 7.3 二叉樹的遍歷 7.4 線索二叉樹 7.5 二叉樹的應(yīng)用1基本算法 7.6 二叉樹的應(yīng)用2哈夫曼樹 7.7 二叉樹的應(yīng)用3二叉排序樹 7.8

38、 二叉樹的應(yīng)用3堆和堆排序 第第7 7章章 72 當(dāng)用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)時(shí)，可以很方當(dāng)用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)時(shí)，可以很方 便地找到某個(gè)結(jié)點(diǎn)的左右孩子；但一般情況下，無(wú)法直便地找到某個(gè)結(jié)點(diǎn)的左右孩子；但一般情況下，無(wú)法直 接找到該結(jié)點(diǎn)在某種遍歷序列中的前趨和后繼結(jié)點(diǎn)。接找到該結(jié)點(diǎn)在某種遍歷序列中的前趨和后繼結(jié)點(diǎn)。 求解二叉樹結(jié)點(diǎn)的前趨和后繼。 1 1、遍歷費(fèi)時(shí)間、遍歷費(fèi)時(shí)間 2 2、增設(shè)前趨、后繼指針域降低存儲(chǔ)空間的利、增設(shè)前趨、后繼指針域降低存儲(chǔ)空間的利 用率。用率。 3 3、利用二叉鏈表中的空指針域、利用二叉鏈表中的空指針域 。 第第7 7章章 73 具有具有n n個(gè)結(jié)點(diǎn)的

39、二叉鏈表中，一共由個(gè)結(jié)點(diǎn)的二叉鏈表中，一共由2n2n個(gè)指針個(gè)指針 域；又域；又 n n個(gè)結(jié)點(diǎn)中有個(gè)結(jié)點(diǎn)中有n-1n-1個(gè)孩子，即個(gè)孩子，即 2n2n個(gè)指針域個(gè)指針域 中，有中，有n-1n-1個(gè)用來(lái)指示結(jié)點(diǎn)的左右孩子，其余個(gè)用來(lái)指示結(jié)點(diǎn)的左右孩子，其余 。 第第7 7章章 74 7.4.1 線索二叉樹的概念 7.4.2 二叉樹的線索化 7.4.3 線索二叉樹的操作 第第7 7章章 75 利用二叉鏈表中的空指針域： 這種這種 稱為稱為 加上了線索的二叉鏈表稱為線索鏈表；加上了線索的二叉鏈表稱為線索鏈表； 相應(yīng)的二叉樹相應(yīng)的二叉樹 稱為稱為 線索二叉樹線索二叉樹 第第7 7章章 76 為區(qū)分孩子指針

40、和線索，對(duì)二叉鏈表中每個(gè)結(jié)點(diǎn)為區(qū)分孩子指針和線索，對(duì)二叉鏈表中每個(gè)結(jié)點(diǎn) 增設(shè)兩個(gè)標(biāo)志增設(shè)兩個(gè)標(biāo)志 ltag 和和 rtag ，并約定：，并約定： ltag = 0 lchild 指向該結(jié)點(diǎn)的左孩子指向該結(jié)點(diǎn)的左孩子 ltag = 1 lchild 指向該結(jié)點(diǎn)的前趨指向該結(jié)點(diǎn)的前趨 rtag = 0 rchild 指向該結(jié)點(diǎn)的右孩子指向該結(jié)點(diǎn)的右孩子 rtag = 1 rchild 指向該結(jié)點(diǎn)的后繼指向該結(jié)點(diǎn)的后繼 這樣，結(jié)點(diǎn)的結(jié)構(gòu)為：這樣，結(jié)點(diǎn)的結(jié)構(gòu)為： data ltag rtag lchildrchild 第第7 7章章 77 先序先序,中序和后序線索鏈表中序和后序線索鏈表 a 00 b

41、01 c 00 d 10 e 10 g 11 h 11 f 11 先序先序 abdgcehf 第第7 7章章 78 a 00 b 01 c 00 d 10 e 10 g 11 h 11 f 11 中序中序 dgbaehcf 第第7 7章章 79 a 00 b 01 c 00 d 10 e 10 g 11 h 11 f 11 后序后序 gdbhefca 第第7 7章章 80 7.4.1 線索二叉樹的概念 7.4.2 二叉樹的線索化 7.4.3 線索二叉樹的操作 第第7 7章章 81 即：將二叉樹中每個(gè)結(jié)點(diǎn)中的空的左右孩子指針域即：將二叉樹中每個(gè)結(jié)點(diǎn)中的空的左右孩子指針域 分別修改為指向其給定順序

42、（先序、中序、后序）的分別修改為指向其給定順序（先序、中序、后序）的 前趨和后繼結(jié)點(diǎn)。前趨和后繼結(jié)點(diǎn)。 這樣，每個(gè)結(jié)點(diǎn)的線索化操作應(yīng)包括以下內(nèi)容：這樣，每個(gè)結(jié)點(diǎn)的線索化操作應(yīng)包括以下內(nèi)容： (1) 若左子樹為空，則將其左孩子域線索化：若左子樹為空，則將其左孩子域線索化： (2) 若右子樹為空，則將其右孩子域線索化：若右子樹為空，則將其右孩子域線索化： 第第7 7章章 82 這樣，若對(duì)結(jié)點(diǎn)這樣，若對(duì)結(jié)點(diǎn)*p線索化，應(yīng)知道其前趨和后繼結(jié)線索化，應(yīng)知道其前趨和后繼結(jié) 點(diǎn)的地址。點(diǎn)的地址。 按照某種遍歷順序，當(dāng)遍歷到結(jié)點(diǎn)按照某種遍歷順序，當(dāng)遍歷到結(jié)點(diǎn)*p時(shí)，用時(shí)，用pre 記錄記錄 *p的前趨結(jié)點(diǎn)的地

43、址；但不知的前趨結(jié)點(diǎn)的地址；但不知*p的后繼結(jié)點(diǎn)的地址；的后繼結(jié)點(diǎn)的地址； 所以只能對(duì)所以只能對(duì)*p結(jié)點(diǎn)前趨線索化，不能對(duì)其后繼線索化結(jié)點(diǎn)前趨線索化，不能對(duì)其后繼線索化 。 第第7 7章章 83 對(duì)結(jié)點(diǎn)對(duì)結(jié)點(diǎn)*p的線索化分兩步進(jìn)行的線索化分兩步進(jìn)行： 當(dāng)*p 為當(dāng)前結(jié)點(diǎn)時(shí)，可進(jìn)行前趨線索化 p-lchild = pre 當(dāng)*p為當(dāng)前結(jié)點(diǎn)時(shí)，對(duì)其前趨*pre后繼線索化。 pre-rchild = p 111111 pre p 第第7 7章章 84 在某種順序的遍歷過(guò)程中，線索化各點(diǎn)。 該算法應(yīng)為相應(yīng)順序的遍歷算法的一種變化形式。 線索二叉樹中結(jié)點(diǎn)的類型說(shuō)明： typedef struct nod

44、e int ltag , rtag ; datatype data ; struct node *lchild ,*rchild ; bithrtr ; 第第7 7章章 85 二叉樹非空時(shí)，遍歷該二叉樹，對(duì)任一結(jié)點(diǎn)*p ，有： 若其前趨結(jié)點(diǎn)*pre 不空，且*pre 無(wú)右孩子， 即：pre-rtag = 1 , 則 將*pre 后繼線索化： pre-rchild = p ; 若*p 無(wú)左孩子， 則 p-ltag = 1 ,且 p-lchild = pre 若*p 無(wú)右孩子，則 p-rtag = 1 將pre 指向下一結(jié)點(diǎn) *p ，即 pre = p 第第7 7章章 86 重復(fù)上述4步，繼續(xù)遍歷

45、其它結(jié)點(diǎn)。 bithrtr *pre = null; prethread(bithrtr *root ) bithrtr *p ; p = root ; 1111 11 第第7 7章章 87 if ( p) if ( pre if (p-lchild =null) p-ltag = 1 ; p-lchild = pre ; if (p-rchild = null) p-rtag = 1 ; pre = p ; prethread( p-lchild ) ; prethread( p-rchild ) ; 第第7 7章章 88 7.4.1 線索二叉樹的概念 7.4.2 二叉樹的線索化 7.4.3

46、 線索二叉樹的操作 第第7 7章章 89 即：求解給定結(jié)點(diǎn)在指定次序下的前趨和后繼。 共有三組6個(gè)問題： 先序線索二叉樹中求解先序前趨和后繼先序線索二叉樹中求解先序前趨和后繼 中序線索二叉樹中求解中序前趨和后繼中序線索二叉樹中求解中序前趨和后繼 后序線索二叉樹中求解后序前趨和后繼后序線索二叉樹中求解后序前趨和后繼 下面，我們重點(diǎn)討論先序后繼先序后繼、先序前趨先序前趨、及中序中序 后繼后繼的求解： 第第7 7章章 90 1、先序后繼、先序后繼（先序遍歷次序中查找某結(jié)點(diǎn)的后繼） a bg d c 先序：根左右先序：根左右 abcgd 若若p左子樹不空，左子樹不空，p-lchild指向它的后繼指向它

47、的后繼 否則若有右孩子，否則若有右孩子，p-rchild指向它的后繼指向它的后繼 否則，否則，p-rchild 指向后繼。指向后繼。 第第7 7章章 91 算法描述如下：算法描述如下： bitree *presuc( bitree *p ) if ( p-ltag = = 0 ) return ( p-lchild ) ; else return ( r-rchild ) ; 第第7 7章章 92 分析：分析： 根沒有前趨 若*p是父結(jié)點(diǎn)的左孩子，則*p 的前趨為父結(jié)點(diǎn) 2、先序前驅(qū)、先序前驅(qū)（先序遍歷次序中查找某結(jié)點(diǎn)的前驅(qū)） a bg d c 若若*p是父結(jié)點(diǎn)的右孩子：是父結(jié)點(diǎn)的右孩子： 若

48、若*p無(wú)左兄弟，則無(wú)左兄弟，則*p 的前趨為父結(jié)點(diǎn)；的前趨為父結(jié)點(diǎn)； 若若*p有左兄弟，則有左兄弟，則*p的前趨為其左兄弟子樹中最右下的前趨為其左兄弟子樹中最右下 的葉子結(jié)點(diǎn)。的葉子結(jié)點(diǎn)。 第第7 7章章 93 若若*p 有右孩子，則有右孩子，則 其右子樹中最左下的結(jié)點(diǎn)其右子樹中最左下的結(jié)點(diǎn) 為其后繼。為其后繼。 否則，若否則，若*p無(wú)右孩子，無(wú)右孩子， 則則p-rchild 指向其后繼。指向其后繼。 3、中序后繼、中序后繼（中序遍歷次序中查找某結(jié)點(diǎn)的后繼） a b c d e f g x z 中序：中序： axzegcfbd 第第7 7章章 94 返回返回 p-rchild *p有右孩子有右

49、孩子 q = p-rchild *q 有左孩子有左孩子 q = q-lchild 返回返回q 第第7 7章章 95 7.1 二叉樹的概念 7.2 二叉樹的存儲(chǔ) 7.3 二叉樹的遍歷 7.4 線索二叉樹 7.5 二叉樹的應(yīng)用1基本算法 7.6 二叉樹的應(yīng)用2哈夫曼樹 7.7 二叉樹的應(yīng)用3二叉排序樹 7.8 二叉樹的應(yīng)用3堆和堆排序 第第7 7章章 96 二叉樹的遞歸遍歷思想將二叉樹的遍歷簡(jiǎn)化為二叉樹的遞歸遍歷思想將二叉樹的遍歷簡(jiǎn)化為 對(duì)根結(jié)點(diǎn)的訪問。對(duì)根結(jié)點(diǎn)的訪問。 利用這一特點(diǎn)，適當(dāng)修改訪問操作的內(nèi)容，就利用這一特點(diǎn)，適當(dāng)修改訪問操作的內(nèi)容，就 可以實(shí)現(xiàn)對(duì)根結(jié)點(diǎn)的多種形式的操作，也就可以得可

50、以實(shí)現(xiàn)對(duì)根結(jié)點(diǎn)的多種形式的操作，也就可以得 到許多問題的求解算法。到許多問題的求解算法。 第第7 7章章 97 例1：按先序遍歷序列建立二叉樹的二叉鏈表 按先序遍歷的順序，將每次訪問根結(jié)點(diǎn)的操作按先序遍歷的順序，將每次訪問根結(jié)點(diǎn)的操作 改為新建一個(gè)結(jié)點(diǎn)。改為新建一個(gè)結(jié)點(diǎn)。 算法描述如下：算法描述如下： 第第7 7章章 98 bitree *crt_bt_pre(bitree *bt) char ch; printf(ch=); scanf(%c, if(ch= = ) bt=null; else bt=malloc(sizeof(bitree); bt-data=ch; bt-lchild=c

51、rt_bt_pre(bt-lchild); bt-rchild=crt_bt_pre(bt-rchild); return(bt); 第第7 7章章 99 例2：統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù) 設(shè)計(jì)算以設(shè)計(jì)算以bt為根指針的二叉樹的葉子結(jié)點(diǎn)數(shù)的函數(shù)為為根指針的二叉樹的葉子結(jié)點(diǎn)數(shù)的函數(shù)為int countleaf (bitree *bt)，分析如下：，分析如下： (1) 若若btnull，則葉子數(shù)為，則葉子數(shù)為0； (2) 否則，可能有兩種情況：否則，可能有兩種情況： bt 的根結(jié)點(diǎn)無(wú)左右孩子，其本身為葉子，則的根結(jié)點(diǎn)無(wú)左右孩子，其本身為葉子，則 整個(gè)二叉樹的葉子結(jié)點(diǎn)數(shù)為整個(gè)二叉樹的葉子結(jié)點(diǎn)數(shù)為1；

52、bt 的左右子樹至少有一個(gè)不空，則二叉樹的左右子樹至少有一個(gè)不空，則二叉樹bt 中葉子結(jié)點(diǎn)的數(shù)目是其左右子樹中葉子數(shù)之和。而其中葉子結(jié)點(diǎn)的數(shù)目是其左右子樹中葉子數(shù)之和。而其 左右子樹中葉子數(shù)可通過(guò)調(diào)用函數(shù)左右子樹中葉子數(shù)可通過(guò)調(diào)用函數(shù) countleaf (bt-lchild)和和countleaf (bt-rchild) 來(lái)求得。來(lái)求得。 第第7 7章章 100 算法描述如下：算法描述如下： #include #include int countleaf (bitree *bt) if (bt= =null) return (0); else if (bt-lchild= =null els

53、e return (countleaf(bt-lchild)+countleaf(bt-rchild); 第第7 7章章 101 void main() bitree *head= null; int count; head=crt_bt_pre(head); count = countleaf(head); printf(count of leaf node is %dn, count); 第第7 7章章 102 例3：設(shè)計(jì)算法求解求二叉樹的深度 算法分析如下：算法分析如下： 若二叉樹若二叉樹btbt為空，則其深度為為空，則其深度為0 0，算法結(jié)束；，算法結(jié)束； 否則，若否則，若btbt不為

54、空，則二叉樹不為空，則二叉樹btbt的深度應(yīng)該的深度應(yīng)該 是其左右子樹的深度的最大值加是其左右子樹的深度的最大值加1 1。 算法描述如下：算法描述如下： 第第7 7章章 103 int treedepth(bitree *bt) if ( bt = =null ) return (0); else return ( max ( treedepth(bt-lchild), treedepth(bt-rchild ) ) +1); 第第7 7章章 104 void main() bitree *head=null; int high; head=crt_bt_pre(head); high = t

55、reedepth(head); printf(depth of tree is %dn,high); 第第7 7章章 105 7.1 二叉樹的概念 7.2 二叉樹的存儲(chǔ) 7.3 二叉樹的遍歷 7.4 線索二叉樹 7.5 二叉樹的應(yīng)用1基本算法 7.6 二叉樹的應(yīng)用2哈夫曼樹 7.7 二叉樹的應(yīng)用3二叉排序樹 7.8 二叉樹的應(yīng)用3堆和堆排序 第第7 7章章 106 7.6.1 基本術(shù)語(yǔ) 7.6.2 構(gòu)造哈夫曼樹 7.6.3 哈夫曼樹的應(yīng)用 7.6 二叉樹的應(yīng)用2哈夫曼樹 第第7 7章章 107 1路徑和路徑長(zhǎng)度 在一棵二叉樹中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩在一棵二叉樹中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的

56、孩 子或子孫結(jié)點(diǎn)之間的通路，稱為子或子孫結(jié)點(diǎn)之間的通路，稱為。 通路中分支的數(shù)目稱為通路中分支的數(shù)目稱為。 若規(guī)定根結(jié)點(diǎn)的層數(shù)為若規(guī)定根結(jié)點(diǎn)的層數(shù)為1 1，則從根結(jié)點(diǎn)到第，則從根結(jié)點(diǎn)到第l l層結(jié)層結(jié) 點(diǎn)的路徑長(zhǎng)度為點(diǎn)的路徑長(zhǎng)度為l-1l-1。 第第7 7章章 108 2結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度 若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值， 則這個(gè)數(shù)值稱為該則這個(gè)數(shù)值稱為該。 為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之 間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。 第第7 7章章 109 3二叉樹的帶權(quán)路徑長(zhǎng)度 二叉樹的帶權(quán)路徑長(zhǎng)度規(guī)定為

57、所有葉子結(jié)點(diǎn)的帶權(quán)二叉樹的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán) 路徑長(zhǎng)度之和，記為路徑長(zhǎng)度之和，記為wpl= 其中其中n 為葉子結(jié)點(diǎn)數(shù)目，為葉子結(jié)點(diǎn)數(shù)目，wi為第為第i 個(gè)葉子結(jié)點(diǎn)的權(quán)個(gè)葉子結(jié)點(diǎn)的權(quán) 值，值，li 為第為第i 個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。 n i ii lw 1 第第7 7章章 110 7.6.1 基本術(shù)語(yǔ) 7.6.2 構(gòu)造哈夫曼樹 7.6.3 哈夫曼樹的應(yīng)用 7.6 二叉樹的應(yīng)用2哈夫曼樹 第第7 7章章 111 1哈夫曼樹的定義 在一棵二叉樹中，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱在一棵二叉樹中，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱 這樣的二叉樹為最優(yōu)二叉樹；這樣的二叉樹為最優(yōu)

58、二叉樹； 也稱為哈夫曼樹也稱為哈夫曼樹(huffman tree)。 下面我們考察用權(quán)值分別為下面我們考察用權(quán)值分別為7,5,2,47,5,2,4的的4 4個(gè)結(jié)點(diǎn)，構(gòu)個(gè)結(jié)點(diǎn)，構(gòu) 造有造有4 4個(gè)葉子結(jié)點(diǎn)的二叉樹個(gè)葉子結(jié)點(diǎn)的二叉樹: : 第第7 7章章 112 abcd 7524 wpl=7*2+5*2+2*2+4*2=36 d c ab 2 4 75 wpl=7*3+5*3+2*1+4*2=46 a b cd 7 5 24 wpl=7*1+5*2+2*3+4*3=35 第第7 7章章 113 可以看出： 在葉子數(shù)目及權(quán)值相同的二叉樹中，完全二叉樹在葉子數(shù)目及權(quán)值相同的二叉樹中，完全二叉樹 不一

59、定是最優(yōu)二叉樹。不一定是最優(yōu)二叉樹。 一般情況下，一般情況下，最優(yōu)二叉樹中，權(quán)值越大的葉子離最優(yōu)二叉樹中，權(quán)值越大的葉子離 根越近。根越近。 第第7 7章章 114 2哈夫曼樹的構(gòu)造 假設(shè)有假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子個(gè)葉子 結(jié)點(diǎn)。結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為個(gè)權(quán)值分別設(shè)為 w1,w2,wn,則哈夫曼樹的構(gòu)則哈夫曼樹的構(gòu) 造規(guī)則為：造規(guī)則為： (1) 將這將這n個(gè)結(jié)點(diǎn)看作是個(gè)結(jié)點(diǎn)看作是n 棵單結(jié)點(diǎn)二叉樹，結(jié)點(diǎn)的權(quán)棵單結(jié)點(diǎn)二叉樹，結(jié)點(diǎn)的權(quán) 值分別是值分別是w1, w2, , wn ；這；這n棵二叉樹構(gòu)成一個(gè)二叉樹棵二叉樹構(gòu)成一個(gè)二叉樹 的集合的集合m。 這

60、這n棵單結(jié)點(diǎn)的二叉樹中，這些結(jié)點(diǎn)既是根結(jié)點(diǎn)又棵單結(jié)點(diǎn)的二叉樹中，這些結(jié)點(diǎn)既是根結(jié)點(diǎn)又 是葉子結(jié)點(diǎn)。是葉子結(jié)點(diǎn)。 第第7 7章章 115 (2) 在集合在集合m中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的二叉樹合中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的二叉樹合 并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán) 值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和； (3) 從集合從集合m中刪除選取的兩棵二叉樹，并將新樹加入中刪除選取的兩棵二叉樹，并將新樹加入 該集合；該集合； (4) 重復(fù)重復(fù)(2)、(3)步，直到集合步，直到集合m中只剩一棵二叉樹為止，中只剩一棵二叉樹