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

Chp6樹和二叉樹本章重點(diǎn)內(nèi)容6.1樹的定義和基本概念6.2二叉樹

6.2.1樹的定義和基本術(shù)語

6.2.2二叉樹的性質(zhì)

6.2.3二叉樹的存儲結(jié)構(gòu)6.3遍歷二叉樹

6.3.1遍歷二叉樹

6.3.2線索二叉樹

6.4樹和森林

6.4.1樹的存儲結(jié)構(gòu)

6.4.2森林與二叉樹的轉(zhuǎn)換6.4.3樹和森林的遍歷6.6赫夫曼樹及其應(yīng)用

6.6.1最優(yōu)二叉樹（赫夫曼樹）

6.6.2赫夫曼編碼

樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界是大量存在的，例如家譜、行政組織機(jī)構(gòu)都可用樹形象地表示。樹在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時(shí)，可用樹來描述其執(zhí)行過程等等引言6.1樹的定義與基本概念1.樹的定義定義：樹(tree)是n(n>0)個(gè)結(jié)點(diǎn)的有限集T，其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根(root)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree)特點(diǎn)：樹中至少有一個(gè)結(jié)點(diǎn)——根樹中各子樹是互不相交的集合A只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹根子樹從邏輯結(jié)構(gòu)看：

1）樹中只有根結(jié)點(diǎn)沒有前趨；

2）除根外，其余結(jié)點(diǎn)都有且僅一個(gè)前趨；3）樹的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后繼；

4）除根外的其他結(jié)點(diǎn)，都存在唯一條從根到該結(jié)點(diǎn)的路徑；5）樹是一種分枝結(jié)構(gòu)，（除了一個(gè)稱為根的結(jié)點(diǎn)外）每個(gè)元素都有且僅有一個(gè)直接前趨，有零個(gè)或多個(gè)直接后繼。JIACBDHGFE2．樹的應(yīng)用

1）樹可表示具有分枝結(jié)構(gòu)關(guān)系的對象例1家族族譜設(shè)某家庭有13個(gè)成員A、B、C、D、E、F、G、H、I、J、K、L、M他們之間的關(guān)系可用下圖所示的樹表示：JIACBDHGFEKLM2）樹是常用的數(shù)據(jù)組織形式

有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。

例2計(jì)算機(jī)的文件系統(tǒng)

不論是Linux文件系統(tǒng)還是Windows文件系統(tǒng)，所有的文件是用樹的形式來組織的。文件夾1文件夾n文件1文件2文件夾11文件夾12文件11文件12/3．樹的邏輯結(jié)構(gòu)描述

二元組描述為：Tree=(D,R)

D={Ki∣1≤i≤n;n≥0,KiTElemtype}

R={r}

其中：D是n個(gè)具有相同特性的數(shù)據(jù)元素的集合;n為樹中結(jié)點(diǎn)個(gè)數(shù)，若n=0，則為一棵空樹，n>0時(shí)稱為一棵非空樹。關(guān)系r應(yīng)滿足下列條件：（1）有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，稱該結(jié)點(diǎn)為樹根;（2）除根結(jié)點(diǎn)以外,其余每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū);（3）樹中每個(gè)結(jié)點(diǎn)可以有零個(gè)或多個(gè)直接后繼(孩子結(jié)點(diǎn))。

基本術(shù)語結(jié)點(diǎn)(node)——表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹數(shù)葉子(leaf)——度為0的結(jié)點(diǎn)孩子(child)——結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的~兄弟(sibling)——同一雙親的孩子堂兄結(jié)點(diǎn)——同一層上結(jié)點(diǎn)樹的度——一棵樹中最大的結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……深度(depth)——樹中結(jié)點(diǎn)的最大層次數(shù)森林(forest)——m(m0)棵互不相交的樹的集合ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先樹的表示方法1.樹型表示bacghdefij2.凹入表表示abdeijfcgh3.嵌套集合表示4.廣義表表示ijdfghabcea(b(d,e(i,j),c(g,h)))6.2二叉樹定義定義：二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結(jié)點(diǎn)的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空性質(zhì)1:

在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。

證明：

用數(shù)學(xué)歸納法。

1)當(dāng)i=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。

2)設(shè)i=k時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。現(xiàn)證明當(dāng)i=k+1時(shí)，結(jié)論成立：因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn)總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即2×2k-1=2(k+1)-1，故結(jié)論成立。推論：度為m的樹中第i層上至多有mi-1個(gè)結(jié)點(diǎn),(i≥1)。二叉樹性質(zhì)性質(zhì)2:

深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≥1）。

證明：因?yàn)樯疃葹閗的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為推論：深度為k的m叉樹至多有個(gè)結(jié)點(diǎn)。

性質(zhì)3:

對任意一棵二叉樹，若終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹中度為1的結(jié)點(diǎn)總數(shù)，設(shè)二叉樹中分支數(shù)目為B。①n=n0+n1+n2

除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對應(yīng)一個(gè)進(jìn)入它的分支：②n=B+1

二叉樹中的分支都是由度為1和度為2的結(jié)點(diǎn)發(fā)出③B=n1+2n2于是：由①②③可得：n0+n1+n2=n1+2n2+1n0=n2+1。幾種特殊形式的二叉樹滿二叉樹定義：一顆深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)滿二叉樹的順序表示，即從二叉樹的根開始，層間從上到下，層內(nèi)從左到右，逐層進(jìn)行編號（1，2，…，n）。完全二叉樹定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱為~特點(diǎn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對任一結(jié)點(diǎn)，若其右子樹的最大層次為L，則其左子樹的最大層次必為L或L+1（最下層的葉子結(jié)點(diǎn)集中在樹的左部）(b)完全二叉樹(c)非完全二叉樹(d)非完全二叉樹圖6.9特殊形態(tài)的二叉樹(a)滿二叉樹性質(zhì)4

具有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2(n)＋1

證明： 設(shè)完全二叉樹的深度為h，則根據(jù)性質(zhì)2和完全二叉樹的定義有

2h－1-1<n2h-1或2h－1

n<2h取對數(shù)h－1<log2nh，又h是整數(shù)，因此有h=log2(n)

＋1621754389101112性質(zhì)5：如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號，則對任一結(jié)點(diǎn)i(1in)，有：

(1)如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；

如果i>1，則其雙親是i/2(2)如果2i>n，則結(jié)點(diǎn)i無左孩子；

如果2in，則其左孩子是2i(3)如果2i+1>n，則結(jié)點(diǎn)i無右孩子；

如果2i+1n，則其右孩子是2i+1621754389101112二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)滿二叉樹或完全二叉樹的順序存儲結(jié)構(gòu)

對于完全二叉樹來說，除最下面一層外，各層都被結(jié)點(diǎn)充滿。若對二叉樹按層排序，則從一個(gè)結(jié)點(diǎn)的編號就可推知其雙親、左右孩子等結(jié)點(diǎn)的編號。用一維數(shù)組bt[]存放一棵完全二叉樹，將標(biāo)號為i的結(jié)點(diǎn)的數(shù)據(jù)元素存放在分量bt[i]中，bt[0]不存放元素。

例:bt[5]（i=5)的雙親結(jié)點(diǎn)標(biāo)號是k=└i/2┘=2，雙親結(jié)點(diǎn)所對應(yīng)的數(shù)組分量bt[k]=bt[2]。bt[2]（i=2)的右孩子結(jié)點(diǎn)標(biāo)號是k=2i+1=5，所對應(yīng)的數(shù)組分量bt[k]=bt[5]。ABCEFG123456k0123456…nbt[k]ABCEFG…順序結(jié)構(gòu)圖示:二叉樹的存儲結(jié)構(gòu)非完全二叉樹的順序存儲結(jié)構(gòu)實(shí)現(xiàn)：按完全二叉樹的形式補(bǔ)齊二叉樹所缺少的那些結(jié)點(diǎn)，對二叉樹結(jié)點(diǎn)再按層編號，將二叉樹原有的結(jié)點(diǎn)按編號存儲到內(nèi)存單元“相應(yīng)”的位置上。特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲位置中浪費(fèi)空間，適于存滿二叉樹和完全二叉樹abcdefgabcde0000fg12345678910116789123451011補(bǔ)齊二叉樹所缺少的那些結(jié)點(diǎn)ABCDEFGHIJKL123456789101112完全二叉樹abcdefghijkl結(jié)點(diǎn)編號123456789101112131415結(jié)點(diǎn)值123450000670000第i號結(jié)點(diǎn)的左右孩子一定保存在第2i及2i+1號單元中。缺點(diǎn)：對非完全二叉樹而言，浪費(fèi)存儲空間#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表typedefstructnode{datatypedata;structnode*lchild,*rchild;}JD;lchilddatarchildABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域ABCDEFG^^^^^^^^空指針個(gè)數(shù)：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成三叉鏈表typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}JD;lchilddataparentrchildABCDEFGABCDEFG^^^^^^^^^指向雙親遍歷：按某種搜索路徑訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次。訪問：含義很廣，可以是對結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。對于線性結(jié)構(gòu)由于每個(gè)結(jié)點(diǎn)只有一個(gè)直接后繼，遍歷是很容易的事

二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可能有兩個(gè)后繼，如何訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次？

6.3遍歷二叉樹二叉樹的遍歷方法二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：L：遍歷左子樹

D：訪問根結(jié)點(diǎn)

R：遍歷右子樹有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD

約定先左后右,有三種遍歷方法：DLR、LDR、LRD

，分別稱為先序遍歷、中序遍歷、后序遍歷

A

F

G

E

D

C

B二叉樹的遍歷方法先序遍歷：先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn)按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn)DLRLDR、LRD、DLRRDL、RLD、DRLADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:

先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷：

先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:

先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn)B先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef--/+*abcdef例：將如下表達(dá)式

a+b*(c-d)-e/f存入一個(gè)樹結(jié)構(gòu)。葉子節(jié)點(diǎn)為操作數(shù)中間節(jié)點(diǎn)為運(yùn)算符前綴表達(dá)式中綴表達(dá)式后綴表達(dá)式若二叉樹非空（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹（3）先序遍歷右子樹；先序遍歷（DLR）的定義：上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束——基本項(xiàng)（也叫終止項(xiàng)）若二叉樹非空——遞歸項(xiàng)（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹（3）先序遍歷右子樹；AFGEDCB

遍歷的算法先序遍歷的遞歸算法voidpreorder(JD*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC先序遍歷的非遞歸算法遞歸算法邏輯清晰、易懂，但在實(shí)現(xiàn)時(shí)，由于函數(shù)調(diào)用棧層層疊加，效率不高，故有時(shí)考慮非遞歸算法。

遍歷時(shí)從根結(jié)點(diǎn)開始沿左子樹深入下去，當(dāng)深入到最左端，無法再深入下去時(shí)，則返回，再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹，再進(jìn)行如此的深入和返回，直到最后從根結(jié)點(diǎn)的右子樹返回到根結(jié)點(diǎn)為止。先序遍歷是在深入時(shí)遇到結(jié)點(diǎn)就訪問。

在下面算法中，二叉樹以二叉鏈表存放，用一維數(shù)組stack[Maxsize]實(shí)現(xiàn)棧，變量top用來表示當(dāng)前棧頂?shù)奈恢谩?/p>

（1）令當(dāng)前指針p指向根結(jié)點(diǎn)；（2）當(dāng)p非空,訪問當(dāng)前結(jié)點(diǎn)p，將p壓入棧中，令當(dāng)前指針指向其左孩子，重復(fù)（2），直到p為NULL；（3）當(dāng)p為空時(shí)，從棧中彈出棧頂元素賦給變量p，令當(dāng)前指針指向其右孩子；（4）若棧非空或當(dāng)前指針非NULL，執(zhí)行（2）；當(dāng)p為空且棧也為空時(shí)，遍歷結(jié)束。先序遍歷（DLR）的非遞歸算法思想

先序遍歷的非遞歸算法dbea*-/c+voidNRPreOrder(BTreebt){ BTreestack[Maxsize],p; inttop; if(bt!=NULL){ top=-1;p=bt; while(p!=NULL||top>-1) { while(p!=NULL) { printf("%d",p->data); top++; stack[top]=p; p=p->lchild; } if(top>-1) { p=stack[top];top--;p=p->rchild; } }}}/*指針指向p的左孩子*//*訪問結(jié)點(diǎn)的數(shù)據(jù)域*//*將當(dāng)前指針p壓棧*//*從棧中彈出棧頂元素，指針指向p的右孩子結(jié)點(diǎn)*//*初始化*/中序遍歷的遞歸算法

voidInOrderTraverse(BiTreeT) {if(T!=NULL){InOrderTraverse(T->lchild); printf("%c",T->data);/*訪問根結(jié)點(diǎn)*/ InOrderTraverse(T->rchild); }}中序遍歷的非遞歸算法遍歷時(shí)從根結(jié)點(diǎn)開始沿左子樹深入下去，當(dāng)深入到最左端，無法再深入下去時(shí)，則返回，再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹，再進(jìn)行如此的深入和返回，直到最后從根結(jié)點(diǎn)的右子樹返回到根結(jié)點(diǎn)為止。先序遍歷是在深入時(shí)遇到結(jié)點(diǎn)就訪問，中序遍歷是在從左子樹返回時(shí)遇到結(jié)點(diǎn)訪問。中序遍歷的非遞歸算法思想從二叉樹的根結(jié)點(diǎn)開始，令變量p為根結(jié)點(diǎn)，若p不為空，則令p沿左子樹根結(jié)點(diǎn)前進(jìn)，在前進(jìn)過程中，把所經(jīng)歷的結(jié)點(diǎn)逐個(gè)壓入棧中，當(dāng)p為空時(shí)，彈出棧頂元素給p，并訪問該結(jié)點(diǎn)，再令p為它當(dāng)前結(jié)點(diǎn)的右子樹根結(jié)點(diǎn)。重復(fù)上述過程，當(dāng)p為空且棧也為空時(shí)，遍歷結(jié)束。在算法具體實(shí)現(xiàn)時(shí)，只需將先序遍歷的非遞歸算法中的Visit(p->data)移到p=stack[top];top--;和p=p->rchild之間即可。后序遍歷遞歸算法

∧a∧

+

*//\d/\-bt∧e∧∧b∧∧c∧a*(b-c)+d/evoidPostorder(BTreebt){

if(bt!=NULL)

{

Postorder(bt->lchild);

Postorder(bt->rchild);

printf(“%c,”,bt->data);

}}后序序列為abc–*de/+稱為后綴表達(dá)式后序遍歷的非遞歸算法遍歷從根結(jié)點(diǎn)開始沿左子樹深入下去，當(dāng)深入到最左端，無法再深入下去時(shí)，則返回，再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹，再進(jìn)行如此的深入和返回，直到最后從根結(jié)點(diǎn)的右子樹返回到根結(jié)點(diǎn)為止。先序遍歷是在深入時(shí)遇到結(jié)點(diǎn)就訪問，中序遍歷是在從左子樹返回時(shí)遇到結(jié)點(diǎn)訪問，后序遍歷是在從右子樹返回時(shí)遇到結(jié)點(diǎn)訪問。后序遍歷的非遞歸算法思想：

后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點(diǎn)的左右子樹是否均遍歷過。

可采用標(biāo)記法，結(jié)點(diǎn)入棧時(shí)，配一個(gè)標(biāo)志tag一同入棧(1：遍歷左子樹前的現(xiàn)場保護(hù)，2：遍歷右子樹前的現(xiàn)場保護(hù))。

首先將T和tag(為1)入棧，遍歷左子樹；返回后，修改棧頂tag為2，遍歷右子樹；最后訪問根結(jié)點(diǎn)。

typedef

struct

{

BTree

data;int

tag;

}stacknode;void

NRPostOrder(BTree

T){

InitStack(S);

while

(

T!=NULL

||

!StackEmpty(S)

){

while

(

T

!=

NULL

){

Push(S,T,1);T

=

T->lchild;}

while

(

!EmptyStack(S)

&&

GetTopTag(S)==2){

Pop(S,

x);Visit(x->data);}

if

(

!EmptyStack(S)

){

SetTopTag(S,

2);

//

設(shè)置棧頂標(biāo)記

T

=

GetTopPointer(S);

//

取棧頂保存的指針

T

=

T->rchild;

}else

break;}

}層序遍歷算法遍歷方法：從上而下，從左到右依次訪問樹中每個(gè)結(jié)點(diǎn)。層序遍歷二叉樹算法思想:若二叉樹不為空，則根結(jié)點(diǎn)入隊(duì)；如隊(duì)列不空，循環(huán)：做出隊(duì)操作，隊(duì)首元素作為當(dāng)前結(jié)點(diǎn)，訪問當(dāng)前結(jié)點(diǎn)；將當(dāng)前結(jié)點(diǎn)的左右孩子入隊(duì)；最后，出隊(duì)序列就是層序遍歷序列AFGEDCB遍歷結(jié)果ABCDEFG例1：為二叉樹建立二叉鏈表(遞歸算法)以遞歸方式建立二叉樹輸入：二叉樹的先序序列結(jié)果：二叉樹的二叉鏈表遍歷操作訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次。是否可在利用遍歷，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接？基本思想：輸入（在空子樹處添加*的二叉樹的）先序序列（設(shè)每個(gè)元素是一個(gè)字符）按先序遍歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接遍歷算法應(yīng)用應(yīng)用1：按先序遍歷序列建立二叉樹的二叉鏈表∧

D

A

B∧C

∧∧

E∧∧

F∧T

先序序列：ABDFCE（在空子樹處添加*的二叉樹的）先序序列：ABD*F***CE***

A

F

E

D

C

B*******

A

F

E

D

C

B①②使得原二叉樹中每個(gè)結(jié)點(diǎn)，（包括葉子結(jié)點(diǎn)）都有左右孩子StatusCreateBiTree(BiTree&T){//輸入（在空子樹處添加*的二叉樹的）先序序列（設(shè)每個(gè)元素是一個(gè)字//符）按先序遍歷的順序，建立二叉鏈表，并將該二叉鏈表根結(jié)點(diǎn)指針//賦給Tscanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’則T=NULL返回

else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;//建立（根）結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹鏈表，并將左子樹根結(jié)點(diǎn)指針

//賦給（根）結(jié)點(diǎn)的左孩子域

CreateBiTree(T->rchild);//構(gòu)造右子樹鏈表，并將右子樹根結(jié)點(diǎn)指針

//賦給（根）結(jié)點(diǎn)的右孩子域

}returnOK;}//CreateBiTree如果輸入字符不是“*”，則建立一個(gè)新結(jié)點(diǎn)，然后建立其左子樹和右子樹；如果是“*”則返回，繼續(xù)進(jìn)行下一次操作。AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^應(yīng)用2：統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)總數(shù)m，葉子結(jié)點(diǎn)個(gè)數(shù)n0分析：每當(dāng)訪問一個(gè)結(jié)點(diǎn)時(shí)，在原訪問語句printf后邊，加上一條計(jì)數(shù)器語句m++和一個(gè)判斷該結(jié)點(diǎn)是否葉子的語句，便可解決問題假設(shè)用中根遍歷方法統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)，算法如下：算法1：Voidinjishu(Bnode*t)

｛if(t!=NULL)

｛injishu(t->lch)；/*統(tǒng)計(jì)左子樹結(jié)點(diǎn)數(shù)*/printf("%6c"，t->data)；/*訪問根結(jié)點(diǎn)*/m++; /*結(jié)點(diǎn)記數(shù)*/if((t->lch==NULL)&&(t->rch==NULL))n0++；/*葉結(jié)點(diǎn)記數(shù)*/

injishu(t->rch)；/*統(tǒng)計(jì)右子樹節(jié)點(diǎn)數(shù)*/

｝｝/*injishu*/

算法2：voidCountLeaf

(BiTreeT,int*count){//求葉子節(jié)點(diǎn)的個(gè)數(shù)，T為根節(jié)點(diǎn)的指針

if(T){if((!T->lchild)&&(!T->rchild))*count++;//對葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeafintHeight(BitreeT)//Heightofatree{if(T==NULL)return0;else { intm=Height(T->lchild); intn=Height(T->rchild); return(m>n)?m+1:n+1; }}應(yīng)用3：求二叉樹高度(遞歸算法)輸入：二叉樹的二叉鏈表結(jié)果：二叉樹的高度分析如下：（1）若二叉樹為空，則其高度為0，求解結(jié)束（2）若二叉樹不為空，則其高度為左右子樹高度最大值加1

對于一個(gè)完全二叉樹來說，利用先序序列、中序序列和后序序列可以確定此樹。然而，對于一個(gè)一般的二叉樹，僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹。如果同時(shí)已知二叉樹的中序序列“cbdaegf”，則會如何？

應(yīng)用4：由二叉樹的先序和中序序列建樹

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根P154,例6-5abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列例1.已知樹的前序序列為abdcegf

中序序列為bdaegcf

則樹為？abdcfeg例2.已知樹的后序序列為dbgefca

中序序列為bdaegcf則樹為？我們可以利用前序序列和中序序列、后序序列和中序序列

來確定一棵二叉樹。注意：若只是知道前序和后序的序列就不能唯一的確定一個(gè)二叉樹。問題的提出遍歷是二叉樹最基本最常用的操作。

1）對二叉樹所有結(jié)點(diǎn)做某種處理可在遍歷過程中實(shí)現(xiàn)；

2）檢索（查找）二叉樹某個(gè)結(jié)點(diǎn)，可通過遍歷實(shí)現(xiàn)；遍歷的過程就是將非線性序列轉(zhuǎn)化為一個(gè)線性序列，使得每個(gè)結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。那么當(dāng)我們采用二叉鏈表作為存儲結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子，不能直接得到它的前驅(qū)和后繼，那么我們?nèi)绾蝸肀４嬖谀撤N遍歷過程中得到的前驅(qū)和后繼信息呢？？為了保留結(jié)點(diǎn)在某種遍歷序列中直接“前驅(qū)”和直接“后繼”的位置信息，可以利用二叉樹的二叉鏈表存儲結(jié)構(gòu)中的那些空指針域來指示二叉鏈表的2n個(gè)孩子指針域中只用到了n-1個(gè)域，還有另外n+1個(gè)指針域?yàn)榭?，被閑置現(xiàn)設(shè)法將這些空閑的指針域利用起來。當(dāng)某結(jié)點(diǎn)無左孩子時(shí)，令左指針指向它的前趨結(jié)點(diǎn)；當(dāng)該結(jié)點(diǎn)無右孩子時(shí)，令右指針指向它的后繼結(jié)點(diǎn)。為了嚴(yán)格區(qū)分結(jié)點(diǎn)的孩子指針域究竟指向孩子結(jié)點(diǎn)還是指向前趨或后繼結(jié)點(diǎn)，需在原結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域。解決辦法定義：前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個(gè)相鄰的結(jié)點(diǎn)互稱為~線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針稱為~線索二叉樹：加上線索的二叉樹叫~線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫~實(shí)現(xiàn)在有n個(gè)結(jié)點(diǎn)的二叉鏈表中必定有n+1個(gè)空鏈域在線索二叉樹的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域ltag:若ltag=0,lc域指向左孩子；若ltag=1,lc域指向其前驅(qū)rtag:若rtag=0,rc域指向右孩子；若rtag=1,rc域指向其后繼結(jié)點(diǎn)定義：typedefstructnode{intdata;intltag,rtag;structnode*lc,*rc;}JD;lcltagdatartagrc6.4線索二叉樹ABCDEABDCET先序序列：ABCDE00001111^11先序線索二叉樹ABCDEABDCET中序序列：BCAED00001111^11^ABDCET后序序列：CBEDA0000111111^ABCDE中序線索二叉樹后序線索二叉樹為簡化線索鏈表的遍歷算法，仿照線性鏈表，為線索鏈表加上一頭結(jié)點(diǎn)

約定：

①頭結(jié)點(diǎn)的lc域：存放線索鏈表的根結(jié)點(diǎn)指針；

②頭結(jié)點(diǎn)的rc域:中序序列最后一個(gè)結(jié)點(diǎn)的指針；

③中序序列第一結(jié)點(diǎn)lc域：指向頭結(jié)點(diǎn);

④中序序列最后一個(gè)結(jié)點(diǎn)的rc域:指向頭結(jié)點(diǎn);F11E01G11D11A00B00H11C0001頭結(jié)點(diǎn)②①④③如圖標(biāo)出的中序二叉樹結(jié)點(diǎn)的順序，可看出1）中序序列的第一結(jié)點(diǎn)，是二叉樹的最左下結(jié)點(diǎn)；2）若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索，則p的右孩子結(jié)點(diǎn)即為后繼結(jié)點(diǎn)；3）若p所指結(jié)點(diǎn)的右孩子域?yàn)楹⒆又羔?，則p的后繼結(jié)點(diǎn)為其右子樹的最左下結(jié)點(diǎn)；F11E01G11D11A00B00H11C0001頭結(jié)點(diǎn)①②③④⑤⑥⑦⑧中序遍歷序列：D,B,H,E,A,F,C,GABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹

0

1頭結(jié)點(diǎn)：ltag=0,lc指向根結(jié)點(diǎn)rtag=1,rc指向中序序列中最后一個(gè)結(jié)點(diǎn)中序遍歷序列中第一個(gè)結(jié)點(diǎn)的lc域和最后一個(gè)結(jié)點(diǎn)的rc域都指向頭結(jié)點(diǎn)ABDCET中序序列：BCAED中序線索二叉樹00001111^11^3．線索二叉樹的遍歷

在二叉樹上加上結(jié)點(diǎn)前趨、后繼線索后，可利用線索對二叉樹進(jìn)行遍歷。

下面是P134線索鏈表的遍歷算法6.5。

在中序線索二叉樹上遍歷二叉樹，其基本步驟：1）p=T->lchild;p指向線索鏈表的根結(jié)點(diǎn)；2）若線索鏈表非空，循環(huán)：（a）循環(huán)，順著p左孩子指針找到最左下結(jié)點(diǎn)；訪問之；（b）若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索，p的右孩子結(jié)點(diǎn)即為后繼結(jié)點(diǎn)循環(huán)：p=p->rchild；并訪問p所指結(jié)點(diǎn)；（在此循環(huán)中，順著后繼線索訪問二叉樹中的結(jié)點(diǎn)）（c）一旦線索“中斷”，p所指結(jié)點(diǎn)的右孩子域?yàn)橛液⒆又羔?，p=p->rchild，使p指向右孩子結(jié)點(diǎn)；3）返回OK；結(jié)束線索鏈表的遍歷算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)){//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，

//中序遍歷二叉線索樹T算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。

P=T->lchild;//p指向根結(jié)點(diǎn)

While(p!=T){//空樹或遍歷結(jié)束時(shí)，p==TWhile(p->Ltag==0)p=p->lchild;//找到最左下結(jié)點(diǎn)；訪問之

if(!Visit(p->data))returnERRORwhile(p->Rtag==1&&p->rchild!=T){//若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索且不是最后一個(gè)結(jié)點(diǎn)

p=p->rchild;Visit(p->data);//訪問后繼結(jié)點(diǎn)

}p=p->rchild;}returnOK;}//InOrderTraverse_Thr1在中序線索二叉樹中查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)對于中序線索二叉樹上的任一結(jié)點(diǎn)，尋找其中序的前驅(qū)結(jié)點(diǎn)，有以下兩種情況：如果該結(jié)點(diǎn)的左標(biāo)志為1，那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn)；如果該結(jié)點(diǎn)的左標(biāo)志為0，表明該結(jié)點(diǎn)有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子為根結(jié)點(diǎn)的子樹的最右結(jié)點(diǎn)（左子樹最后一個(gè)訪問結(jié)點(diǎn)），即沿著其左子樹的右指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時(shí)，它就是所要找的前驅(qū)結(jié)點(diǎn)。線索二叉樹的基本操作實(shí)現(xiàn)BithrtreeInprenode(Bithrtreep){ Bithrtreepre; pre=p->lchild; if(p->ltag!=1) while(pre->rtag==0) pre=pre->rchild; return(pre);}在中序線索二叉樹中查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)2在中序線索二叉樹中查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)對于中序線索二叉樹上的任一結(jié)點(diǎn)，尋找其中序的后繼結(jié)點(diǎn)，也有以下兩種情況：如果該結(jié)點(diǎn)的右標(biāo)志為1，那么其右指針域所指向的結(jié)點(diǎn)便是它的后繼結(jié)點(diǎn)；如果該結(jié)點(diǎn)的右標(biāo)志為0，表明該結(jié)點(diǎn)有右孩子，根據(jù)中序遍歷的定義，它的后繼結(jié)點(diǎn)是以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)的子樹的最左結(jié)點(diǎn)（右子樹第一個(gè)訪問結(jié)點(diǎn)），即沿著其右子樹的左指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的左標(biāo)志為1時(shí)，它就是所要找的后繼結(jié)點(diǎn)。BithrtreeInpostnode(Bithrtreep){ Bithrtreepost; post=p->rchild; if(p->rtag!=1)

while(post->ltag==0) post=post->lchild; return(post);}在中序線索二叉樹中查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)6.5樹的存儲結(jié)構(gòu)在計(jì)算機(jī)中，樹的存儲通常采用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，但無論采用何種存儲方式，都要求存儲結(jié)構(gòu)不但能存儲各結(jié)點(diǎn)本身的數(shù)據(jù)信息，還要能唯一地反映樹中各結(jié)點(diǎn)之間的邏輯關(guān)系

雙親表示法實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn)：找雙親容易，找孩子難typedefstructnode{datatypedata;intparent;}JD;JDt[M];abcdefhgiacdefghib-101124440501234678dataparent如何找孩子結(jié)點(diǎn)圖中用parent域的值為-1表示該結(jié)點(diǎn)無雙親結(jié)點(diǎn)，即該結(jié)點(diǎn)是一個(gè)根結(jié)點(diǎn)。孩子表示法多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹的根結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹的度D,浪費(fèi)內(nèi)存結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度d，實(shí)現(xiàn)不放便datachild1child2……….childDdatadegreechild1child2……….childd孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲，再用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表其主體是一個(gè)與結(jié)點(diǎn)個(gè)數(shù)一樣大小的一維數(shù)組 數(shù)組的每一個(gè)元素有兩個(gè)域組成，一個(gè)域用來存放結(jié)點(diǎn)信息；另一個(gè)用來存放指針，該指針指向由該結(jié)點(diǎn)孩子組成的單鏈表的首位置。孩子結(jié)點(diǎn)單鏈表的結(jié)構(gòu)也由兩個(gè)域組成，一個(gè)存放孩子結(jié)點(diǎn)在一維數(shù)組中的下標(biāo)；另一個(gè)是指針域，指向下一個(gè)孩子。abcdefhgi501234678acdefghibdatafirstchild12^34^^867^5^^^^^如何找雙親結(jié)點(diǎn)孩子結(jié)點(diǎn)：typedefstructnode{intchild;//該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo)

structnode*next;//指向下一孩子結(jié)點(diǎn)}ChildNode;表頭結(jié)點(diǎn)：typedefstructtnode{datatypedata;//數(shù)據(jù)域

ChildNode*firstchild;//指向第一個(gè)孩子的指針}NodeType;

NodeType

t[M];帶雙親的孩子鏈表501234678acdefghibdatafirstchild12348675^^^^^^^^^-101124440parentabcdefhgi孩子兄弟表示法（二叉鏈表表示法）實(shí)現(xiàn)：用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)特點(diǎn)操作容易破壞了樹的層次typedefstructnode{datatypedata;structnode*fch,*nsib;}JD;abcdefhgiabcdefghi^^^^^^^^^^IACBDHGFE此二叉鏈表既是樹(a)的孩子兄弟表示又是二叉樹(b)的二叉鏈表(a)(b)由此可將樹與二叉樹對應(yīng)起來AIHDGFCEBFIABDHGCE二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可導(dǎo)出樹與二叉樹之間的轉(zhuǎn)換。樹與二叉樹轉(zhuǎn)換方法樹根結(jié)點(diǎn)X的第一個(gè)孩子結(jié)點(diǎn)X緊鄰的右兄弟二叉樹根結(jié)點(diǎn)X的左孩子結(jié)點(diǎn)X的右孩子IACBDHGFEFIABDHGCE樹與二叉樹轉(zhuǎn)換樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對應(yīng)存儲存儲解釋解釋將樹轉(zhuǎn)換成二叉樹加線：在兄弟之間加一連線抹線：對每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空將二叉樹轉(zhuǎn)換成樹加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來抹線：抹掉原二叉樹中雙親與右孩子之間的連線調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點(diǎn)用線相連以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ練習(xí)： 對下圖中的二叉樹進(jìn)行后序線索化，為每個(gè)空指針建立相應(yīng)的前驅(qū)或后繼？ADCBFEGH將下圖中的森林轉(zhuǎn)換為對應(yīng)的二叉樹。ADCBFEGJKLMNOPIH將下圖中二叉樹轉(zhuǎn)換為森林。ADCBFEGJKLMNOIH1樹的遍歷先序遍歷樹和森林的遍歷在樹和森林中，一個(gè)結(jié)點(diǎn)可能有兩棵以上的子樹，所以不討論其中序遍歷，只討論先序遍歷和后序遍歷。AFEDCB訪問根結(jié)點(diǎn)；按照從左到右的順序先序遍歷根結(jié)點(diǎn)的每一棵子樹。

ABECFD后序遍歷按照從左到右的順序后序遍歷根結(jié)點(diǎn)的每一棵子樹。訪問根結(jié)點(diǎn)；

EBFCDA樹的遍歷與轉(zhuǎn)換的相應(yīng)二叉樹的遍歷序列有什么關(guān)系？與對應(yīng)二叉樹的中序序列相同與對應(yīng)二叉樹的先序序列相同2森林的遍歷先序遍歷訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷第一棵樹的根結(jié)點(diǎn)的子樹；先序遍歷去掉第一棵樹后的子森林。

ABCDEFGHI后序遍歷后序遍歷第一棵樹的根結(jié)點(diǎn)的子樹；訪問森林中第一棵樹的根結(jié)點(diǎn)；后序遍歷去掉第一棵樹后的子森林。

BCDAFEHIGFEADCBGIH森林的遍歷與轉(zhuǎn)換的相應(yīng)二叉樹的遍歷序列有什么關(guān)系？ABCDEFGHIJKLMNO先序遍歷：后序遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDA6.5二叉樹的應(yīng)用哈夫曼樹(Huffman)——帶權(quán)路徑長度最短的樹定義路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的~路徑長度：路徑上的分支數(shù)目若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和PL樹的外部路徑長度是各葉結(jié)點(diǎn)(外結(jié)點(diǎn))到根結(jié)點(diǎn)的路徑長度之和EPL。樹的內(nèi)部路徑長度是各非葉結(jié)點(diǎn)(內(nèi)結(jié)點(diǎn))到根結(jié)點(diǎn)的路徑長度之和IPL。

樹的路徑長度PL=EPL+IPL12345678樹的外部路徑長度EPL=3*1+2*3=9樹的內(nèi)部路徑長度IPL=1*2+2*1=4樹的外部路徑長度EPL=1*1+2*1+3*1+4*1=1023456781結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度：若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積稱為結(jié)點(diǎn)的帶權(quán)路徑長度。樹的帶權(quán)路徑長度（WeightedPathLength

，WPL）：樹的各葉結(jié)點(diǎn)所帶的權(quán)值

wi與該結(jié)點(diǎn)到根的路徑長度

li的乘積的和。Huffman樹——帶權(quán)路徑長度達(dá)到最小的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。例有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35對于已知的一組葉子的權(quán)值W1，W2，…，Wn：構(gòu)造Huffman樹的方法——Huffman算法構(gòu)造Huffman樹步驟以權(quán)值分別為W1,W2．．．,Wｎ的ｎ個(gè)結(jié)點(diǎn)，構(gòu)成n棵二叉樹T1,T2,．．．,Tn并組成森林F={T1,T2,．．．Tn},其中每棵二叉樹Ti僅有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)；在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新二叉樹，并且置新二叉樹根結(jié)點(diǎn)權(quán)值為左右子樹上根結(jié)點(diǎn)的權(quán)值之和（根結(jié)點(diǎn)的權(quán)值=左右孩子權(quán)值之和，葉結(jié)點(diǎn)的權(quán)值=Wi）從F中刪除這兩棵二叉樹，同時(shí)將新二叉樹加入到F中;重復(fù)(2)、(３)直到F中只含一棵二叉樹為止，這棵二叉樹就是Huffman樹。F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}

7524初始合并{2}{4}75246F:{18}

1175246合并{5}{6}5合并{7}{11}27461118舉例霍夫曼樹的構(gòu)造過程例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100

由哈夫曼樹構(gòu)造思想得知，初始森林中共有n棵二叉樹，每棵樹中都僅有一個(gè)孤立的結(jié)點(diǎn)，接著將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹合并成一棵新的二叉樹。每次都是將兩個(gè)子樹合并，所以不存在度為1的結(jié)點(diǎn)特點(diǎn)1：哈夫曼樹中不存在度為1的結(jié)點(diǎn)由哈夫曼樹構(gòu)造思想得知，初始森林中共有n棵二叉樹，每棵樹中都僅有一個(gè)孤立的結(jié)點(diǎn)，接著將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹合并成一棵新的二叉樹。每合并一次，森林中就減少一棵樹。顯然要進(jìn)行n-1次合并，才能使森林中的二叉樹的數(shù)目，由n棵減少到只剩下一棵最終的哈夫曼樹。并且每次合并，都要產(chǎn)生一個(gè)新結(jié)點(diǎn)。合并n-1次共產(chǎn)生n-1個(gè)新結(jié)點(diǎn)，并且它們都是具有兩個(gè)孩子的分支結(jié)點(diǎn)。由此可知，最終求得的哈夫曼樹中共有2n-1個(gè)結(jié)點(diǎn)。特點(diǎn)2：n個(gè)葉子結(jié)點(diǎn)構(gòu)造的哈夫曼樹中，共有2n-1個(gè)結(jié)點(diǎn)特點(diǎn)3：任一棵哈夫曼樹的帶樹路徑長度等于所有分支結(jié)點(diǎn)（非葉子結(jié)點(diǎn)）值的累加和。11358192342291487152958100哈夫曼結(jié)點(diǎn)結(jié)構(gòu)(采用靜態(tài)鏈表)w