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

1、第6章 樹和二叉樹6.1 樹的定義和基本術(shù)語6.2 二叉樹6.3 遍歷二叉樹6.4 線索二叉樹6.5 樹和森林6.6 哈夫曼樹教學(xué)目的、要求1領(lǐng)會樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別。2熟記二叉樹的主要特性，并掌握它們的證明方法。3熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。4理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。5熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及其建立的算法。6學(xué)會編寫實現(xiàn)樹的各種操作的算法。7了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。6.1 樹的定義和基本術(shù)語6.1.1樹的定義樹是由n（n0）個結(jié)點組成的有

2、限集合。若n=0，稱為空樹；若n0，則：有一個特定的稱為根（root）的結(jié)點。它只有直接后繼，但沒有直接前驅(qū)；除根結(jié)點以外的其它結(jié)點可以劃分為m（m0）個互不相交的有限集合T0，T1，Tm-1，每個集合Ti（i=0,1,m-1）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。 樹的結(jié)構(gòu)參見下圖：圖6.1樹的結(jié)構(gòu)在圖6.1(c)中，樹的根結(jié)點為A，該樹還可以分為三個互不相交子集T0，T1，T2，其中T0=B，E，F(xiàn)，J，K，L，T1=C，G，T2=D，H，I，M，其中的T0，T1，T2都

3、是樹，稱為圖6.1(C)中樹的子樹，而T0，T1，T2又可以分解成若干棵不相交子樹。如T0可以分解成T00，T01兩個不相交子集，T00=E，J，K，L，T01=F，而T00又可以分為三個不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。樹的抽象數(shù)據(jù)類型定義見教材P118-1196.1.2 基本術(shù)語1. 結(jié)點指樹中的一個數(shù)據(jù)元素，一般用一個字母表示。2. 度一個結(jié)點包含子樹的數(shù)目，稱為該結(jié)點的度。3. 樹葉（葉子）度為0的結(jié)點，稱為葉子結(jié)點或樹葉，也叫終端結(jié)點。4. 孩子結(jié)點若結(jié)點X有子樹，則子樹的根結(jié)點為X的孩子結(jié)點，也稱為孩子，兒子，子女等。如圖6.1

4、（c）中A的孩子為B，C，D。5. 雙親結(jié)點若結(jié)點X有子女Y，則X為Y的雙親結(jié)點。6. 祖先結(jié)點從根結(jié)點到該結(jié)點所經(jīng)過分枝上的所有結(jié)點為該結(jié)點的祖先，如圖6-1（c）中M的祖先有A，D ，H 。7. 子孫結(jié)點某一結(jié)點的子女及子女的子女都為該結(jié)點子孫。8. 兄弟結(jié)點具有同一個雙親的結(jié)點，稱為兄弟結(jié)點。9. 分枝結(jié)點除葉子結(jié)點外的所有結(jié)點，為分枝結(jié)點，也叫非終端結(jié)點。10. 層數(shù)根結(jié)點的層數(shù)為1，其它結(jié)點的層數(shù)為從根結(jié)點到該結(jié)點所經(jīng)過的分支數(shù)目再加1。11. 樹的深度（高度）樹中結(jié)點所處的最大層數(shù)稱為樹的高度，如空樹的高度為0，只有一個根結(jié)點的樹高度為1。12. 樹的度樹中結(jié)點度的最大值稱為樹的度

5、。13. 有序樹若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。14. 無序樹若一棵樹中所有子樹的次序無關(guān)緊要，則稱為無序樹。15森林若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個特殊的森林。6.1.3 樹的表示1. 樹形結(jié)構(gòu)表示法2. 凹入法表示法圖6.1（c）的樹的凹入法表示3. 嵌套集合表示法圖6.1（c）的嵌套集合表示4. 廣義表表示法對圖6-1（c）的樹結(jié)構(gòu)，廣義表表示法可表示為：（A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I）6.1.4 樹的性質(zhì)性質(zhì)1 樹中的結(jié)點數(shù)等于所有結(jié)點的度加1。證明：根據(jù)樹的定義，在一棵樹中，除根結(jié)點以外，

6、每個結(jié)點有且僅有一個直接前驅(qū)，也就是說，每個結(jié)點與指向它的一個分支一一對應(yīng)，所以，除根結(jié)點以外的結(jié)點數(shù)等于所有結(jié)點的分支數(shù)（即度數(shù)），而根結(jié)點無直接前驅(qū)，因此，樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1。性質(zhì)2 度為k的樹中第i層上最多有ki-1個結(jié)點（i1）。下面用數(shù)學(xué)歸納法證明：對于i=1，顯然成立，假設(shè)對于i-1層，上述條件成立，即第i-1層最多有ki-2個結(jié)點，對于第i層，結(jié)點數(shù)最多為第i-1層結(jié)點數(shù)的k倍（因為度為k），故第i層的結(jié)點數(shù)為ki-2*k= ki-1。性質(zhì)3 深度為h的 k叉樹最多有 個結(jié)點。證明：由性質(zhì)2可知，若每一層的結(jié)點數(shù)最多，則整個k叉樹結(jié)點數(shù)最多，共有 當(dāng)一棵K叉樹上的

7、結(jié)點數(shù)達(dá)到 時，稱為滿K叉樹。性質(zhì)4 具有n個結(jié)點的k叉樹的最小深度為 。（ 表示取不小于x的最小整數(shù)）證明：設(shè)具有n個結(jié)點的k叉樹的深度為h，在該樹的前面h-1層都是滿的，即每一層的結(jié)點數(shù)等于ki-1個(1ih-1)，第h層（即最后一層）的結(jié)點數(shù)可能滿，也可能不滿，這時，該樹具有最小的深度。由性質(zhì)3知道，結(jié)點數(shù)n應(yīng)滿足下面條件：通過轉(zhuǎn)換為：kh-1n(k-1)+1kh，再取以k為底的對數(shù)后，可以得到： h-1logk(n(k-1)+1)h即有：logk(n(k-1)+1)hn，則結(jié)點i無左孩子，否則i的左孩子為2i。即滿足2in的結(jié)點為葉子結(jié)點；若2i+1n，則結(jié)點i無右孩子，否則i的右孩子

8、為2i+1；若結(jié)點i為奇數(shù)且不等于1，則它的左兄弟為i-1；若結(jié)點i為偶數(shù)且不等于n，它的右兄弟為i+1；結(jié)點i所在層數(shù)(層次)為 ；6.2.3 二叉樹的存貯結(jié)構(gòu)1. 順序存貯結(jié)構(gòu)按二叉樹的結(jié)點自上而下、從左至右編號，用一組連續(xù)的存儲單元存儲。若該二叉樹為非完全二叉樹，則必須將相應(yīng)位置空出來，使存放的結(jié)果符合完全二叉樹形狀。圖6.7 二叉樹的順序存儲對于一棵二叉樹，若采用順序存貯時，當(dāng)它為完全二叉樹時，比較方便,若為非完全二叉樹，將會浪費大量存貯存貯單元。最壞的非完全二叉樹是全部只有右分支，設(shè)高度為K，則需占用2K-1個存貯單元，而實際只有k個元素，實際只需k個存儲單元。因此，對于非完全二叉樹

9、，宜采用下面的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2. 二叉鏈表存貯結(jié)構(gòu) 二叉鏈表表示將一個結(jié)點分成三部分，一部分存放結(jié)點本身信息，另外兩部分為指針，分別存放左、右孩子的地址。注：如果需要倒查某結(jié)點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。lchilddatarchild對于圖6.7所示二叉樹，用二叉鏈表形式描述。圖6.8 二叉樹的二叉鏈表表示 二叉鏈表的數(shù)據(jù)類型bitree.h/二叉鏈表定義#include using namespace std;typedef char TElemType;struct BiTNodeTElemType data;BiTNode *lchild,*r

10、child;typedef BiTNode *BiTree;void initBiTree(BiTree &T);void createBiTree(BiTree &T); /遞歸前序遍歷void preOrderTraverse(BiTree T,void (*visit)(TElemType); /非遞歸前序遍歷void preOrderTraverse1(BiTree T,void (*visit)(TElemType);/遞歸中序遍歷 void inOrderTraverse(BiTree T,void (*visit)(TElemType); /遞歸后序遍歷void postOrde

11、rTraverse(BiTree T,void (*visit)(TElemType); 二叉鏈表的建立為了后面遍歷二叉樹方便，先介紹建立二叉鏈表的算法（假設(shè)ElemType 為char型）。/按先序次序輸入二叉樹中結(jié)點的值（#表示空格），/構(gòu)造二叉鏈表表示的二叉樹T。void createBiTree(BiTree &T) TElemType ch;cinch;if(ch=#) / 空T=NULL;elseT=new BiTNode;if(!T)exit(1);T-data=ch; / 生成根結(jié)點createBiTree(T-lchild); / 構(gòu)造左子樹createBiTree(T-rc

12、hild); / 構(gòu)造右子樹6.3 遍歷二叉樹遍歷是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次。這里提到的訪問是指對結(jié)點施行某種操作，操作可以是輸出結(jié)點信息，修改結(jié)點的數(shù)據(jù)值等，但要求這種訪問不破壞它原來的數(shù)據(jù)結(jié)構(gòu)。在本書中，我們規(guī)定訪問是輸出結(jié)點信息data，且以二叉鏈表作為二叉樹的存貯結(jié)構(gòu)。由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點可能有一個以上的直接后繼，因此，必須規(guī)定遍歷的規(guī)則，并按此規(guī)則遍歷二叉樹，最后得到二叉樹所有結(jié)點的一個線性序列。令L、R、D分別代表二叉樹的左子樹、右子

13、樹、根結(jié)點，則遍歷二叉樹有6種規(guī)則：DLR、DRL、LDR、LRD、RDL、RKD。若規(guī)定二叉樹中必須先左后右(左右順序不能顛倒)，則只有DLR、LDR、LRD三種遍歷規(guī)則。DLR稱為前根遍歷(或前序遍歷、先序遍歷、先根遍歷)，LDR稱為中根遍歷(或中序遍歷)，LRD稱為后根遍歷(或后序遍歷)。6.3.1 前序遍歷所謂前序遍歷，就是根結(jié)點最先遍歷，其次左子樹，最后右子樹。1. 遞歸遍歷前序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則輸出根結(jié)點；前根遍歷左子樹;前根遍歷右子樹。/ 先序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次void preOrderTraverse

14、(BiTree T,void (*visit)(TElemType) if(T) / T不空visit(T-data); / 先訪問根結(jié)點preOrderTraverse(T-lchild,visit); / 再先序遍歷左子樹preOrderTraverse(T-rchild,visit); / 最后先序遍歷右子樹2. 非遞歸遍歷利用一個一維數(shù)組作棧，來存貯二叉鏈表中結(jié)點，算法思想為：從二叉樹根結(jié)點開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，訪問所遇結(jié)點，并依次把所遇結(jié)點進(jìn)棧，當(dāng)左子樹為空時，從棧頂退出某結(jié)點，并將指針指向該結(jié)點的右孩子。如此重復(fù)，直到棧為空或指針為空止。 /前

15、序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visitvoid preOrderTraverse1(BiTree T,void (*visit)(TElemType)BiTree s100;int top=0; /top為棧頂指針while(T!=NULL)|(top0)while(T!=NULL)visit(T-data); stop+=T;T=T-lchild;T=s-top;T=T-rchild;6.3.2 中序遍歷所謂中序遍歷，就是根在中間，先左子樹，然后根結(jié)點，最后右子樹。中序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則中根遍歷左子樹;輸出根結(jié)點;中

16、根遍歷右子樹。/中序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次void inOrderTraverse(BiTree T,void (*visit)(TElemType)if(T)inOrderTraverse(T-lchild,visit); / 先中序遍歷左子樹visit(T-data); / 再訪問根結(jié)點inOrderTraverse(T-rchild,visit); / 最后中序遍歷右子樹6.3.3 后序遍歷所謂后序遍歷，就是根在最后，即先左子樹，然后右子樹，最后根結(jié)點。后序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結(jié)束；否則后根遍歷左子樹:后根遍歷歷子樹;訪問根結(jié)

17、點。/后序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次void postOrderTraverse(BiTree T,void (*visit)(TElemType)if(T)inOrderTraverse(T-lchild,visit); / 后序遍歷左子樹inOrderTraverse(T-rchild,visit); / 再后序遍歷右子樹visit(T-data); / 最后訪問根結(jié)點6.3.4 按層次遍歷對于一棵二叉樹，若規(guī)定遍歷順序為從上到下(上層遍歷完才進(jìn)入下層)，從左到右(同一層從左到右進(jìn)行，這樣的遍歷稱為按層次遍歷。下面用一個一維數(shù)組來模擬隊列，實現(xiàn)二叉樹的層次遍歷。/

18、層序遍歷T(利用隊列),對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次void levelOrderTraverse(BiTree T,void (*visit)(TElemType)BiTree q100,p;int f,r; / f,r類似于頭尾指針q0=T;f=0;r=1;while(fdata);if(p-lchild!=NULL)qr+=p-lchild; /入隊if(p-rchild!=NULL)qr+=p-rchild; /入隊6.4 線索二叉樹6.4.1 線索的概念通過前面介紹的二叉樹可知，遍歷二叉樹實際上就是將樹中所有結(jié)點排成一個線性序列（即非線性結(jié)構(gòu)線性化），在這樣的線性序列中，

19、很容易求得某個結(jié)點在某種遍歷下的直接前驅(qū)和后繼。然而，有時我們希望不進(jìn)行遍歷就能快速找到某個結(jié)點在某種遍歷下的直接前驅(qū)和后繼，這樣，就應(yīng)該把每個結(jié)點的直接前驅(qū)和直接后繼記錄下來。為了做到這一點，可以在原來的二叉鏈表結(jié)點中，再增加兩個指針域，一個指向前驅(qū)，一個指向后繼，但這樣做將會浪費大量存貯單元，存貯空間的利用率相當(dāng)?shù)?一個結(jié)點中有4個指針，1個指左孩子，1個指右孩子，1個指前驅(qū)，1個指后繼)，而原來的左、右孩子域有許多空指針又沒有利用起來（在有n個結(jié)點的二叉鏈表中必定存在n+1個空鏈域）。為了不浪費存存貯空間，我們利用原有的孩子指針為空時來存放直接前驅(qū)和后繼，這樣的指針稱為線索，加線索的過程

20、稱為線索化，加了線索的二叉樹，稱為線索二叉樹，對應(yīng)的二叉鏈表稱為線索二叉鏈表。在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結(jié)點在某種遍歷下的直接前驅(qū)和后繼。但是，我們怎樣來區(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅(qū)或直接后繼信息呢?為此，在二叉鏈表結(jié)點中，還必須增加兩個標(biāo)志域ltag、rtag。ltag和rtag定義如下：這樣，二叉鏈表中每個結(jié)點還是有5個域，但其中只有2個指針，較原來的4個指針要方便。增加線索后的二叉鏈表結(jié)點結(jié)構(gòu)可描述如下： lchildltagdatartagrchild前序序列為：ABCD。圖 前序線索中序序列為：BADC。圖 中序線索后序序列為：B

21、DCA。圖 后序線索6.4.3 線索的算法實現(xiàn)在此，僅介紹中序線索二叉樹的算法實現(xiàn)。為方便起見，依照線性表的存儲結(jié)構(gòu)，在二叉樹的線索鏈表上也添加一個頭結(jié)點，并令其lchild域的指針指向二叉樹的根結(jié)點，其rchild域的指針指向中序遍歷時訪問的最后一個結(jié)點，并令二叉樹中序序列中的第一個結(jié)點的lchild域指針和最后一個結(jié)點的rchild域的指針均指向頭結(jié)點。圖 中序線索鏈表（中序序列為：BADC）由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷的過程中修改空指針的過程。為了記下遍歷過程中訪問結(jié)點的先后關(guān)系，需附設(shè)

22、一個指針pre始終指向剛剛訪問過的結(jié)點。1. 線索鏈表類型定義inthreading.h#include using namespace std;typedef char TElemType;enum PointerTagLink,Thread; /Link=0:指針，Thread=1:線索struct BiThrNodeTElemType data;BiThrNode *lchild,*rchild;PointerTag ltag,rtag;typedef BiThrNode *BiThrTree;void createBiThrTree(BiThrTree &T);void preOrde

23、rTraverse(BiThrTree T,void (*visit)(TElemType);BiThrNode* inOrderThreading(BiThrTree T);void inTraverseThr(BiThrTree T,void (*visit)(TElemType);2. 實現(xiàn)inthreading.cpp#include inthreading.h/按先序次序輸入二叉樹中結(jié)點的值（#表示空格），構(gòu)造二叉線索樹Tvoid createBiThrTree(BiThrTree &T) TElemType ch;cinch;if(ch=#) / 空T=NULL;elseT=new

24、 BiThrNode;if(!T)exit(1);T-data=ch; / 生成根結(jié)點createBiThrTree(T-lchild); / 構(gòu)造左子樹if(T-lchild) / 有左孩子T-ltag=Link;createBiThrTree(T-rchild); / 構(gòu)造右子樹if(T-rchild) / 有右孩子T-rtag=Link;/ 先序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次void preOrderTraverse(BiThrTree T,void (*visit)(TElemType) if(T) / T不空visit(T-data); / 先訪問根結(jié)點preO

25、rderTraverse(T-lchild,visit); / 再先序遍歷左子樹preOrderTraverse(T-rchild,visit); / 最后先序遍歷右子樹BiThrTree pre; / 全局變量,始終指向剛剛訪問過的結(jié)點void inThreading(BiThrTree p) / 中序遍歷進(jìn)行中序線索化if(p)inThreading(p-lchild); / 左子樹線索化if(!p-lchild) / 沒有左孩子p-ltag=Thread; / 前驅(qū)線索p-lchild=pre; / 左孩子指針指向前驅(qū)if(!pre-rchild) / 前驅(qū)沒有右孩子pre-rtag=T

26、hread; / 后繼線索pre-rchild=p; / 前驅(qū)右孩子指針指向后繼(當(dāng)前結(jié)點p)pre=p; / 保持pre始終指向剛剛訪問過的結(jié)點inThreading(p-rchild); / 右子樹線索化/中序遍歷二叉樹T,并將其中序線索化,BiThrNode* inOrderThreading(BiThrTree T) BiThrNode* Thrt=new BiThrNode; /Thrt指向頭結(jié)點 Thrt-ltag=Link; Thrt-rtag=Thread;Thrt-rchild=Thrt; /右指針回指if(!T) /若二叉樹空，則左指針回指Thrt-lchild=Thrt;

27、elseThrt-lchild=T;pre=Thrt;inThreading(T); /中序遍歷進(jìn)行中序線索化pre-rtag=Thread; /最后一個結(jié)點線索化pre-rchild=Thrt;Thrt-rchild=pre;return Thrt;/中序遍歷二叉線索樹T(頭結(jié)點)的非遞歸算法void inTraverseThr(BiThrTree T,void (*visit)(TElemType)BiThrTree p;p=T-lchild; /p指向根結(jié)點while(p!=T) /空樹或遍歷結(jié)束時,p=Twhile(p-ltag=Link)p=p-lchild;visit(p-data

28、); /訪問左子樹為空的結(jié)點while(p-rtag=Thread&p-rchild!=T)p=p-rchild;visit(p-data); /訪問后繼結(jié)點p=p-rchild;6.5 樹和森林6.5.1 樹的存儲結(jié)構(gòu)1. 雙親表示法它是以一組連續(xù)的存儲單元來存放樹中的結(jié)點，每個結(jié)點有兩個域：一個是data域，存放結(jié)點信息，另一個是parent域，用來存放雙親的位置(指針)。樹的雙親表示法2. 孩子表示法將一個結(jié)點所有孩子鏈接成一個單鏈表形，而樹中有若干個結(jié)點，故有若干個單鏈表，每個單鏈表有一個表頭結(jié)點，所有表頭結(jié)點用一個數(shù)組來描述。樹的孩子表示法3. 雙親孩子表示法將第1、2兩種方法結(jié)合起

29、來，則得到雙親孩子表示法。 雙親孩子表示法4. 孩子兄弟表示法類似于二叉鏈表，但第一根鏈指向第一個孩子，第二根鏈指向下一個兄弟。孩子兄弟表示法6.5.2 樹、森林和二叉樹的轉(zhuǎn)換1. 樹轉(zhuǎn)換成二叉樹（孩子-兄弟表示法）可以分為三步：加線將樹中同一結(jié)點的兄弟相連;抹線保留結(jié)點的最左孩子連線，刪除其它孩子連線；旋轉(zhuǎn)將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。討論：二叉樹怎樣還原為樹？要點：逆操作，把所有右孩子變?yōu)樾值?！樹轉(zhuǎn)換成二叉樹2. 森林轉(zhuǎn)換成二叉樹將森林中每一棵樹分別轉(zhuǎn)換成二叉樹；合并：使第n棵樹接入到第n-1棵的右邊并成為它的右子樹，第 n-1 棵二叉樹接入到第n-2 棵的右邊并成為它的右子樹，第

30、2棵二叉樹接入到第1棵的右邊并成為它的右子樹，直到最后剩下一棵二叉樹為止。森林轉(zhuǎn)換成二叉樹3. 二叉樹還原成樹或森林右鏈斷開將二叉樹的根結(jié)點的右鏈及右鏈的右鏈等全部斷開，得到若干棵無右子樹的二叉樹。二叉樹還原成樹將中得到的每一棵二叉樹都還原成樹（與樹轉(zhuǎn)換成二叉樹的步驟剛好相反）。二叉樹還原成森林的過程6.5.3 樹和森林的遍歷在樹和森林中，一個結(jié)點可能有兩棵以上的子樹，所以不宜討論它們的中序遍歷， 即樹和森林只有先序遍歷和后序遍歷。1. 先序遍歷 樹的先序遍歷若樹非空，則先訪問根結(jié)點，然后依次先序遍歷各子樹。 森林的先序遍歷若森林非空，則先訪問森林中第一棵樹的根結(jié)點，再先序遍歷第一棵樹各子樹，接著先序遍歷第二棵樹、第三棵樹、直到最后一棵樹。2. 后序遍歷 樹的后序遍歷若樹非空，則依次后序遍歷各子樹，最后訪問根結(jié)點。 森林的后序遍歷按順序后序遍歷森林中的每一棵樹。另外，請注意，樹和森林的先序遍歷等價于它轉(zhuǎn)換成的二叉樹的先序遍歷，樹和森林的后序遍歷等價于它轉(zhuǎn)換成的二叉樹的中序遍歷。6.6 哈夫曼樹6.6.1 基本術(shù)語1. 路徑和路徑長度在一棵樹中，從一個結(jié)點往下可以達(dá)到的孩子或子孫結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。2. 結(jié)點的權(quán)及帶權(quán)路徑長度若將樹中