數(shù)據(jù)結(jié)構(gòu)之樹(shù)和二叉樹(shù)

第6章樹(shù)和二叉樹(shù)6.1樹(shù)的定義和基本術(shù)語(yǔ)6.2二叉樹(shù)6.3遍歷二叉樹(shù)6.4線索二叉樹(shù)6.5樹(shù)和森林6.6哈夫曼樹(shù)教學(xué)目的的、要求求1．領(lǐng)會(huì)會(huì)樹(shù)和二二叉樹(shù)的的類型定定義，理理解樹(shù)和和二叉樹(shù)樹(shù)的結(jié)構(gòu)構(gòu)差別。。2．熟記記二叉樹(shù)樹(shù)的主要要特性，，并掌握握它們的的證明方方法。3．熟練練掌握二二叉樹(shù)的的各種遍遍歷算法法，并能能靈活運(yùn)運(yùn)用遍歷歷算法實(shí)實(shí)現(xiàn)二叉叉樹(shù)的其其它操作作。4．理解解二叉樹(shù)樹(shù)的線索索化過(guò)程程以及在在中序線線索化樹(shù)樹(shù)上找給給定結(jié)點(diǎn)點(diǎn)的前驅(qū)驅(qū)和后繼繼的方法法。5．熟練練掌握二二叉樹(shù)和和樹(shù)的各各種存儲(chǔ)儲(chǔ)結(jié)構(gòu)及及其建立立的算法法。6．學(xué)會(huì)會(huì)編寫(xiě)實(shí)實(shí)現(xiàn)樹(shù)的的各種操操作的算算法。7．了解解最優(yōu)樹(shù)樹(shù)的特性性，掌握握建立最最優(yōu)樹(shù)和和赫夫曼曼編碼的的方法。。6.1樹(shù)樹(shù)的定定義和基基本術(shù)語(yǔ)語(yǔ)6.1..1樹(shù)的的定義樹(shù)是由n（n≥≥0）個(gè)個(gè)結(jié)點(diǎn)組組成的有有限集合合。若n=0，，稱為空空樹(shù)；若若n>0，則：：①有一個(gè)個(gè)特定的的稱為根根（root））的結(jié)點(diǎn)點(diǎn)。它只只有直接接后繼，，但沒(méi)有有直接前前驅(qū)；②除根結(jié)結(jié)點(diǎn)以外外的其它它結(jié)點(diǎn)可可以劃分分為m（（m≥0）個(gè)互互不相交交的有限限集合T0，T1，…，Tm-1，每個(gè)集集合Ti（i=0,1,,…,m-1））又是一一棵樹(shù)，，稱為根根的子樹(shù)樹(shù)，每棵棵子樹(shù)的的根結(jié)點(diǎn)點(diǎn)有且僅僅有一個(gè)個(gè)直接前前驅(qū)，但但可以有有0個(gè)或或多個(gè)直直接后繼繼。由此可知知，樹(shù)的的定義是是一個(gè)遞遞歸的定定義，即即樹(shù)的定定義中又又用到了了樹(shù)的概概念。樹(shù)的結(jié)構(gòu)構(gòu)參見(jiàn)下下圖：圖6.1樹(shù)的結(jié)結(jié)構(gòu)在圖6..1(c)中，，樹(shù)的根根結(jié)點(diǎn)為為A，該該樹(shù)還可可以分為為三個(gè)互互不相交交子集T0，T1，T2，其中T0={B，，E，F(xiàn)，J，，K，L}，T1={C，，G}，，T2={D，，H，I，M}}，其中中的T0，T1，T2都是樹(shù)，，稱為圖圖6.1(C))中樹(shù)的的子樹(shù)，，而T0，T1，T2又可以分分解成若若干棵不不相交子子樹(shù)。如如T0可以分解解成T00，T01兩個(gè)不相相交子集集，T00={E，，J，K，L}}，T01={F}}，而T00又可以分分為三個(gè)個(gè)不相交交子集T000，T001，T002，其中，，T000={J}}，T001={K}}，T002={L}}。樹(shù)的抽象象數(shù)據(jù)類類型定義義見(jiàn)教材材P118-1196.1..2基基本術(shù)語(yǔ)語(yǔ)1.結(jié)結(jié)點(diǎn)指樹(shù)中的的一個(gè)數(shù)數(shù)據(jù)元素素，一般般用一個(gè)個(gè)字母表表示。2.度度一個(gè)結(jié)點(diǎn)點(diǎn)包含子子樹(shù)的數(shù)數(shù)目，稱稱為該結(jié)結(jié)點(diǎn)的度度。3.樹(shù)樹(shù)葉（葉葉子）度為0的的結(jié)點(diǎn)，，稱為葉葉子結(jié)點(diǎn)點(diǎn)或樹(shù)葉葉，也叫叫終端結(jié)結(jié)點(diǎn)。4.孩孩子結(jié)點(diǎn)點(diǎn)若結(jié)點(diǎn)X有子樹(shù)樹(shù)，則子子樹(shù)的根根結(jié)點(diǎn)為為X的孩孩子結(jié)點(diǎn)點(diǎn)，也稱稱為孩子子，兒子子，子女女等。如如圖6..1（c）中A的孩子子為B，，C，D。5.雙雙親結(jié)點(diǎn)點(diǎn)若結(jié)點(diǎn)X有子女女Y，則則X為Y的雙親親結(jié)點(diǎn)。。6.祖祖先結(jié)點(diǎn)點(diǎn)從根結(jié)點(diǎn)點(diǎn)到該結(jié)結(jié)點(diǎn)所經(jīng)經(jīng)過(guò)分枝枝上的所所有結(jié)點(diǎn)點(diǎn)為該結(jié)結(jié)點(diǎn)的祖祖先，如如圖6--1（c）中M的祖先先有A，，D，，H。。7.子子孫結(jié)點(diǎn)點(diǎn)某一結(jié)點(diǎn)點(diǎn)的子女女及子女女的子女女都為該該結(jié)點(diǎn)子子孫。8.兄兄弟結(jié)點(diǎn)點(diǎn)具有同一一個(gè)雙親親的結(jié)點(diǎn)點(diǎn)，稱為為兄弟結(jié)結(jié)點(diǎn)。9.分分枝結(jié)點(diǎn)點(diǎn)除葉子結(jié)結(jié)點(diǎn)外的的所有結(jié)結(jié)點(diǎn)，為為分枝結(jié)結(jié)點(diǎn)，也也叫非終終端結(jié)點(diǎn)點(diǎn)。10.層層數(shù)根結(jié)點(diǎn)的的層數(shù)為為1，其其它結(jié)點(diǎn)點(diǎn)的層數(shù)數(shù)為從根根結(jié)點(diǎn)到到該結(jié)點(diǎn)點(diǎn)所經(jīng)過(guò)過(guò)的分支支數(shù)目再再加1。。11.樹(shù)樹(shù)的深深度（高高度）樹(shù)中結(jié)點(diǎn)點(diǎn)所處的的最大層層數(shù)稱為為樹(shù)的高高度，如如空樹(shù)的的高度為為0，只只有一個(gè)個(gè)根結(jié)點(diǎn)點(diǎn)的樹(shù)高高度為1。12.樹(shù)樹(shù)的度度樹(shù)中結(jié)點(diǎn)點(diǎn)度的最最大值稱稱為樹(shù)的的度。13.有有序樹(shù)樹(shù)若一棵樹(shù)樹(shù)中所有有子樹(shù)從從左到右右的排序序是有順順序的，，不能顛顛倒次序序。稱該該樹(shù)為有有序樹(shù)。。14.無(wú)無(wú)序樹(shù)樹(shù)若一棵樹(shù)樹(shù)中所有有子樹(shù)的的次序無(wú)無(wú)關(guān)緊要要，則稱稱為無(wú)序序樹(shù)。15．森森林若干棵互互不相交交的樹(shù)組組成的集集合為森森林。一一棵樹(shù)可可以看成成是一個(gè)個(gè)特殊的的森林。。6.1..3樹(shù)樹(shù)的表示示1.樹(shù)樹(shù)形結(jié)構(gòu)構(gòu)表示法法2.凹凹入法表表示法圖6.1（c））的樹(shù)的的凹入法法表示3.嵌嵌套集合合表示法法圖6.1（c））的嵌套套集合表表示4.廣廣義表表表示法對(duì)圖6--1（c）的樹(shù)樹(shù)結(jié)構(gòu)，，廣義表表表示法法可表示示為：（A（B（E（（J，K，L）），F(xiàn)）），C（（G），，D（H（M）），I））））6.1..4樹(shù)樹(shù)的性質(zhì)質(zhì)性質(zhì)1樹(shù)樹(shù)中中的結(jié)點(diǎn)點(diǎn)數(shù)等于于所有結(jié)結(jié)點(diǎn)的度度加1。。證明：根根據(jù)樹(shù)的的定義，，在一棵棵樹(shù)中，，除根結(jié)結(jié)點(diǎn)以外外，每個(gè)個(gè)結(jié)點(diǎn)有有且僅有有一個(gè)直直接前驅(qū)驅(qū)，也就就是說(shuō)，，每個(gè)結(jié)結(jié)點(diǎn)與指指向它的的一個(gè)分分支一一一對(duì)應(yīng)，，所以，，除根結(jié)結(jié)點(diǎn)以外外的結(jié)點(diǎn)點(diǎn)數(shù)等于于所有結(jié)結(jié)點(diǎn)的分分支數(shù)（（即度數(shù)數(shù)），而而根結(jié)點(diǎn)點(diǎn)無(wú)直接接前驅(qū)，，因此，，樹(shù)中的的結(jié)點(diǎn)數(shù)數(shù)等于所所有結(jié)點(diǎn)點(diǎn)的度數(shù)數(shù)加1。。性質(zhì)2度度為為k的樹(shù)樹(shù)中第i層上最最多有ki-1個(gè)結(jié)點(diǎn)（（i≥1）。下面用數(shù)數(shù)學(xué)歸納納法證明明：對(duì)于i==1，顯顯然成立立，假設(shè)設(shè)對(duì)于i-1層層，上述述條件成成立，即即第i--1層最最多有ki-2個(gè)結(jié)點(diǎn)，，對(duì)于第i層，結(jié)結(jié)點(diǎn)數(shù)最最多為第第i-1層結(jié)點(diǎn)點(diǎn)數(shù)的k倍（因因?yàn)槎葹闉閗），，故第i層的結(jié)結(jié)點(diǎn)數(shù)為為ki-2*k=ki-1。性質(zhì)3深深度為為h的k叉樹(shù)樹(shù)最多有有個(gè)個(gè)結(jié)點(diǎn)點(diǎn)。證明：由性質(zhì)2可知，，若每一一層的結(jié)結(jié)點(diǎn)數(shù)最最多，則則整個(gè)k叉樹(shù)結(jié)結(jié)點(diǎn)數(shù)最最多，共共有

當(dāng)一棵K叉樹(shù)上上的結(jié)點(diǎn)點(diǎn)數(shù)達(dá)到到時(shí)時(shí)，稱為為滿K叉叉樹(shù)。性質(zhì)4具具有n個(gè)結(jié)點(diǎn)點(diǎn)的k叉叉樹(shù)的最最小深度度為。。（表示示取不小小于x的的最小整整數(shù)）證明：設(shè)設(shè)具有n個(gè)結(jié)點(diǎn)點(diǎn)的k叉叉樹(shù)的深深度為h，在該該樹(shù)的前前面h--1層都都是滿的的，即每每一層的的結(jié)點(diǎn)數(shù)數(shù)等于ki-1個(gè)(1≤≤i≤h-1))，第h層（即即最后一一層）的的結(jié)點(diǎn)數(shù)數(shù)可能滿滿，也可可能不滿滿，這時(shí)時(shí)，該樹(shù)樹(shù)具有最最小的深深度。由性質(zhì)3知道，，結(jié)點(diǎn)數(shù)數(shù)n應(yīng)滿滿足下面面條件：：通過(guò)轉(zhuǎn)換換為：kh-1<n(k-1))+1≤≤kh，再取以以k為底底的對(duì)數(shù)數(shù)后，可可以得到到：h-1<<logk(n(k-1))+1))≤h即有：logk(n(k-1))+1))≤h<<logk(n(k-1))+1))+1，，而h只只能取整整數(shù)，所所以，該該k叉樹(shù)樹(shù)的最小小深度為為：h=6.2二二叉樹(shù)樹(shù)為何要重重點(diǎn)研究究每結(jié)點(diǎn)點(diǎn)最多只只有兩個(gè)個(gè)"叉叉"的的樹(shù)？①二叉樹(shù)樹(shù)的結(jié)構(gòu)構(gòu)最簡(jiǎn)單單，規(guī)律律性最強(qiáng)強(qiáng)；②可以證證明，所所有樹(shù)都都能轉(zhuǎn)為為唯一對(duì)對(duì)應(yīng)的二二叉樹(shù)，，不失一一般性。。6.2..1二二叉樹(shù)的的定義和樹(shù)結(jié)構(gòu)構(gòu)定義類類似，二二叉樹(shù)的的定義也也可以遞遞歸形式式給出：：二叉樹(shù)是是n（n≥0））個(gè)結(jié)點(diǎn)點(diǎn)的有限限集，它它或者是是空集（（n=0），或或者由一一個(gè)根結(jié)結(jié)點(diǎn)及兩兩棵不相相交的左子樹(shù)和右子樹(shù)組成。二叉樹(shù)的的特點(diǎn)是是每個(gè)結(jié)結(jié)點(diǎn)最多多有兩個(gè)個(gè)孩子，，或者說(shuō)說(shuō)，在二二叉樹(shù)中中，不存存在度大大于2的的結(jié)點(diǎn)，，并且二二叉樹(shù)是是有序樹(shù)（樹(shù)為無(wú)無(wú)序樹(shù)）），其子子樹(shù)的順順序不能能顛倒，，因此，，二叉樹(shù)樹(shù)有五種種不同的的形態(tài)，，參見(jiàn)圖圖6.5。圖6.5二叉叉樹(shù)的五五種不同同形態(tài)問(wèn)：具有有3個(gè)結(jié)結(jié)點(diǎn)的二二叉樹(shù)可可能有幾幾種不同同形態(tài)？？有五種二叉樹(shù)的的的抽象象數(shù)據(jù)類類型定義義見(jiàn)教材材P121。性質(zhì)1二叉樹(shù)的的第i層層結(jié)點(diǎn)數(shù)數(shù)，最多多為2i-1個(gè)（i≥≥1）。。性質(zhì)2深度為k的二叉叉樹(shù)最大大結(jié)點(diǎn)數(shù)數(shù)為2k-1（i≥1）。性質(zhì)3對(duì)任意一一棵二叉叉樹(shù)，如如果葉子子結(jié)點(diǎn)個(gè)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)點(diǎn)個(gè)數(shù)為為n2，則有n0=n2+1。證明：設(shè)設(shè)二叉樹(shù)樹(shù)中度為為1的結(jié)結(jié)點(diǎn)個(gè)數(shù)數(shù)為n1，根據(jù)二二叉樹(shù)的的定義可可知，該該二叉樹(shù)樹(shù)的結(jié)點(diǎn)點(diǎn)數(shù)n==n0+n1+n2。又因?yàn)樵谠诙鏄?shù)樹(shù)中，度度為0的的結(jié)點(diǎn)沒(méi)沒(méi)有孩子子，度為為1的結(jié)結(jié)點(diǎn)有1個(gè)孩孩子，度度為2的的結(jié)點(diǎn)有有2個(gè)結(jié)結(jié)孩子，，故該二二叉樹(shù)的的孩子結(jié)結(jié)點(diǎn)數(shù)為為n0*0+n1*1+n2*2。。而一棵二二叉樹(shù)中中，除根根結(jié)點(diǎn)外外所有的的結(jié)點(diǎn)都都為孩子子結(jié)點(diǎn)，，故該二二叉樹(shù)的的結(jié)點(diǎn)數(shù)數(shù)應(yīng)為孩孩子結(jié)點(diǎn)點(diǎn)數(shù)加1即：n=n0*0+n1*1+n2*2+1。因此，有有n==n0+n1+n2=n0*0+n2*1+n2*2+1，最后后得到n0=n2+1。為繼續(xù)給給出二叉叉樹(shù)的其其它性質(zhì)質(zhì)，先定定義兩種種特殊的的二叉樹(shù)樹(shù)。①滿二叉樹(shù)樹(shù)深度為k具有2k-1個(gè)結(jié)點(diǎn)的的二叉樹(shù)樹(shù)，稱為為滿二叉叉樹(shù)。從上面滿滿二叉樹(shù)樹(shù)定義可可知，必必須是二二叉樹(shù)的的每一層層上的結(jié)結(jié)點(diǎn)數(shù)都都達(dá)到最最大，否否則就不不是滿二二叉樹(shù)。。②完全二叉叉樹(shù)對(duì)滿二叉叉樹(shù)的結(jié)結(jié)點(diǎn)，從從根結(jié)點(diǎn)點(diǎn)起，自自上而下下，自左左至右進(jìn)進(jìn)行連續(xù)續(xù)編號(hào)。。如果一棵棵具有n個(gè)結(jié)點(diǎn)點(diǎn)的深度度為k的的二叉樹(shù)樹(shù)，它的的每一個(gè)個(gè)結(jié)點(diǎn)都都與深度度為k的的滿二叉叉樹(shù)中編編號(hào)為1~n的結(jié)點(diǎn)點(diǎn)一一對(duì)對(duì)應(yīng)，則則稱這棵棵二叉樹(shù)樹(shù)為完全全二叉樹(shù)樹(shù)。從滿二叉叉樹(shù)及完完全二叉叉樹(shù)定義義可以知知道，滿滿二叉樹(shù)樹(shù)一定是一棵完完全二叉叉樹(shù)，反反之完全全二叉樹(shù)樹(shù)不一定是一棵滿滿二叉樹(shù)樹(shù)。滿二叉樹(shù)樹(shù)的葉子子結(jié)點(diǎn)全全部在最最底層，，而完全全二叉樹(shù)樹(shù)的葉子子結(jié)點(diǎn)可可以分布布在最下面兩兩層。深度為為4的滿滿二叉樹(shù)樹(shù)和完全全二叉樹(shù)樹(shù)如圖6.6所所示。圖6.6滿二二叉樹(shù)和和完全二二叉樹(shù)性質(zhì)4具有n個(gè)個(gè)結(jié)點(diǎn)的的完全二二叉樹(shù)深深度為或或。。性質(zhì)5如果將一一棵有n個(gè)結(jié)點(diǎn)點(diǎn)的完全全二叉樹(shù)樹(shù)從上到到下，從從左到右右對(duì)結(jié)點(diǎn)點(diǎn)編號(hào)1，2，，…，n，并簡(jiǎn)簡(jiǎn)稱編號(hào)號(hào)為i的的結(jié)點(diǎn)為為i(1≤i≤≤n)，，則有如如下結(jié)論論成立：：①若i=1，，則結(jié)點(diǎn)點(diǎn)i為根根結(jié)點(diǎn)，，無(wú)雙親親，否則則i的雙雙親為；；②若2i>n，，則結(jié)點(diǎn)點(diǎn)i無(wú)左左孩子，，否則i的左孩孩子為2i。即即滿足2i>n的結(jié)點(diǎn)點(diǎn)為葉子子結(jié)點(diǎn)；；③若2i+1>>n，則則結(jié)點(diǎn)i無(wú)右孩孩子，否否則i的的右孩子子為2i+1；；④若結(jié)點(diǎn)點(diǎn)i為奇奇數(shù)且不不等于1，則它它的左兄兄弟為i-1；；⑤若結(jié)點(diǎn)點(diǎn)i為偶偶數(shù)且不不等于n，它的的右兄弟弟為i++1；⑥結(jié)點(diǎn)i所在層層數(shù)(層層次)為為；；6.2..3二二叉樹(shù)的的存貯結(jié)結(jié)構(gòu)1.順順序存貯貯結(jié)構(gòu)按二叉樹(shù)樹(shù)的結(jié)點(diǎn)點(diǎn)"自上而下下、從左左至右"編號(hào)，，用一組組連續(xù)的的存儲(chǔ)單單元存儲(chǔ)儲(chǔ)。若該二叉叉樹(shù)為非非完全二二叉樹(shù)，，則必須須將相應(yīng)應(yīng)位置空空出來(lái)，，使存放放的結(jié)果果符合完完全二叉叉樹(shù)形狀狀。圖6.7二叉叉樹(shù)的順順序存儲(chǔ)儲(chǔ)對(duì)于一棵棵二叉樹(shù)樹(shù)，若采采用順序序存貯時(shí)時(shí)，當(dāng)它它為完全全二叉樹(shù)樹(shù)時(shí)，比比較方便便,若為為非完全全二叉樹(shù)樹(shù)，將會(huì)會(huì)浪費(fèi)大大量存貯貯存貯單單元。最最壞的非非完全二二叉樹(shù)是是全部只只有右分分支，設(shè)設(shè)高度為為K，則則需占用用2K-1個(gè)存貯單單元，而而實(shí)際只只有k個(gè)個(gè)元素，，實(shí)際只只需k個(gè)個(gè)存儲(chǔ)單單元。因因此，對(duì)對(duì)于非完完全二叉叉樹(shù)，宜宜采用下下面的鏈鏈?zhǔn)酱鎯?chǔ)儲(chǔ)結(jié)構(gòu)。。2.二二叉鏈表表存貯結(jié)結(jié)構(gòu)⑴二叉叉鏈表表表示將一個(gè)結(jié)結(jié)點(diǎn)分成成三部分分，一部部分存放放結(jié)點(diǎn)本本身信息息，另外外兩部分分為指針針，分別別存放左左、右孩孩子的地地址。注：如果果需要倒倒查某結(jié)結(jié)點(diǎn)的雙雙親，可可以再增增加一個(gè)個(gè)雙親域域（直接接前趨））指針，，將二叉叉鏈表變變成三叉叉鏈表。。lchilddatarchild對(duì)于圖6.7所所示二叉叉樹(shù)，用用二叉鏈鏈表形式式描述。。圖6.8二叉叉樹(shù)的二二叉鏈表表表示⑵二叉叉鏈表的的數(shù)據(jù)類類型bitree..h//二叉叉鏈表定定義#include<<iostream>>usingnamespacestd;typedefcharTElemType;structBiTNode{TElemTypedata;BiTNode*lchild,,*rchild;};typedefBiTNode**BiTree;voidinitBiTree((BiTree&T);voidcreateBiTree(BiTree&&T));//遞歸歸前序遍遍歷voidpreOrderTraverse((BiTreeT,,void((*visit)(TElemType)));//非遞遞歸前序序遍歷voidpreOrderTraverse1(BiTreeT,void((*visit)((TElemType));;//遞歸歸中序遍遍歷voidinOrderTraverse(BiTreeT,void(**visit))(TElemType)));//遞歸歸后序遍遍歷voidpostOrderTraverse(BiTreeT,void((*visit)((TElemType));;⑶二叉叉鏈表的的建立為了后面面遍歷二二叉樹(shù)方方便，先先介紹建建立二叉叉鏈表的的算法（（假設(shè)ElemType為為char型））。//按先先序次序序輸入二二叉樹(shù)中中結(jié)點(diǎn)的的值（''#'表表示空格格），//構(gòu)造造二叉鏈鏈表表示示的二叉叉樹(shù)T。。voidcreateBiTree(BiTree&&T)){TElemTypech;;cin>>>ch;if(ch==='#'')///空空T=NULL;;else{T=newBiTNode;if(!!T)exit(1));T->data=ch;///生生成根結(jié)結(jié)點(diǎn)createBiTree((T->>lchild);///構(gòu)構(gòu)造左左子樹(shù)createBiTree((T->>rchild);///構(gòu)構(gòu)造右右子樹(shù) }}6.3遍遍歷二二叉樹(shù)遍歷是樹(shù)樹(shù)結(jié)構(gòu)插插入、刪刪除、修修改、查查找和排排序運(yùn)算算的前提提，是二二叉樹(shù)一一切運(yùn)算算的基礎(chǔ)礎(chǔ)和核心心。所謂遍歷二叉叉樹(shù)，就是遵遵從某種種次序，，訪問(wèn)二二叉樹(shù)中中的所有有結(jié)點(diǎn)，，使得每每個(gè)結(jié)點(diǎn)點(diǎn)僅被訪訪問(wèn)一次次。這里提到到的"訪訪問(wèn)"是是指對(duì)結(jié)結(jié)點(diǎn)施行行某種操操作，操操作可以以是輸出出結(jié)點(diǎn)信信息，修修改結(jié)點(diǎn)點(diǎn)的數(shù)據(jù)據(jù)值等，，但要求求這種訪訪問(wèn)不破破壞它原原來(lái)的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)。在本本書(shū)中，，我們規(guī)規(guī)定訪問(wèn)問(wèn)是輸出出結(jié)點(diǎn)信信息data，，且以二二叉鏈表表作為二二叉樹(shù)的的存貯結(jié)結(jié)構(gòu)。由于二叉叉樹(shù)是一一種非線線性結(jié)構(gòu)構(gòu)，每個(gè)個(gè)結(jié)點(diǎn)可可能有一一個(gè)以上上的直接接后繼，，因此，，必須規(guī)規(guī)定遍歷的規(guī)規(guī)則，并按此此規(guī)則遍遍歷二叉叉樹(shù)，最最后得到到二叉樹(shù)樹(shù)所有結(jié)結(jié)點(diǎn)的一一個(gè)線性性序列。。令L、R、D分分別代表表二叉樹(shù)樹(shù)的左子子樹(shù)、右右子樹(shù)、、根結(jié)點(diǎn)點(diǎn)，則遍遍歷二叉叉樹(shù)有6種規(guī)則則：DLR、DRL、、LDR、LRD、RDL、、RKD。若規(guī)定二叉叉樹(shù)中必必須先左左后右(左右順順序不能能顛倒))，則只只有DLR、LDR、、LRD三種遍遍歷規(guī)則則。DLR稱為前根根遍歷((或前序序遍歷、、先序遍遍歷、先先根遍歷歷)，LDR稱為中根根遍歷((或中序序遍歷))，LRD稱為后根根遍歷((或后序序遍歷))。6.3..1前前序遍歷歷所謂前序序遍歷，，就是根根結(jié)點(diǎn)最最先遍歷歷，其次次左子樹(shù)樹(shù)，最后后右子樹(shù)樹(shù)。1.遞遞歸遍歷歷前序遍歷歷二叉樹(shù)樹(shù)的遞歸歸遍歷算算法描述述為：若二叉樹(shù)樹(shù)為空，，則算法法結(jié)束；；否則①輸出根根結(jié)點(diǎn)；；②前根遍遍歷左子子樹(shù);③前根遍遍歷右子子樹(shù)。//先先序遞歸歸遍歷T，對(duì)每每個(gè)結(jié)點(diǎn)點(diǎn)調(diào)用函函數(shù)Visit一次且且僅一次次voidpreOrderTraverse((BiTreeT,,void((*visit)(TElemType))){if(T){///T不空空visit(T->data);///先先訪問(wèn)問(wèn)根結(jié)點(diǎn)點(diǎn)preOrderTraverse(T-->lchild,visit);;///再先先序遍歷歷左子樹(shù)樹(shù)preOrderTraverse(T-->rchild,visit);;///最后后先序遍遍歷右子子樹(shù) }}2.非非遞歸遍遍歷利用一個(gè)個(gè)一維數(shù)數(shù)組作棧棧，來(lái)存存貯二叉叉鏈表中中結(jié)點(diǎn)，，算法思思想為：：從二叉樹(shù)樹(shù)根結(jié)點(diǎn)點(diǎn)開(kāi)始，，沿左子子樹(shù)一直直走到末末端(左左孩子為為空)為為止，在在走的過(guò)過(guò)程中，，訪問(wèn)所所遇結(jié)點(diǎn)點(diǎn)，并依依次把所所遇結(jié)點(diǎn)點(diǎn)進(jìn)棧，，當(dāng)左子子樹(shù)為空空時(shí)，從從棧頂退退出某結(jié)結(jié)點(diǎn)，并并將指針針指向該該結(jié)點(diǎn)的的右孩子子。如此此重復(fù)，，直到棧棧為空或或指針為為空止。。//前序序遍歷二二叉樹(shù)T的非遞遞歸算法法(利用用棧)，，對(duì)每個(gè)個(gè)數(shù)據(jù)元元素調(diào)用用函數(shù)VisitvoidpreOrderTraverse1(BiTreeT,void((*visit)((TElemType)){{BiTrees[100]];inttop=0;;///top為棧棧頂指針針while(((T!==NULL)|||(top>>0))){while(T!=NULL){visit(T->data);s[top+++]=T;T=T-->lchild; }T=s[[--top]];T=T-->rchild; }}6.3..2中中序遍歷歷所謂中序序遍歷，，就是根根在中間間，先左左子樹(shù)，，然后根根結(jié)點(diǎn)，，最后右右子樹(shù)。。中序遍歷歷二叉樹(shù)樹(shù)的遞歸歸遍歷算算法描述述為：若二叉樹(shù)樹(shù)為空，，則算法法結(jié)束；；否則①中根遍遍歷左子子樹(shù);②輸出根根結(jié)點(diǎn);;③中根遍遍歷右子子樹(shù)。//中序序遞歸遍遍歷T,,對(duì)每個(gè)個(gè)結(jié)點(diǎn)調(diào)調(diào)用函數(shù)數(shù)Visit一一次且僅僅一次voidinOrderTraverse(BiTreeT,void(**visit))(TElemType))){if(T){inOrderTraverse((T->>lchild,visit);///先先中序序遍歷左左子樹(shù)visit(T->data);///再再訪問(wèn)問(wèn)根結(jié)點(diǎn)點(diǎn)inOrderTraverse((T->>rchild,visit);///最最后中中序遍歷歷右子樹(shù)樹(shù) }}6.3..3后后序遍歷歷所謂后序序遍歷，，就是根根在最后后，即先先左子樹(shù)樹(shù)，然后后右子樹(shù)樹(shù)，最后后根結(jié)點(diǎn)點(diǎn)。后序遍歷歷二叉樹(shù)樹(shù)的遞歸歸遍歷算算法描述述為：若二叉樹(shù)樹(shù)為空，，則算法法結(jié)束；；否則①后根遍遍歷左子子樹(shù):②后根遍遍歷歷子子樹(shù);③訪問(wèn)根根結(jié)點(diǎn)。。//后序序遞歸遍遍歷T，，對(duì)每個(gè)個(gè)結(jié)點(diǎn)調(diào)調(diào)用函數(shù)數(shù)Visit一一次且僅僅一次voidpostOrderTraverse(BiTreeT,void((*visit)((TElemType)){{if(T){inOrderTraverse((T->>lchild,visit);///后后序遍遍歷左子子樹(shù)inOrderTraverse((T->>rchild,visit);///再再后序序遍歷右右子樹(shù)visit(T->data);///最最后訪訪問(wèn)根結(jié)結(jié)點(diǎn) }}6.3..4按按層次遍遍歷對(duì)于一棵棵二叉樹(shù)樹(shù)，若規(guī)規(guī)定遍歷歷順序?yàn)闉閺纳系降较?上上層遍歷歷完才進(jìn)進(jìn)入下層層)，從從左到右右(同一一層從左左到右進(jìn)進(jìn)行，這這樣的遍遍歷稱為為按層次次遍歷。。下面用一一個(gè)一維維數(shù)組來(lái)來(lái)模擬隊(duì)隊(duì)列，實(shí)實(shí)現(xiàn)二叉叉樹(shù)的層層次遍歷歷。//層序序遍歷T(利用用隊(duì)列)),對(duì)每每個(gè)結(jié)點(diǎn)點(diǎn)調(diào)用函函數(shù)Visit一次且且僅一次次voidlevelOrderTraverse(BiTreeT,void(**visit))(TElemType))){BiTreeq[100]],p;;intf,r;///f,r類似于于頭尾指指針q[0]]=T;;f=0;;r=1;;while(f<r)){p=q[[f+++];///出隊(duì)隊(duì)visit(p->data);if(p->lchild!!=NULL))q[r+++]==p->>lchild;///入入隊(duì)if(p->rchild!!=NULL))q[r+++]==p->>rchild;///入入隊(duì) }}6.4線線索二二叉樹(shù)6.4..1線線索的概概念通過(guò)前面面介紹的的二叉樹(shù)樹(shù)可知，，遍歷二二叉樹(shù)實(shí)實(shí)際上就就是將樹(shù)樹(shù)中所有有結(jié)點(diǎn)排排成一個(gè)個(gè)線性序列列（即非線線性結(jié)構(gòu)構(gòu)線性化化），在在這樣的的線性序序列中，，很容易易求得某某個(gè)結(jié)點(diǎn)點(diǎn)在某種種遍歷下下的直接接前驅(qū)和和后繼。。然而，，有時(shí)我我們希望望不進(jìn)行行遍歷就就能快速速找到某某個(gè)結(jié)點(diǎn)點(diǎn)在某種種遍歷下下的直接接前驅(qū)和和后繼，，這樣，，就應(yīng)該該把每個(gè)個(gè)結(jié)點(diǎn)的的直接前前驅(qū)和直直接后繼繼記錄下下來(lái)。為了做到到這一點(diǎn)點(diǎn)，可以以在原來(lái)來(lái)的二叉叉鏈表結(jié)結(jié)點(diǎn)中，，再增加加兩個(gè)指指針域，，一個(gè)指指向前驅(qū)驅(qū)，一個(gè)個(gè)指向后后繼，但但這樣做做將會(huì)浪浪費(fèi)大量量存貯單單元，存存貯空間間的利用用率相當(dāng)當(dāng)?shù)?一一個(gè)結(jié)點(diǎn)點(diǎn)中有4個(gè)指針針，1個(gè)個(gè)指左孩孩子，1個(gè)指右右孩子，，1個(gè)指指前驅(qū)，，1個(gè)指指后繼))，而原原來(lái)的左左、右孩孩子域有有許多空空指針又又沒(méi)有利利用起來(lái)來(lái)（在有有n個(gè)結(jié)結(jié)點(diǎn)的二二叉鏈表表中必定定存在n+1個(gè)個(gè)空鏈域域）。為了不浪浪費(fèi)存存存貯空間間，我們們利用原原有的孩孩子指針針為空時(shí)時(shí)來(lái)存放放直接前前驅(qū)和后后繼，這這樣的指指針?lè)Q為為"線索"，加線線索的過(guò)過(guò)程稱為為線索化化，加了了線索的的二叉樹(shù)樹(shù)，稱為為線索二叉叉樹(shù)，對(duì)應(yīng)的的二叉鏈鏈表稱為為線索二叉叉鏈表。在線索二二叉樹(shù)中中，由于于有了線線索，無(wú)無(wú)需遍歷歷二叉樹(shù)樹(shù)就可以以得到任任一結(jié)點(diǎn)點(diǎn)在某種種遍歷下下的直接接前驅(qū)和和后繼。。但是，，我們?cè)踉鯓觼?lái)區(qū)區(qū)分孩子子指針域域中存放放的是左左、右孩孩子信息息還是直直接前驅(qū)驅(qū)或直接接后繼信信息呢??為此，，在二叉叉鏈表結(jié)結(jié)點(diǎn)中，，還必須須增加兩兩個(gè)標(biāo)志志域ltag、、rtag。ltag和rtag定定義如下下：這樣，二二叉鏈表表中每個(gè)個(gè)結(jié)點(diǎn)還還是有5個(gè)域，，但其中中只有2個(gè)指針針，較原原來(lái)的4個(gè)指針針要方便便。增加加線索后后的二叉叉鏈表結(jié)結(jié)點(diǎn)結(jié)構(gòu)構(gòu)可描述述如下：：lchildltagdatartagrchild前序序列列為：ABCD。圖前序序線索中序序列列為：BADC。圖中序序線索后序序列列為：BDCA。圖后序序線索6.4..3線線索的算算法實(shí)現(xiàn)現(xiàn)在此，僅僅介紹中中序線索索二叉樹(shù)樹(shù)的算法法實(shí)現(xiàn)。。為方便起起見(jiàn)，依依照線性性表的存存儲(chǔ)結(jié)構(gòu)構(gòu)，在二二叉樹(shù)的的線索鏈鏈表上也也添加一一個(gè)頭結(jié)結(jié)點(diǎn)，并并令其lchild域域的指針針指向二二叉樹(shù)的的根結(jié)點(diǎn)點(diǎn)，其rchild域域的指針針指向中中序遍歷歷時(shí)訪問(wèn)問(wèn)的最后后一個(gè)結(jié)結(jié)點(diǎn)，并并令二叉叉樹(shù)中序序序列中中的第一一個(gè)結(jié)點(diǎn)點(diǎn)的lchild域指指針和最最后一個(gè)個(gè)結(jié)點(diǎn)的的rchild域的指指針均指指向頭結(jié)結(jié)點(diǎn)。圖中序序線索鏈鏈表（中中序序列列為：BADC）由于線索索化的實(shí)實(shí)質(zhì)是將將二叉鏈鏈表中的的空指針針改為指指向前驅(qū)驅(qū)或后繼繼的線索索，而前前驅(qū)或后后繼的信信息只有有在遍歷歷時(shí)才能能得到，，因此線線索化的的過(guò)程即即為在遍遍歷的過(guò)過(guò)程中修修改空指指針的過(guò)過(guò)程。為了記下下遍歷過(guò)過(guò)程中訪訪問(wèn)結(jié)點(diǎn)點(diǎn)的先后后關(guān)系，，需附設(shè)設(shè)一個(gè)指指針pre始終指向向剛剛訪訪問(wèn)過(guò)的的結(jié)點(diǎn)。。1.線線索鏈表表類型定定義inthreading.h#include<<iostream>>usingnamespacestd;typedefcharTElemType;enumPointerTag{{Link,Thread}};///Link===0::指針，，Thread==1:線索索structBiThrNode{TElemTypedata;BiThrNode**lchild,**rchild;PointerTagltag,,rtag;};typedefBiThrNode**BiThrTree;voidcreateBiThrTree(BiThrTree&&T));voidpreOrderTraverse((BiThrTreeT,,void((*visit)(TElemType)));BiThrNode**inOrderThreading((BiThrTreeT));voidinTraverseThr((BiThrTreeT,,void((*visit)(TElemType)));2.實(shí)實(shí)現(xiàn)inthreading.cpp#include""inthreading..h"http://按先先序次序序輸入二二叉樹(shù)中中結(jié)點(diǎn)的的值（''#'表表示空格格），構(gòu)構(gòu)造二叉叉線索樹(shù)樹(shù)TvoidcreateBiThrTree(BiThrTree&&T)){TElemTypech;;cin>>>ch;if(ch==='#'')///空空T=NULL;;else{T=newBiThrNode;;if(!!T)exit(1));T->data=ch;///生生成根結(jié)結(jié)點(diǎn)

createBiThrTree((T->>lchild);///構(gòu)構(gòu)造左左子樹(shù)if(T->lchild))///有左左孩子T->ltag=Link;;createBiThrTree((T->>rchild);///構(gòu)構(gòu)造右右子樹(shù)if(T->rchild))///有右右孩子T->rtag=Link;; }}//先先序遞歸歸遍歷T,對(duì)每每個(gè)結(jié)點(diǎn)點(diǎn)調(diào)用函函數(shù)Visit一次且且僅一次次voidpreOrderTraverse((BiThrTreeT,,void((*visit)(TElemType))){if(T){///T不空空visit(T->data);///先先訪問(wèn)問(wèn)根結(jié)點(diǎn)點(diǎn)preOrderTraverse(T-->lchild,visit);;///再先先序遍歷歷左子樹(shù)樹(shù)preOrderTraverse(T-->rchild,visit);;///最后后先序遍遍歷右子子樹(shù) }}BiThrTreepre;///全全局變量量,始終終指向剛剛剛訪問(wèn)問(wèn)過(guò)的結(jié)結(jié)點(diǎn)voidinThreading(BiThrTreep){///中中序遍遍歷進(jìn)行行中序線線索化if(p){inThreading(p->lchild));///左左子樹(shù)線線索化if(!!p->>lchild){///沒(méi)沒(méi)有左左孩子p->ltag=Thread;///前前驅(qū)線線索p->lchild==pre;///左左孩子指指針指向向前驅(qū) }if(!!pre->rchild)){///前前驅(qū)沒(méi)有有右孩子子pre-->rtag==Thread;///后后繼線索索pre-->rchild=p;//前前驅(qū)右孩孩子指針針指向后后繼(當(dāng)當(dāng)前結(jié)點(diǎn)點(diǎn)p) }pre==p;///保保持pre始始終指向向剛剛訪訪問(wèn)過(guò)的的結(jié)點(diǎn)inThreading(p->rchild));///右右子樹(shù)線線索化 }}//中序序遍歷二二叉樹(shù)T,并將將其中序序線索化化,BiThrNode**inOrderThreading((BiThrTreeT)){BiThrNode**Thrt==newBiThrNode;////Thrt指向向頭結(jié)點(diǎn)點(diǎn)Thrt->ltag=Link;;Thrt->rtag=Thread;Thrt->rchild==Thrt;////右指針針回指if(!!T)///若二二叉樹(shù)空空，則左左指針回回指Thrt->lchild==Thrt;else{Thrt->lchild==T;pre==Thrt;inThreading(T);////中序遍遍歷進(jìn)行行中序線線索化pre-->rtag==Thread;///最后后一個(gè)結(jié)結(jié)點(diǎn)線索索化pre-->rchild=Thrt;Thrt->rchild==pre; }returnThrt;}//中序序遍歷二二叉線索索樹(shù)T((頭結(jié)點(diǎn)點(diǎn))的非非遞歸算算法voidinTraverseThr((BiThrTreeT,,void((*visit)(TElemType))){BiThrTreep;p=T-->lchild;////p指向向根結(jié)點(diǎn)點(diǎn)while(p!=T){////空樹(shù)或或遍歷結(jié)結(jié)束時(shí),,p===Twhile(p->ltag==Link)p=p-->lchild;visit(p->data);////訪問(wèn)左左子樹(shù)為為空的結(jié)結(jié)點(diǎn)while(p->rtag==Thread&&&p-->rchild!==T){{p=p-->rchild;visit(p->data);///訪訪問(wèn)后繼繼結(jié)點(diǎn) }p=p-->rchild; }}6.5樹(shù)樹(shù)和森森林6.5..1樹(shù)樹(shù)的存儲(chǔ)儲(chǔ)結(jié)構(gòu)1.雙雙親表表示法它是以一一組連續(xù)續(xù)的存儲(chǔ)儲(chǔ)單元來(lái)來(lái)存放樹(shù)樹(shù)中的結(jié)結(jié)點(diǎn)，每每個(gè)結(jié)點(diǎn)點(diǎn)有兩個(gè)個(gè)域：一一個(gè)是data域，存存放結(jié)點(diǎn)點(diǎn)信息，，另一個(gè)個(gè)是parent域，，用來(lái)存存放雙親親的位置置(指針針)。樹(shù)的雙親親表示法法2.孩孩子表示示法將一個(gè)結(jié)結(jié)點(diǎn)所有有孩子鏈鏈接成一一個(gè)單鏈鏈表形，，而樹(shù)中中有若干干個(gè)結(jié)點(diǎn)點(diǎn)，故有有若干個(gè)個(gè)單鏈表表，每個(gè)個(gè)單鏈表表有一個(gè)個(gè)表頭結(jié)結(jié)點(diǎn)，所所有表頭頭結(jié)點(diǎn)用用一個(gè)數(shù)數(shù)組來(lái)描描述。樹(shù)的孩子子表示法法3.雙雙親孩子子表示法法將第1、、2兩種種方法結(jié)結(jié)合起來(lái)來(lái)，則得得到雙親親孩子表表示法。。雙親孩子子表示法法4.孩孩子兄弟弟表示法法類似于二二叉鏈表表，但第第一根鏈鏈指向第第一個(gè)孩孩子，第第二根鏈鏈指向下下一個(gè)兄兄弟。孩子兄弟弟表示法法6.5..2樹(shù)樹(shù)、森林林和二叉叉樹(shù)的轉(zhuǎn)轉(zhuǎn)換1.樹(shù)樹(shù)轉(zhuǎn)換成成二叉樹(shù)樹(shù)（孩子子--兄兄弟表示示法）可以分為為三步：：①加線將樹(shù)中同同一結(jié)點(diǎn)點(diǎn)的兄弟弟相連;;②抹線保留結(jié)點(diǎn)點(diǎn)的最左左孩子連連線，刪刪除其它它孩子連連線；③旋轉(zhuǎn)將同一孩孩子的連連線繞左左孩子旋旋轉(zhuǎn)45度角。。討論：二二叉樹(shù)怎怎樣還原原為樹(shù)？？要點(diǎn)：逆逆操作，，把所有有右孩子子變?yōu)樾中值?！?shù)轉(zhuǎn)換成成二叉樹(shù)樹(shù)2.森森林轉(zhuǎn)換換成二叉叉樹(shù)①將森林林中每一一棵樹(shù)分分別轉(zhuǎn)換換成二叉叉樹(shù)；②合并：：使第n棵樹(shù)接接入到第第n-1棵的右右邊并成成為它的的右子樹(shù)樹(shù)，第n-1棵二二叉樹(shù)接接入到第第n-2棵的的右邊并并成為它它的右子子樹(shù)，……，第2棵二叉叉樹(shù)接入入到第1棵的右右邊并成成為它的的右子樹(shù)樹(shù)，直到到最后剩剩下一棵棵二叉樹(shù)樹(shù)為止。。森林轉(zhuǎn)換換成二叉叉樹(shù)3.二二叉樹(shù)還還原成樹(shù)樹(shù)或森林林①右鏈斷斷開(kāi)將二叉樹(shù)樹(shù)的根結(jié)結(jié)點(diǎn)的右右鏈及右右鏈的右右鏈等全全部斷開(kāi)開(kāi)，得到到若干棵棵無(wú)右子子樹(shù)的二二叉樹(shù)。。②二叉樹(shù)樹(shù)還原成成樹(shù)將①中得得到的每每一棵二二叉樹(shù)都都還原成成樹(shù)（與與樹(shù)轉(zhuǎn)換換成二叉叉樹(shù)的步步驟剛好好相反））。二叉樹(shù)還還原成森森林的過(guò)過(guò)程6.5..3樹(shù)樹(shù)和森林林的遍歷歷在樹(shù)和森森林中，，一個(gè)結(jié)結(jié)點(diǎn)可能能有兩棵棵以上的的子樹(shù)，，所以不不宜討論論它們的的中序遍遍歷，即即樹(shù)和和森林只有先序序遍歷和和后序遍遍歷。1.先先序遍歷歷⑴樹(shù)的的先序遍遍歷若樹(shù)非空空，則先先訪問(wèn)根根結(jié)點(diǎn)，，然后依依次先序序遍歷各各子樹(shù)。。⑵森林林的先序序遍歷若森林非非空，則則先訪問(wèn)問(wèn)森林中中第一棵棵樹(shù)的根根結(jié)點(diǎn)，，再先序序遍歷第第一棵樹(shù)樹(shù)各子樹(shù)樹(shù)，接著著先序遍遍歷第二二棵樹(shù)、、第三棵棵樹(shù)、……、直到到最后一一棵樹(shù)。。2.后后序遍歷歷⑴樹(shù)的的后序遍遍歷若樹(shù)非空空，則依依次后序序遍歷各各子樹(shù)，，最后訪訪問(wèn)根結(jié)結(jié)點(diǎn)。⑵森林林的后序序遍歷按順序后后序遍歷歷森林中中的每一一棵樹(shù)。。另外，請(qǐng)請(qǐng)注意，，樹(shù)和森森林的先先序遍歷歷等價(jià)于于它轉(zhuǎn)換換成的二二叉樹(shù)的的先序遍遍歷，樹(shù)樹(shù)和森林林的后序序遍歷等等價(jià)于它它轉(zhuǎn)換成成的二叉叉樹(shù)的中中序遍歷歷。6.6哈哈夫曼曼樹(shù)6.6..1基基本術(shù)語(yǔ)語(yǔ)1.路路徑和路路徑長(zhǎng)度度在一棵樹(shù)樹(shù)中，從從一個(gè)結(jié)結(jié)點(diǎn)往下下可以達(dá)達(dá)到的孩孩子或子子孫結(jié)點(diǎn)點(diǎn)之間的的通路，，稱為路徑。通路中中分支的的數(shù)目稱稱為路徑長(zhǎng)度度。若規(guī)定根根結(jié)點(diǎn)的的層數(shù)為為1，則則從根結(jié)結(jié)點(diǎn)到第第L層結(jié)結(jié)點(diǎn)的路路徑長(zhǎng)度度為L(zhǎng)-