教學(xué)內(nèi)容第1章緒論第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章排序集合——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系。線性結(jié)構(gòu)——一個(gè)對一個(gè)，如線性表、棧、隊(duì)列、串、數(shù)組等。樹形結(jié)構(gòu)——一個(gè)對多個(gè)，如樹。圖形結(jié)構(gòu)——多個(gè)對多個(gè)，如圖。邏輯結(jié)構(gòu)樹型結(jié)構(gòu)（非線性結(jié)構(gòu)）結(jié)點(diǎn)之間一對多關(guān)系具有層次關(guān)系例自然界：樹人類社會(huì)家譜行政組織機(jī)構(gòu)計(jì)算機(jī)領(lǐng)域國務(wù)院河南省北京市西藏自治區(qū)…

南陽市鄭州市信陽市…

宛城區(qū)臥龍區(qū)…

鎮(zhèn)平縣第6章樹和二叉樹6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用6.1樹的定義和基本術(shù)語1樹的定義

樹(Tree)是n(n≧0)個(gè)結(jié)點(diǎn)的有限集合T，若n=0時(shí)稱為空樹，否則：⑴有且只有一個(gè)特定的結(jié)點(diǎn)稱為樹的根(Root)結(jié)點(diǎn)；⑵若n>1時(shí)，其余的結(jié)點(diǎn)被分為m(m>0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集本身又是一棵樹，稱其為根的子樹(Subtree)。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)后繼。這是樹的遞歸定義，即用樹來定義樹。樹是n個(gè)結(jié)點(diǎn)的有限集T1T2T32.樹的抽象數(shù)據(jù)類型定義ADTTree{數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:若D為空集，則稱為空樹；//允許n=0若D中僅含一個(gè)數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于數(shù)據(jù)元素的說明基本操作P：…//至少有15個(gè)（教材p119）}ADTTree3.樹的其他表示形式凹入表示嵌套集合廣義表4.樹的基本術(shù)語結(jié)點(diǎn)(node)——表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支；結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹數(shù)；樹的度——一棵樹中最大的結(jié)點(diǎn)度數(shù)；葉子(leaf)——度為0的結(jié)點(diǎn)，也稱為終端結(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)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……；深度(depth)——樹中結(jié)點(diǎn)的最大層次數(shù)；森林(forest)——m(m0)棵互不相交的樹的集合；有序樹——樹中結(jié)點(diǎn)的各子樹看成從左到右是有次序的（即不能互換），則稱該樹為有序樹。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的祖先樹形結(jié)構(gòu)和線性結(jié)構(gòu)的比較線性結(jié)構(gòu)樹形結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素?zé)o前驅(qū)根結(jié)點(diǎn)（只有一個(gè)）無雙親最后一個(gè)數(shù)據(jù)元素?zé)o后繼葉子結(jié)點(diǎn)(可以有多個(gè))無孩子其它數(shù)據(jù)元素一個(gè)前驅(qū),一個(gè)后繼其它結(jié)點(diǎn)一個(gè)雙親,多個(gè)孩子一對一一對多6.2二叉樹6.2.1二叉樹的定義定義：二叉樹是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))二叉樹的子樹有左、右之分，且其次序不能任意顛倒二叉樹的5種基本形態(tài)A只有根結(jié)點(diǎn)的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空

練習(xí)：具有3個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？普通樹呢？二叉樹：5種普通樹：2種ADTBinaryTree{數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于數(shù)據(jù)元素的說明④……//關(guān)于左子樹和右子樹的說明基本操作P：…//至少有20個(gè)}ADTBinaryTree二叉樹的抽象數(shù)據(jù)類型定義6.2.2二叉樹的性質(zhì)性質(zhì)1：在非空二叉樹中，第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≧1)。證明：用歸納法證明之①i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i-1=20=1是對的。②假設(shè)對所有j(1j<i)命題成立，即第j層上至多有2j-1個(gè)結(jié)點(diǎn)，那么，第i-1層至多有2i-2個(gè)結(jié)點(diǎn)。③∵二叉樹每個(gè)結(jié)點(diǎn)的度至多為2∴第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即2·2i-2=2i-1性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≧1)。證明：由性質(zhì)1，可得深度為k的二叉樹最大結(jié)點(diǎn)數(shù)是對于二叉樹來說，每層結(jié)點(diǎn)最多的情況如下圖所示：891011121314154567231……第1層1個(gè)結(jié)點(diǎn)，21-1=1第2層2結(jié)點(diǎn)，即22-1=2第3層4結(jié)點(diǎn)，即23-1=4第4層8結(jié)點(diǎn)，即24-1=8第i層2i-1性質(zhì)3：對任何一棵二叉樹，若其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。證明：設(shè)n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)分支進(jìn)入，設(shè)B為分支總數(shù)，則n=B+1又：分支由度為1和度為2的結(jié)點(diǎn)射出，B=n1+2n2于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1特殊形態(tài)的二叉樹：滿二叉樹定義：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。完全二叉樹定義：深度為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。894101151213614157213894101152112673(a)滿二叉樹(b)完全二叉樹1362455674213(c)非完全二叉樹

完全二叉樹是滿二叉樹的一部分，而滿二叉樹是完全二叉樹的特例。性質(zhì)4：n個(gè)結(jié)點(diǎn)的完全二叉樹深度為：㏒2n

+1。

其中符號：x表示不大于x的最大整數(shù)。

x

表示不小于x的最小整數(shù)。證明：

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

2k-1-1<n≦2k-1或2k-1≦n<2k

取對數(shù)得：k-1<㏒2n<k因?yàn)閗是整數(shù)。

∴k=㏒2n

+1性質(zhì)5：若對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(深度為㏒2n+1)的結(jié)點(diǎn)按層（從第1層到第㏒2n

+1層)序自左至右進(jìn)行編號,則對于編號為i（1≦i≦n)的結(jié)點(diǎn)：⑴若i=1：則結(jié)點(diǎn)i是二叉樹的根，無雙親結(jié)點(diǎn)；否則，若i>1，則其雙親結(jié)點(diǎn)編號是

i/2

。⑵如果2i>n：則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無左孩子；否則，其左孩子結(jié)點(diǎn)編號是2i。⑶如果2i+1>n：則結(jié)點(diǎn)i無右孩子；否則，其右孩子結(jié)點(diǎn)編號是2i+1。證明：（留給大家思考，提示：使用數(shù)學(xué)歸納法）。6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)1順序存儲(chǔ)結(jié)構(gòu)二叉樹存儲(chǔ)結(jié)構(gòu)的類型定義：#defineMAX_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)

typedeftelemtypesqbitree[MAX_SIZE];//0號單元存儲(chǔ)根結(jié)點(diǎn)用一組地址連續(xù)的存儲(chǔ)單元依次“自上而下、自左至右”存儲(chǔ)完全二叉樹的數(shù)據(jù)元素。對于完全二叉樹上編號為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組的下標(biāo)值為i-1的分量中。對于一般的二叉樹，將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對照，存儲(chǔ)在一維數(shù)組中。abcdhiejklfg(a)完全二叉樹(b)非完全二叉樹abcdefgh???01234567891011

abcdefghijkl

(c)完全二叉樹的順序存儲(chǔ)形式012345678910abcde0h0

0

fg(d)非完全二叉樹的順序存儲(chǔ)形式二叉樹順序存儲(chǔ)的特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿二叉樹和完全二叉樹最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的單支樹需要長度為2k-1的一維數(shù)組。ABCD02614單支樹2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。①二叉鏈表結(jié)點(diǎn)。有三個(gè)域：一個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(jié)點(diǎn)的指針域LchilddataRchildtypedefstructBTNode{ElemTypedata;structBTNode*Lchild,*Rchild;}BTNode;ABCDEFGABCDEFG^^^^^^^^在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域證明：空指針個(gè)數(shù)：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1ABCDEFG^^^^^^^^三叉鏈表結(jié)點(diǎn)。除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域，用來指向結(jié)點(diǎn)的父結(jié)點(diǎn)。LchilddataparentRchildtypedefstructBTNode_3{ElemTypedata;structBTNode_3*Lchild,*Rchild,*parent;}BTNode_3;ABCDEFGABCDEFG^^^^^^^^^6.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹遍歷二叉樹(TraversingBinaryTree)：是指按指定的規(guī)律對二叉樹中的每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。所謂訪問是指對結(jié)點(diǎn)做某種處理。如：輸出信息、修改結(jié)點(diǎn)的值等。二叉樹是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都可能有左、右兩棵子樹，因此，需要尋找一種規(guī)律，使二叉樹上的結(jié)點(diǎn)能排列在一個(gè)線性隊(duì)列上，從而便于遍歷。二叉樹的基本組成：根結(jié)點(diǎn)、左子樹、右子樹。若能依次遍歷這三部分，就是遍歷了二叉樹。

若以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。若規(guī)定先左后右，則只有前三種情況，分別是：DLR——先(根)序遍歷。LDR——中(根)序遍歷。LRD——后(根)序遍歷。另外還有一種按層次遍歷：先訪問第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，……第n層的結(jié)點(diǎn)

先序遍歷：ABDEC中序遍歷：DBEAC后序遍歷：DEBCA層次遍歷：ABCDEABCDE+*A*/EDCB先序遍歷+**/ABCDE前綴表示（波蘭式）中序遍歷A/B*C*D+E中綴表示后序遍歷AB/C*D*E+后綴表示（逆波蘭式）層序遍歷+*E*D/CAB用二叉樹表示算術(shù)表達(dá)式（了解）DLRADLRDLR>B>>D>>CDLRADBC先序遍歷序列：ABDC若二叉樹為空，則空操作否則

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

先序遍歷左子樹(L)

先序遍歷右子樹(R)1.遍歷的算法實(shí)現(xiàn)－先序遍歷先序遍歷的遞歸算法voidPreorderTraverse(BTNode*T){if(T!=NULL){visit(T->data);/*訪問根結(jié)點(diǎn)*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}說明：visit()函數(shù)是訪問結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體問題而定。樹采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量T來指向。voidPreorder(BiTreeT，void(*visit)(BiTree)){//先序遍歷二叉樹

if(T){//T=NULL時(shí)，二叉樹為空樹，不做任何操作

visit(T);//通過函數(shù)指針*visit訪問根結(jié)

//點(diǎn)，以便靈活完成相應(yīng)的操作

Preorder(T->lchild,visit);//先序遍歷左子樹

Preorder(T->rchild,visit);//先序遍歷右子樹

}}//PreOrderTraverse主程序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);先序序列：ABDC2.遍歷的算法實(shí)現(xiàn)－中序遍歷若二叉樹為空，則空操作否則:

中序遍歷左子樹(L)

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

中序遍歷右子樹(R)ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷的遞歸算法voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*訪問根結(jié)點(diǎn)*/InorderTraverse(T->Rchild);}}3.遍歷的算法實(shí)現(xiàn)－后序遍歷若二叉樹為空，則空操作否則

后序遍歷左子樹(L)

后序遍歷右子樹(R)

訪問根結(jié)點(diǎn)(D)ADBCLRDLRDLRDA>>D>>CLRDB后序遍歷序列：DBCA后序遍歷的遞歸算法voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*訪問根結(jié)點(diǎn)*/}}

對遍歷的分析：

1.從前面的三種遍歷算法可以知道：如果將visit語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過3次。第1次經(jīng)過時(shí)訪問＝先序遍歷第2次經(jīng)過時(shí)訪問＝中序遍歷第3次經(jīng)過時(shí)訪問＝后序遍歷AFEDCBG2.二叉樹遍歷的時(shí)間效率和空間效率時(shí)間效率:O(n)

//每個(gè)結(jié)點(diǎn)只訪問一次空間效率:O(n)

//棧占用的最大輔助空間遍歷算法應(yīng)用

“遍歷”是二叉樹最重要的基本操作，是各種其它操作的基礎(chǔ)，二叉樹的許多其它操作都可以通過遍歷來實(shí)現(xiàn)。建立二叉樹的存儲(chǔ)結(jié)構(gòu)；求二叉樹的結(jié)點(diǎn)數(shù)；求二叉樹的深度等。重要結(jié)論：若二叉樹中各結(jié)點(diǎn)的值均不相同，則：由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。練習(xí)：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG

和

DECBHGFA，請畫出這棵二叉樹。①由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（A）；②由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹子孫（BDCE），其右部必全部是右子樹子孫（FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。ABFCD

EGH

遍歷二叉樹是按一定的規(guī)則將樹中的結(jié)點(diǎn)排列成一個(gè)線性序列，即是對非線性結(jié)構(gòu)的線性化操作。當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左右孩子，而不能直接得到結(jié)點(diǎn)的直接前驅(qū)和直接后繼。如何找到遍歷過程中動(dòng)態(tài)得到的每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼(第一個(gè)和最后一個(gè)除外)?如何保存這些信息?

另外，設(shè)一棵二叉樹有n個(gè)結(jié)點(diǎn)，則有n-1條邊(指針連線)，而n個(gè)結(jié)點(diǎn)共有2n個(gè)指針域(Lchild和Rchild)，顯然有n+1個(gè)空閑指針域未用。則可以利用這些空閑的指針域來存放結(jié)點(diǎn)的直接前驅(qū)和直接后繼信息。6.3.2線索二叉樹對結(jié)點(diǎn)的指針域做如下規(guī)定：◆若結(jié)點(diǎn)有左孩子，則Lchild指向其左孩子，否則，指向其直接前驅(qū)；◆若結(jié)點(diǎn)有右孩子，則Rchild指向其右孩子，否則，指向其直接后繼；為避免混淆,對結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個(gè)標(biāo)志域。LchildLtagdataRtagRchild0：Lchild域指示結(jié)點(diǎn)的左孩子1：Lchild域指示結(jié)點(diǎn)的前驅(qū)Ltag=0：Rchild域指示結(jié)點(diǎn)的右孩子1：Rchild域指示結(jié)點(diǎn)的后繼Rtag=用這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索；按照某種次序遍歷，加上線索的二叉樹稱之為線索二叉樹（ThreadedBinaryTree）。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫作線索化。線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)typedefstructBiThrNode{ElemTypedata;structBiTreeNode*Lchild,*Rchild;intLtag,Rtag;}BiThrNode;AFHIEGBDC(a)二叉樹

(b)先序線索樹的邏輯形式結(jié)點(diǎn)序列：ABDCEGFHIAFHIEGBDCNIL(d)后序線索樹的邏輯形式結(jié)點(diǎn)序列：DBGEHIFCA(c)中序線索樹的邏輯形式結(jié)點(diǎn)序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNIL

0A0

0B1

0C0?

1D1

0E1

0F0

1G1

1H1

1F1?(e)中序線索樹的鏈表結(jié)構(gòu)說明：畫線索二叉樹時(shí)，實(shí)線表示指針，指向其左、右孩子；虛線表示線索，指向其直接前驅(qū)或直接后繼。在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個(gè)結(jié)點(diǎn)，然后就可以依次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼為空為止。ABCDEABDCET先序序列：ABCDE00001111^11

lchildLTagdataRTagrchild先序線索二叉樹ABCDEABDCET中序序列：BCAED00001111^11^

lchildLTagdataRTagrchild中序線索二叉樹

lchildLTagdataRTagrchildABCDEABDCET后序序列：CBEDA0000111111^后序線索二叉樹6.5樹與森林6.5.1樹的存儲(chǔ)結(jié)構(gòu)6.5.2森林與二叉樹的轉(zhuǎn)換6.5.3樹的遍歷6.5.1樹的存儲(chǔ)結(jié)構(gòu)

樹的存儲(chǔ)結(jié)構(gòu)根據(jù)應(yīng)用的不同而不同，在這里介紹3中常用的存儲(chǔ)結(jié)構(gòu)。雙親表示法(順序存儲(chǔ)結(jié)構(gòu))孩子表示法（順序和鏈?zhǔn)浇Y(jié)合）孩子兄弟表示法（二叉樹表示法、二叉鏈表表示法）1雙親表示法(順序存儲(chǔ)結(jié)構(gòu))

用一組連續(xù)的存儲(chǔ)空間來存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附加一個(gè)指示器(整數(shù)域)，用以指示雙親結(jié)點(diǎn)的位置(下標(biāo)值)。數(shù)組元素及數(shù)組的類型定義如下：#defineMAX_SIZE100typedefstructPTNode//結(jié)點(diǎn)結(jié)構(gòu){ElemTypedata;//數(shù)據(jù)域，存放結(jié)點(diǎn)數(shù)值intparent;//指針域，指向雙親位置}PTNode;typedefstruct//樹結(jié)構(gòu){PTNodeNodes[MAX_SIZE];introot;//根結(jié)點(diǎn)位置intnum;//結(jié)點(diǎn)數(shù)}Ptree;這種存儲(chǔ)結(jié)構(gòu)利用了任一結(jié)點(diǎn)的父結(jié)點(diǎn)唯一的性質(zhì)。可以方便地直接找到任一結(jié)點(diǎn)的父結(jié)點(diǎn)，但求結(jié)點(diǎn)的子結(jié)點(diǎn)時(shí)需要掃描整個(gè)數(shù)組。樹的雙親表示法R-10A01B02C03D14E15F36G67H68I69FGHIRABCDE2孩子鏈表表示法樹中每個(gè)結(jié)點(diǎn)有多個(gè)指針域，每個(gè)指針指向其一棵子樹的根結(jié)點(diǎn)。有兩種結(jié)點(diǎn)結(jié)構(gòu)。⑴定長結(jié)點(diǎn)結(jié)構(gòu)

指針域的數(shù)目就是樹的度。其特點(diǎn)是：鏈表結(jié)構(gòu)簡單，但指針域的浪費(fèi)明顯。在一棵有n個(gè)結(jié)點(diǎn)，度為k的樹中必有n(k-1)+1空指針域。⑵不定長結(jié)點(diǎn)結(jié)構(gòu)

樹中每個(gè)結(jié)點(diǎn)的指針域數(shù)量不同，是該結(jié)點(diǎn)的度。沒有多余的指針域，但操作不便。datachild1child2

?childn(a)定長結(jié)點(diǎn)結(jié)構(gòu)(b)不定長結(jié)點(diǎn)結(jié)構(gòu)datakchild1child2

?childk⑶復(fù)合鏈表結(jié)構(gòu)

把樹中的每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，看成是一個(gè)線性表，且以單鏈表作存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)的樹有n個(gè)(孩子)單鏈表(葉子結(jié)點(diǎn)的孩子鏈表為空)，而n個(gè)頭結(jié)點(diǎn)又組成一個(gè)線性表且以順序存儲(chǔ)結(jié)構(gòu)表示。表結(jié)點(diǎn)和頭結(jié)點(diǎn)的結(jié)構(gòu)如下圖所示。

datafirstchild(a)頭結(jié)點(diǎn)childnonext(b)表結(jié)點(diǎn)孩子鏈表結(jié)點(diǎn)結(jié)構(gòu)nodes789?35?012?6?0123456789MAX_NODE-1rootnumAB?CD?E?FG?H?

I?┇┇R49FGHIRABCDE3孩子兄弟表示法(二叉樹表示法)

以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)形式如圖所示。兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類型定義如下：typedefstructCSnode{ElemTypedata;structCSnode*firstchild,*nextsibling;}CSNode;孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchilddatanextsibling

孩子兄弟存儲(chǔ)結(jié)構(gòu)

R?

A?D

C??G?B?F??E?

樹

FGRABCDE6.5.2森林與二叉樹的轉(zhuǎn)換

由于二叉樹和樹都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，對比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可以導(dǎo)出樹和二叉樹之間的一個(gè)對應(yīng)關(guān)系。◆從物理結(jié)構(gòu)來看，樹和二叉樹的二叉鏈表是相同的，只是對指針的邏輯解釋不同而已。

◆從樹的二叉鏈表表示的定義可知，任何一棵和樹對應(yīng)的二叉樹，其右子樹一定為空。

樹與二叉樹的對應(yīng)關(guān)系二叉樹

CERADB

R?

A?D??C?

B?E?樹

RABCDE對應(yīng)關(guān)系

R?

A?D??C?

B?E??C?

B?E?

R

A?D?存儲(chǔ)解釋存儲(chǔ)解釋樹和二叉樹之間的對應(yīng)關(guān)系樹：兄弟關(guān)系二叉樹：雙親和右孩子樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG

1.兄弟加線.ABCDEFG1樹轉(zhuǎn)換成二叉樹1樹轉(zhuǎn)換成二叉樹ABCDEFG1.兄弟加線.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1樹轉(zhuǎn)換成二叉樹ABCDEFG1.兄弟加線.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.1樹轉(zhuǎn)換成二叉樹GDABECF1.兄弟加線.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.1樹轉(zhuǎn)換成二叉樹詳細(xì)步驟是：⑴加線——樹中所有相鄰兄弟之間加一條連線。

⑵去線——對樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線。

⑶層次調(diào)整——以根結(jié)點(diǎn)為軸心，將樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之層次分明。

這樣轉(zhuǎn)換后的二叉樹的特點(diǎn)是：

◆二叉樹的根結(jié)點(diǎn)沒有右子樹，只有左子樹；

◆左子樹結(jié)點(diǎn)仍然是原來樹中相應(yīng)結(jié)點(diǎn)的左子結(jié)點(diǎn)，而所有沿右鏈往下的右子樹結(jié)點(diǎn)均是原來樹中該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。樹向二叉樹的轉(zhuǎn)換過程(a)一般的樹

FGRABCDEFGRABCDE(b)加虛線，去連線后

(C)轉(zhuǎn)換后的二叉樹FGRACDBE2二叉樹轉(zhuǎn)換為樹或森林⑴加線——若某結(jié)點(diǎn)x是其雙親y的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、……，都與結(jié)點(diǎn)y用線連起來；⑵去線——?jiǎng)h去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；⑶

層次調(diào)整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

FHGEAICDBFHGDCEBAIFEDCBAHGI加線層次調(diào)整IHGBCDAFE3森林轉(zhuǎn)換為二叉樹森林定義為：F={T1，T2，T3，…,Tm}①將F={T1,T2,?,Tn}中的每棵樹轉(zhuǎn)換成二叉樹。②按給出的森林中樹的次序，從最后一棵二叉樹開始，每棵二叉樹作為前一棵二叉樹的根結(jié)點(diǎn)的右子樹，依次類推，則第一棵樹的根結(jié)點(diǎn)就是轉(zhuǎn)換后生成的二叉樹的根結(jié)點(diǎn)。ACBDGMLHK(a)森林(b)森林中每棵樹對應(yīng)的二叉樹ABCDGLKHM(c)森林對應(yīng)的二叉樹ABCDGLKHM4二叉樹轉(zhuǎn)換為森林①去連線。將二叉樹B的根結(jié)點(diǎn)與其右子結(jié)點(diǎn)以及沿右子結(jié)點(diǎn)鏈方向的所有右子結(jié)點(diǎn)的連線全部去掉，得到若干棵孤立的二叉樹，每一棵就是原來森林F中的樹依次對應(yīng)的二叉樹。②二叉樹的還原。將各棵孤立的二叉樹按二叉樹還原為樹的方法還原成一般的樹。ACBDMGLHK(c)還原成森林(a)二叉樹ABCDGLKHM(b)去連線后ABCDMGLKH6.5.3樹和森林的遍歷1樹的遍歷

由樹結(jié)構(gòu)的定義可知，樹的遍歷有二種方法。⑴先序遍歷：先訪問根結(jié)點(diǎn)，然后依次先序遍歷完每棵子樹。如圖所示的樹，先序遍歷的次序是：ABCDEFGIJHK⑵后序遍歷：先依次后序遍歷完每棵子樹，然后訪問根結(jié)點(diǎn)。如圖所示的樹，后序遍歷的次序是：CDBFIJGHEKAABDCKGJIFHE說明：樹的先序遍歷實(shí)質(zhì)上與轉(zhuǎn)換成的二叉樹后對二叉樹的先序遍歷相同。樹的后序遍歷實(shí)質(zhì)上與轉(zhuǎn)換成的二叉樹后對二叉樹的中序遍歷相同。2森林的遍歷設(shè)F={T1,T2,?,Tn}是森林，對F的遍歷有二種方法。⑴先序遍歷：按先序遍歷樹的方式依次遍歷F中的每棵樹。⑵中序遍歷：按后序遍歷樹的方式依次遍歷F中的每棵樹。6.6赫夫曼樹及其應(yīng)用

赫夫曼(Huffman)樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。6.6.1最優(yōu)二叉樹(Huffman樹)1基本概念①路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。②路徑長度：結(jié)點(diǎn)路徑上的分支數(shù)目稱為路徑長度。③樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。④

結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)的到樹的根結(jié)點(diǎn)之間的路徑長度與結(jié)點(diǎn)的權(quán)(值)的乘積。權(quán)(值)：各種開銷、代價(jià)、頻度等的抽象稱呼。⑤

樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記做：

WPL=w1l1+w2l2+?+wnln=∑wili(i=1,2,?,n)其中：n為葉子結(jié)點(diǎn)的個(gè)數(shù)；wi為第i個(gè)結(jié)點(diǎn)的權(quán)值；

li為第i個(gè)結(jié)點(diǎn)的路徑長度。⑥

Huffman樹：具有n個(gè)葉子結(jié)點(diǎn)(每個(gè)結(jié)點(diǎn)的權(quán)值為wi)的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵WPL值最小的樹，稱這棵樹為Huffman樹(或稱最優(yōu)樹)。如圖具有4個(gè)葉子a，b，c，d結(jié)點(diǎn)的二叉樹，權(quán)值分別為2、3、6、7，它們的帶權(quán)路徑長度分別為：(a)WPL=22+32+62+72=36；(b)WPL=21+32+63+73=47；(c)WPL=71+62+23+33=34。

其中(c)的WPL值最小，可以證明是Huffman樹。abcdbcdacdab(a)(b)(c)具有相同葉子結(jié)點(diǎn)，不同帶權(quán)路徑長度的二叉樹222333666777哈夫曼樹的特點(diǎn)：1.權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2.只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).2Huffman樹的構(gòu)造⑴初始化：由給定的n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合F＝{T1，T2，…，Tn}；⑵選取與合并：在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；⑶刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；⑷重復(fù)⑵、⑶兩步，當(dāng)集合F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是哈夫曼樹。權(quán)值集合W={8,3,4,6,5,5}構(gòu)造Huffman樹的過程。所構(gòu)造的Huffman樹的WPL是：WPL=62+33+43+82+53+53=79345568第一步5568第二步34768第三步34755108第四步5510634713第六步1111100000855101863471331第五步85510186347136.6.2赫夫曼編碼及其算法在電報(bào)收發(fā)等數(shù)據(jù)通訊中，常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的字符串來傳輸。為了使收發(fā)的速度提高，就要求電文編碼要盡可能地短。此外，要設(shè)計(jì)長短不等的編碼，還必須保證任意字符的編碼都不是另一個(gè)字符編碼的前綴，這種編碼稱為前綴編碼。

Huffman樹可以用來構(gòu)造編碼長度不等且譯碼不產(chǎn)生二義性的編碼。