第6章樹和二叉樹

第6章樹和二叉樹16.1樹6.1.1樹的定義

樹是由n（n≥0）個(gè)元素構(gòu)成的有限集合。n=0稱為空樹；n>0稱為非空樹。任意一顆非空樹，都滿足：（1）有且僅有一個(gè)稱為根的結(jié)點(diǎn)，沒有前驅(qū)結(jié)點(diǎn)。（2）其余結(jié)點(diǎn)被分成m（m≥0）個(gè)互不相交的有限集T1，T2，…，Tm，其中每一個(gè)集合Ti（1≤i≤m）又是一顆樹，稱為根的子樹。26.1.1樹的定義結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有子樹的個(gè)數(shù)稱為結(jié)點(diǎ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)。也稱非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)以外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)：樹中一個(gè)結(jié)點(diǎ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)。結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)，稱為結(jié)點(diǎn)的祖先。36.1.1樹的定義結(jié)點(diǎn)的子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。結(jié)點(diǎn)的層次：樹是一種層次結(jié)構(gòu)，樹中的每個(gè)結(jié)點(diǎn)都處于某個(gè)層次上。樹的深度：樹中所有結(jié)點(diǎn)的層次的最大值稱為樹的深度。也稱為樹的高度。有序樹：如果樹中各結(jié)點(diǎn)的子樹是按照從左到右有序排列的，即各子樹的位置不能交換，這樣的樹稱為有序樹。無序樹：如果樹中各結(jié)點(diǎn)的子樹的排列是無序的，稱為無序樹。森林：m（m≥0）顆互不相交的樹的集合稱為森林。46.1.2樹的表示方法1.樹形表示法以圓圈表示結(jié)點(diǎn)，以連線表示結(jié)點(diǎn)之間的關(guān)系。2.嵌套集合表示法也稱為文氏圖表示法。用圓圈表示樹、子樹和結(jié)點(diǎn)，并用包含關(guān)系表示結(jié)點(diǎn)間的關(guān)系。3.凹入表示法結(jié)點(diǎn)逐層縮進(jìn)，即孩子結(jié)點(diǎn)縮進(jìn)于雙親結(jié)點(diǎn)。4.廣義表表示法用廣義表表示樹。用名稱表示樹的根，括號(hào)內(nèi)表示子樹。5線性結(jié)構(gòu)和樹結(jié)構(gòu)的比較線性結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素：無前驅(qū)最后一個(gè)數(shù)據(jù)元素：無后繼其他元素：一個(gè)前驅(qū)一個(gè)后繼樹結(jié)構(gòu)根結(jié)點(diǎn)（只有一個(gè)）：無雙親葉子結(jié)點(diǎn)（可以有多個(gè)）：無孩子其他結(jié)點(diǎn)：一個(gè)雙親多個(gè)孩子66.1.3樹的抽象數(shù)據(jù)類型ADTTree數(shù)據(jù)元素集合：具有相同性質(zhì)的稱為結(jié)點(diǎn)的數(shù)據(jù)元素的一個(gè)有限序列。其中一個(gè)稱為根結(jié)點(diǎn)，其它形成m顆互不相交的子樹?；静僮鳎簶?gòu)造樹(CreateTree)：構(gòu)造一顆樹求樹根(Root)：返回樹的根取值(Value)：獲取指定結(jié)點(diǎn)的值賦值(Assign)：將值賦給指定的結(jié)點(diǎn)雙親(Parent)：獲取指定結(jié)點(diǎn)的雙親左孩子(LeftChild)：獲取指定結(jié)點(diǎn)的左孩子右兄弟(RightSibling)：獲取指定結(jié)點(diǎn)的右兄弟插入子樹(InsertChild)：在指定的結(jié)點(diǎn)下插入第i顆子樹刪除子樹(DeleteChild)：刪除指定結(jié)點(diǎn)的第i顆子樹樹的深度(TreeDepth)：返回樹的深度遍歷樹(TraverseTree)：訪問樹中的每一個(gè)元素，且僅訪問一次76.1.4樹的存儲(chǔ)結(jié)構(gòu)1.雙親表示法雙親表示法就是以一組地址連續(xù)的存儲(chǔ)空間存儲(chǔ)樹的結(jié)點(diǎn)。其中，每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和指針域。數(shù)據(jù)域存放數(shù)據(jù)元素的值，指針域存放一個(gè)指向其雙親的指針。86.1.4樹的存儲(chǔ)結(jié)構(gòu)2.孩子表示法在結(jié)點(diǎn)中設(shè)置指向每個(gè)孩子的指針域，利用指針指向該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)。大多采用按樹的度設(shè)置結(jié)點(diǎn)的指針域的個(gè)數(shù)。96.1.4樹的存儲(chǔ)結(jié)構(gòu)3.孩子兄弟表示法在結(jié)點(diǎn)中設(shè)置兩個(gè)指針域，一個(gè)指針域指向該結(jié)點(diǎn)的第一個(gè)孩子，另一個(gè)指針域指向其右兄弟。106.2二叉樹6.2.1二叉樹的定義

二叉樹是n（n≥0）個(gè)結(jié)點(diǎn)構(gòu)成的有限集合。當(dāng)n=0時(shí)，它是一顆空二叉樹；當(dāng)n>0時(shí)，它由一個(gè)根結(jié)點(diǎn)和兩顆互不相交的、分別稱作左子樹和右子樹的二叉樹構(gòu)成。（1）二叉樹的度只能是0、1或2；（2）二叉樹是有序樹，它的左、右子樹是有次序的，即使只有一顆子樹也要區(qū)分是左子樹還是右子樹。

11兩種特殊形態(tài)的二叉樹（1）滿二叉樹如果二叉樹的所有分支結(jié)點(diǎn)都有左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在二叉樹的最下一層，則稱這樣的二叉樹為滿二叉樹。

（2）完全二叉樹在一顆具有n個(gè)結(jié)點(diǎn)的二叉樹中，如果它的結(jié)構(gòu)與滿二叉樹的前n個(gè)結(jié)點(diǎn)的結(jié)構(gòu)相同，則稱這樣的二叉樹為完全二叉樹。

126.2.1二叉樹的定義【例6-3】所示的4顆二叉樹中，哪顆是完全二叉樹？133.二叉樹的抽象數(shù)據(jù)類型ADTBiTree數(shù)據(jù)元素集合：具有相同性質(zhì)的稱為結(jié)點(diǎn)的數(shù)據(jù)元素的一個(gè)有限序列。其中一個(gè)稱為根結(jié)點(diǎn)，其它形成兩顆互不相交的、分別稱作左子樹和右子樹的二叉樹基本操作：構(gòu)造二叉樹(CreateBiTree)：構(gòu)造一顆二叉樹求樹根(Root)：返回二叉樹的根取值(Value)：獲取指定結(jié)點(diǎn)的值賦值(Assign)：將值賦給指定的結(jié)點(diǎn)雙親(Parent)：獲取指定結(jié)點(diǎn)的雙親左孩子(LeftChild)：獲取指定結(jié)點(diǎn)的左孩子左兄弟(LeftSibling)：獲取指定結(jié)點(diǎn)的左兄弟插入子樹(InsertChild)：在指定的結(jié)點(diǎn)下插入第i顆子樹刪除子樹(DeleteChild)：刪除指定結(jié)點(diǎn)的第i顆子樹遍歷樹(TraverseBiTree)：遍歷的次序主要有先序遍歷、中序遍歷、后序遍歷和層次遍歷四種146.2.2二叉樹的性質(zhì)性質(zhì)1非空二叉樹的第i（i≥1）層上最多有2i-1個(gè)結(jié)點(diǎn)

證明：使用歸納法。當(dāng)i=1（第1層）時(shí)，非空二叉樹只有一個(gè)根結(jié)點(diǎn)，即21-1=1，命題成立。假定對(duì)于第i-1層命題成立，即非空二叉樹第i-1層最多有2i-2個(gè)結(jié)點(diǎn)。由二叉樹的定義可知，二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，因此，第i層的結(jié)點(diǎn)總數(shù)最多是第i-1層結(jié)點(diǎn)數(shù)的2倍，即第i層最多有2×2i-2=2i-1個(gè)結(jié)點(diǎn)。命題得證。156.2.2二叉樹的性質(zhì)性質(zhì)2深度為h（h≥1）的非空二叉樹最多有2h-1個(gè)結(jié)點(diǎn)。證明：只有滿二叉樹才能出現(xiàn)最多結(jié)點(diǎn)個(gè)數(shù)，即二叉樹的每層結(jié)點(diǎn)數(shù)都應(yīng)該達(dá)到最大結(jié)點(diǎn)數(shù)2i-1（由性質(zhì)1得到）。因此，深度為h的二叉樹所具有的最多結(jié)點(diǎn)數(shù)為166.2.2二叉樹的性質(zhì)性質(zhì)3在任意非空二叉樹中，若度為0（葉子結(jié)點(diǎn)）的結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則關(guān)系n0=n2+1成立。證明：

設(shè)度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，則二叉樹的結(jié)點(diǎn)總數(shù)為 n=n0+n1+n2 (6-1)

除了根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)都有一個(gè)直接前驅(qū)，即每個(gè)結(jié)點(diǎn)都有一個(gè)分支與之相連，因此，具有n個(gè)結(jié)點(diǎn)的二叉樹的分支總數(shù)為

B=n-1 （6-2）這些分支來自于度為1和度為2的結(jié)點(diǎn)，因此，分支總數(shù)為

B=n1+2×n2 （6-3）把式（6-1）代入式（6-2），并使之等于式（6-3），得到

n0=n2+1176.2.2二叉樹的性質(zhì)性質(zhì)4具有n（n>0）個(gè)結(jié)點(diǎn)的完全二叉樹的深度h=證明：根據(jù)完全二叉樹的定義可知深度為h-1層及以上的結(jié)點(diǎn)構(gòu)成滿二叉樹，因此由性質(zhì)2得深度為h的完全二叉樹滿足

n>2h-1-1和n≤2h-1整理后得到

2h-1≤n<2h不等式兩邊取對(duì)數(shù)，得

h-1≤log2n<h由于h為正整數(shù)，因此

h=186.2.2二叉樹的性質(zhì)性質(zhì)5

對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從第1層、第2層、…、第層的次序，且每層從左到右的次序?qū)Y(jié)點(diǎn)進(jìn)行編號(hào)，則編號(hào)為i的結(jié)點(diǎn)有以下性質(zhì)：（1）若i>1，則編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為；當(dāng)i=1時(shí)，編號(hào)為i的結(jié)點(diǎn)為二叉樹的根結(jié)點(diǎn)，沒有雙親結(jié)點(diǎn)。（2）若2i≤n，則編號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為2i；若2i>n，則編號(hào)為i的結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)。（3）若2i+1≤n，則編號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的編號(hào)為2i+1；若2i+1>n，則編號(hào)為i的結(jié)點(diǎn)沒有右孩子結(jié)點(diǎn)。196.2.2二叉樹的性質(zhì)【例6-4】已知一顆完全二叉樹的第6層有7個(gè)結(jié)點(diǎn)，則該完全二叉樹總共有多少個(gè)結(jié)點(diǎn)？度為1的結(jié)點(diǎn)有多少個(gè)？度為0的結(jié)點(diǎn)有多少個(gè)？編號(hào)最大的非葉結(jié)點(diǎn)是哪一個(gè)？編號(hào)最小的葉結(jié)點(diǎn)是哪一個(gè)？解：深度為5的滿二叉樹：25-1=31，第6層7個(gè)結(jié)點(diǎn)，總結(jié)點(diǎn)數(shù)為38。第6層的7個(gè)結(jié)點(diǎn)會(huì)出現(xiàn)一個(gè)度為1的結(jié)點(diǎn)。第6層的7個(gè)結(jié)點(diǎn)是度為0的結(jié)點(diǎn)，除第5層上有4個(gè)結(jié)點(diǎn)之外的結(jié)點(diǎn)均是度為0的結(jié)點(diǎn)，總共有25-1-4=12個(gè)。度為0的結(jié)點(diǎn)有7+12=19個(gè)。編號(hào)最大的非葉結(jié)點(diǎn)就是第5層上的4個(gè)雙親結(jié)點(diǎn)中編號(hào)最大的結(jié)點(diǎn)，即編號(hào)為31-4=27的結(jié)點(diǎn)。編號(hào)最小的葉結(jié)點(diǎn)是編號(hào)最大的非葉結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，因此是編號(hào)為28的結(jié)點(diǎn)。206.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)1.二叉樹的順序存儲(chǔ)結(jié)構(gòu)

是用一組地址連續(xù)的存儲(chǔ)單元依次存放二叉樹的數(shù)據(jù)元素。根據(jù)二叉樹的性質(zhì)5，完全二叉樹中結(jié)點(diǎn)編號(hào)之間的關(guān)系反映了結(jié)點(diǎn)之間的邏輯關(guān)系。非完全二叉樹的順序存儲(chǔ)：為非完全二叉樹增添一些實(shí)際上不存在的“空結(jié)點(diǎn)”，從而轉(zhuǎn)換成完全二叉樹。然后再順序存儲(chǔ)。216.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)2.二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1）二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)：數(shù)據(jù)域、左孩子指針域和右孩子指針域。226.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)二叉鏈表的存儲(chǔ)結(jié)構(gòu)：typedef

structNode{ DataTypedata; /*數(shù)據(jù)域*/ structNode*left;/*左孩子指針域*/ structNode*right;/*右孩子指針域*/}BTNode,*PBTNode,*BiTreeLink;（2）三叉鏈表結(jié)點(diǎn)結(jié)構(gòu)：

parent域存放指向結(jié)點(diǎn)雙親的指針。236.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)3.二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的操作

（1）創(chuàng)建二叉樹

BiTreeLink

CreateBiTree(char*nodes,int

pos,intnum){

PBTNodep;

if(nodes[pos]==''||pos>num)returnNULL;/*遞歸結(jié)束條件*/ p=(PBTNode)malloc(sizeof(BTNode));/*建立根結(jié)點(diǎn)*/

if(!p){printf("初始化鏈表錯(cuò)誤！\n");return0;} p->data=nodes[pos]; p->left=CreateBiTree(nodes,2*pos,num); /*遞歸建立左子樹*/ p->right=CreateBiTree(nodes,2*pos+1,num);/*遞歸建立右子樹*/ returnp;}246.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)（3）插入右孩子PBTNode

InsertRight(PBTNode

r,DataTypex){

PBTNodep;

if(!r)returnNULL; p=(PBTNode)malloc(sizeof(BTNode));/*生成新結(jié)點(diǎn)*/ p->data=x; p->left=NULL;/*若結(jié)點(diǎn)原來有右孩子，則把它作為新插入結(jié)點(diǎn)的右孩子*/

p->right=r->right; r->right=p;/*將x插入作為r的右孩子*/ returnp;}256.2.4二叉樹的遍歷（4）刪除右子樹

voidDeleteRight(PBTNoder){

if(!r)return;

ReleaseTree(&r->right); r->right=NULL;}（5）銷毀子樹

voidReleaseTree(PBTNode*r){ if(*r){

ReleaseTree(&(*r)->left); /*銷毀左子樹*/

ReleaseTree(&(*r)->right); /*銷毀右子樹*/ free(*r); }} /*銷毀根*/ 266.2.4二叉樹的遍歷二叉樹的遍歷是指按一定次序訪問二叉樹中的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅被訪問一次。1.前序遍歷若二叉樹非空，則按以下次序進(jìn)行遍歷：（1）訪問根結(jié)點(diǎn)；（2）前序遍歷根結(jié)點(diǎn)的左子樹；（3）前序遍歷根結(jié)點(diǎn)的右子樹。voidPreOrder(BiTreeLinkr){

if(r!=NULL){

printf("%c",r->data); /*訪問根*/

PreOrder(r->left); /*前序遍歷左子樹*/

PreOrder(r->right);}} /*前序遍歷右子樹*/ 276.2.4二叉樹的遍歷2.中序遍歷若二叉樹非空，則按以下次序進(jìn)行遍歷：（1）中序遍歷根結(jié)點(diǎn)的左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷根結(jié)點(diǎn)的右子樹。voidInOrder(BiTreeLinkr){

if(r!=NULL){

InOrder(r->left); /*中序遍歷左子樹*/

printf("%c",r->data); /*訪問根*/

InOrder(r->right); /*中序遍歷右子樹*/ }}286.2.4二叉樹的遍歷3.后序遍歷若二叉樹非空，則按以下次序進(jìn)行遍歷：（1）后序遍歷根結(jié)點(diǎn)的左子樹；（2）后序遍歷根結(jié)點(diǎn)的右子樹；（3）訪問根結(jié)點(diǎn)。voidPostOrder(BiTreeLinkr){

if(r!=NULL){

PostOrder(r->left); /*后序遍歷左子樹*/

PostOrder(r->right); /*后序遍歷右子樹*/

printf("%c",r->data); /*訪問根*/ }}296.2.4二叉樹的遍歷【例6-7】已知一顆二叉樹的中序遍歷序列和后序遍歷序列分別為DBAEGCHFI和DBGEHIFCA，試畫出這顆二叉樹。思路：由任意一個(gè)遍歷序列均不能惟一確定一顆二叉樹，只有知道中序和后序或中序和前序遍歷序列才能惟一確定一顆二叉樹。確定方法：由前序或后序遍歷序列確定樹或子樹的根，再由中序遍歷序列確定根的左子樹和右子樹306.2.4二叉樹的遍歷4.二叉樹遍歷的應(yīng)用（1）統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)

二叉樹結(jié)點(diǎn)的個(gè)數(shù)=左子樹中所含結(jié)點(diǎn)的個(gè)數(shù)+右子樹所含結(jié)點(diǎn)的個(gè)數(shù)+根結(jié)點(diǎn)。int

BiTreeCount(BiTreeLinkr){

if(r==NULL)return0;/*空二叉樹的結(jié)點(diǎn)個(gè)數(shù)為0*/ else returnBiTreeCount(r->left)+BiTreeCount(r->right)+1;}316.2.4二叉樹的遍歷（2）求二叉樹的深度

二叉樹的深度=左子樹的深度>右子樹的深度?左子樹的深度+1：右子樹的深度右子樹的深度+1。

int

BiTreeDepth(BiTreeLinkr){

int

ld,rd;

if(r==NULL) return0; else{ ld=BiTreeDepth(r->left); rd=BiTreeDepth(r->right); returnld>rd?ld+1:rd+1; }}326.2.4二叉樹的遍歷【例6-9】仿照算法6-12，編寫一個(gè)算法統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的數(shù)目。

思路：葉子結(jié)點(diǎn)數(shù)=左子樹葉子結(jié)點(diǎn)數(shù)+右子樹葉子結(jié)點(diǎn)數(shù)。int

LeafCount(BiTreeLinkr){

if(!r)return0;/*空樹葉子個(gè)數(shù)為0*/ elseif(!r->left&&!r->right)/*只有根結(jié)點(diǎn)，葉子數(shù)為1*/ return1; else returnLeafCount(r->left)+LeafCount(r->right);}

336.4森林6.4.1樹、森林與二叉樹的轉(zhuǎn)換

樹、森林與二叉樹之間有著一一對(duì)應(yīng)關(guān)系。1.樹與二叉樹之間的相互轉(zhuǎn)換

任何一顆樹都可以用孩子兄弟鏈表表示出來，而任何一顆二叉樹都可以用二叉鏈表表示出來。

346.4.1樹、森林與二叉樹的轉(zhuǎn)換（1）樹轉(zhuǎn)換為二叉樹方法將樹中具有同一雙親的兄弟結(jié)點(diǎn)之間用線段連接起來；保留雙親與第一個(gè)孩子之間的連線，刪除其他孩子與雙親之間的連線；將兄弟之間的連線順時(shí)針旋轉(zhuǎn)45°?！纠?-11】將樹轉(zhuǎn)換為二叉樹。356.4.1樹、森林與二叉樹的轉(zhuǎn)換（2）二叉樹轉(zhuǎn)換為樹方法若二叉樹某結(jié)點(diǎn)是其雙親的左孩子，則把以該結(jié)點(diǎn)為根的右子樹中的所有右孩子與該結(jié)點(diǎn)的雙親之間用線段連接起來；刪除這些右孩子與其他結(jié)點(diǎn)之間的連線；整理連線，使各結(jié)點(diǎn)按層次排列?！纠?-12】將二叉樹轉(zhuǎn)換為樹。366.4.1樹、森林與二叉樹的轉(zhuǎn)換2.森林與二叉樹之間的相互轉(zhuǎn)換

（1）森林轉(zhuǎn)換成二叉樹方法將森林中的所有樹均轉(zhuǎn)換為二叉樹；將森林中第一顆樹轉(zhuǎn)換成的二叉樹作為轉(zhuǎn)換后的二叉樹的根和左子樹；將森林中第二顆樹轉(zhuǎn)換成的二叉樹作為轉(zhuǎn)換后的二叉樹的右子樹添加到轉(zhuǎn)換后的二叉樹上；將森林中第三顆樹轉(zhuǎn)換成的二叉樹作為轉(zhuǎn)換后的二叉樹的右子樹的右子樹添加到轉(zhuǎn)換后的二叉樹上；依此類推，直至把所有二叉樹均添加到轉(zhuǎn)換后的二叉樹上為止。376.4.1樹、森林與二叉樹的轉(zhuǎn)換【例6-13】將森林轉(zhuǎn)換為二叉樹。386.4.1樹、森林與二叉樹的轉(zhuǎn)換（2）二叉樹轉(zhuǎn)換成森林方法將二叉樹的根及左子樹轉(zhuǎn)換成樹，作為森林第一顆樹；將剩下的二叉樹的根及左子樹轉(zhuǎn)換成樹，作為森林的第二顆樹；以此類推，直至把二叉樹轉(zhuǎn)換完為止?！纠?-14】將二叉樹轉(zhuǎn)換為森林。

396.4.2樹和森林的遍歷1.樹的遍歷按一定次序訪問樹中的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅被訪問一次。（1）先根遍歷若樹不空，則訪問根結(jié)點(diǎn)；按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一顆子樹。（2）后根遍歷若樹不空，則按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一顆子樹。訪問根結(jié)點(diǎn)；406.4.2樹和森林的遍歷2.森林的遍歷（1）先序遍歷森林若森林不空，則訪問森林中第一顆樹的根結(jié)點(diǎn)；先序遍歷第一顆樹中根結(jié)點(diǎn)的子樹森林；先序遍歷除去第一顆樹之后剩余的樹構(gòu)成的森林。（2）中序遍歷森林若森林不空，則中序遍歷森林中第一顆樹中根結(jié)點(diǎn)的子樹森林；訪問第一顆樹的根結(jié)點(diǎn)；中序遍歷除去第一顆樹之后剩余的樹構(gòu)成的森林。416.4.2樹和森林的遍歷3.二叉樹、樹和森林遍歷的對(duì)應(yīng)關(guān)系樹森林二叉樹先根遍歷先序遍歷先序遍歷后根遍歷中序遍歷中序遍歷426.5哈夫曼樹及其應(yīng)用在一顆二叉樹中，從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支序列構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。二叉樹中兩個(gè)結(jié)點(diǎn)之間的路徑上的分支數(shù)目稱作結(jié)點(diǎn)間的路徑長度。從二叉樹的根結(jié)點(diǎn)到每一個(gè)結(jié)點(diǎn)的路徑長度之和稱作樹的路徑長度。若給二叉樹的葉結(jié)點(diǎn)賦以權(quán)值，則定義從二叉樹的根結(jié)點(diǎn)到二叉樹中所有葉結(jié)點(diǎn)的路徑長度與相應(yīng)葉結(jié)點(diǎn)權(quán)值的乘積之和為二叉樹的帶權(quán)路徑長度，記作

其中，wi為第i個(gè)葉結(jié)點(diǎn)的權(quán)值，li為第i個(gè)葉結(jié)點(diǎn)的路徑長度，n為葉結(jié)點(diǎn)數(shù)。436.5.1哈夫曼樹給定一組帶有權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出許多帶權(quán)路徑長度不同的二叉樹，其中帶權(quán)路徑長度最小的二叉樹稱作哈夫曼樹或最優(yōu)二叉樹。WPL=6×3+5×3+1×2+2×2=39WPL=6×1+5×2+1×3+2×3=25446.5.1哈夫曼樹2.哈夫曼樹構(gòu)造算法（1）用給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)造n顆只有根結(jié)點(diǎn)的二叉樹，形成一個(gè)二叉樹森林F={T1,T2,…,Tn}；（2）在二叉樹森林F中，選出根的權(quán)值最小的兩