16.1樹的定義與基本術語第6章樹和二叉樹6.2二叉樹6.3二叉樹的遍歷與線索化6.4樹、森林與二叉樹的關系6.5哈夫曼樹及其應用6.6總結與提高26.1樹的定義與基本術語第6章樹和二叉樹樹：是n(n≥0)個結點的有限集合T。

當n=0時稱為空樹；

當n>0時，該集合滿足如下條件：其中必有一個稱為根(root)的特定結點，它沒有直接前驅，但有零個或多個直接后繼。(2)其余n-1個結點可以劃分成m(m≥0)個互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結點有且僅有一個直接前驅，但有零個或多個直接后繼。36.1樹的定義與基本術語例如：第6章樹和二叉樹ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2根46.1樹的定義與基本術語表示方法：第6章樹和二叉樹①樹型表示bacghdefij56.1樹的定義與基本術語表示方法：第6章樹和二叉樹②文氏圖表示ijdfghabce66.1樹的定義與基本術語表示方法：第6章樹和二叉樹③凹入表示abdeijfcgh76.1樹的定義與基本術語表示方法：第6章樹和二叉樹④嵌套括號表示a(b(d,e(i,j),c(g,h)))86.1樹的定義與基本術語第6章樹和二叉樹基本術語①結點：數據元素+若干指向子樹的分支②結點的度:分支的個數③樹的度:樹中所有結點的度的最大值④葉子結點:度為零的結點⑤分支結點:度大于零的結點⑥(從根到結點的)路徑：由從根到該結點所經分支和結點構成。ABCDEFGHIJMKL96.1樹的定義與基本術語第6章樹和二叉樹基本術語⑦孩子結點：一個結點的直接后繼⑧雙親結點:一個結點的直接前驅⑨兄弟結點:同一雙親結點的孩子結點之間互稱~。⑩堂兄弟、祖先結點、子孫結點結點的層次:根結點的層次為1，第i層的結點的子樹的根結點的層次為i+1樹的深度：樹中結點的層次的最大值ABCDEFGHIJMKL森林：是m（m≥0）棵互不相交的樹的集合106.1樹的定義與基本術語第6章樹和二叉樹基本操作①InitTree(Tree);②DestoryTree(Tree);③CreatTree(Tree);④TreeEmpty(Tree);⑤Root(Tree);⑥Parent(Tree,x);⑦FirstChild(Tree,x);⑧NextSibling(Tree,x);⑨InsertChild(Tree,p,Child);⑩DeleteChild(Tree,p,Child);返回116.2二叉樹第6章樹和二叉樹定義：滿足以上兩個條件的樹型結構為二叉樹。①每個結點的度都不大于2；②每個結點的孩子結點次序不能任意顛倒。二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABEFKLDHJM根結點左子樹右子樹126.2二叉樹第6章樹和二叉樹形態(tài)：空二叉樹只有根結點的二叉樹只有右子樹的二叉樹左、右子樹均非空的二叉樹只有左子樹的二叉樹5種136.2二叉樹第6章樹和二叉樹基本操作：①Initiate(bt);②Destory(bt);③Creat(bt);④Empty(bt);⑤Root(bt);⑥Parent(bt,x);⑦LeftChild(bt,x);⑧RithtChild(bt,x);⑨Traverse(bt);⑩Clear(bt);146.2二叉樹第6章樹和二叉樹重要性質：①在二叉樹的第i

層上至多有2i-1

個結點。用歸納法證明：Ⅰ.當i=1

層時，只有一個根結點：2i-1

=20

=1；Ⅱ.假設對所有的j，1≤j

i，命題成立；Ⅲ.二叉樹上每個結點至多有兩棵子樹，則第i層的結點數=2i-2

2=2i-1

。156.2二叉樹第6章樹和二叉樹重要性質：②深度為k的二叉樹上至多含2k-1個結點(k≥1)。證明：基于上一條性質，深度為k的二叉樹上的結點數至多為20+21++2k-1=2k-1166.2二叉樹第6章樹和二叉樹重要性質：③對任何一棵二叉樹，若它含有n0

個葉子結點、

n2

個度為

2

的結點，則必存在關系式：

n0=n2+1。

證明：設二叉樹上結點總數n=n0+n1+n2又二叉樹上分支總數b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1176.2二叉樹第6章樹和二叉樹特殊的二叉樹滿二叉樹完全二叉樹深度為k且含有2k-1個結點的二叉樹。樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。123456789101112131415滿二叉樹abcdefghij完全二叉樹關系：滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。186.2二叉樹第6章樹和二叉樹重要性質：④具有n個結點的完全二叉樹的深度為

log2n

+1。

證明：設完全二叉樹的深度為k則根據第二條性質得2k-1-1<n≤2k-1則2k-1

≤n<2k即

k-1≤log2n<k因為k只能是整數，因此，k=log2n+1。196.2二叉樹第6章樹和二叉樹重要性質：⑤若對含n個結點的完全二叉樹從上到下且從左至右進行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結點：(1)若i=1，則該結點是二叉樹的根，無雙親，否則，編號為

i/2

的結點為其雙親結點；(2)若2i>n，則該結點無左孩子，

否則，編號為2i

的結點為其左孩子結點；(3)若2i+1>n，則該結點無右孩子結點，

否則，編號為2i+1

的結點為其右孩子結點。206.2二叉樹第6章樹和二叉樹存儲結構：①順序存儲結構；

②

鏈式存儲結構。

二叉樹的結構是非線性的，每一個結點最多可有兩個后繼。21ABCDEFGHIJKL6.2二叉樹第6章樹和二叉樹存儲結構：①順序存儲結構是用一組連續(xù)的存儲單元來存放二叉樹的數據元素。ABCDEFGHIJKL一維數組bt[1..n]

A

B

DC

E

F123456789

1011121314ABCDEF2511437

可見，對于一般的二叉樹，按照完全二叉樹的編號來存儲，會造成空間的極大浪費。A^B^^^C^^^^^^^D單支樹就是一個極端情況：13715ABCD單支樹1371524root∧∧6.2二叉樹第6章樹和二叉樹存儲結構：②

鏈式存儲結構：二叉鏈表結點結構:lchildrchilddataABCDEFGABCD∧EF∧G∧∧∧∧typedefstructNode{

DataType

data;structNode*lchild;structNode*rchild;}BiTNode,*BiTree;256.2二叉樹第6章樹和二叉樹存儲結構：②

鏈式存儲結構：三叉鏈表結點結構:lchildrchilddataABCDEFGparent∧rootABCD∧EF∧G∧∧∧∧∧∧返回266.3二叉樹的遍歷與線索化第6章樹和二叉樹遍歷二叉樹：順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次。“遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。二叉樹是非線性結構，每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。276.3二叉樹的遍歷與線索化第6章樹和二叉樹“二叉樹”由三個基本單元組成：根結點、左子樹和右子樹。若能依次遍歷這三部分，就遍歷了整個二叉樹。

設用L、D、R分別表示遍歷左子樹、訪問根結點、遍歷右子樹，對“二叉樹”而言，可以有6種搜索路徑：①DLR②DRL③LDR④RDL⑤LRD⑥RLD先左后右先右后左√286.3二叉樹的遍歷與線索化第6章樹和二叉樹先（根）序的遍歷算法：若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。ABCDEFGABDGCEF先序遍歷結果：ABDGCEF296.3二叉樹的遍歷與線索化第6章樹和二叉樹中（根）序的遍歷算法：若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。ABCDEFGABDGCEF中序遍歷結果：ABDGCEF306.3二叉樹的遍歷與線索化第6章樹和二叉樹后（根）序的遍歷算法：若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。ABCDEFGABDGCEF后序遍歷結果：ABDGCEF先序遍歷：A、B、D、F、G、C、E、H。ABCDFGEH例如:中序遍歷：B、F、D、G、A、C、E、H。后序遍歷：F、G、D、B、H、E、C、A。abcdefghij又如:先序遍歷:abdhiejcfg中序遍歷:hdibjeafcg后序遍歷:hidjebfgca336.3二叉樹的遍歷與線索化第6章樹和二叉樹舉例：-+/a*ef-bcd先序：-+a*b-cd/ef中序：a+b*c-d-e/f后序：abcd-*+ef/-前綴式（波蘭式）中綴式后綴式（逆波蘭式）3434ABCDEFGHK先序序列:ABCDEFGHK中序序列:BDCAHGKFE后序序列:DCBHKGFEA6.3二叉樹的遍歷與線索化第6章樹和二叉樹由遍歷序列確定二叉樹356.3二叉樹的遍歷與線索化第6章樹和二叉樹由遍歷序列確定二叉樹由先序和中序序列恢復二叉樹二叉樹的先序序列左子樹右子樹根二叉樹的中序序列左子樹右子樹根366.3二叉樹的遍歷與線索化第6章樹和二叉樹由遍歷序列確定二叉樹由先序和中序序列恢復二叉樹舉例先序序列：ABCDEFG中序序列：CBDAEGFAA左子樹右子樹ABBBCCCDDDEEEFFFGGG376.3二叉樹的遍歷與線索化第6章樹和二叉樹具體的遍歷算法（以二叉鏈表為存儲結構）：①先序遍歷算法voidPreOrder(BiTreeroot){ if(root!=NULL){Visit(root->data);/*訪問根結點*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/ }}386.3二叉樹的遍歷與線索化第6章樹和二叉樹具體的遍歷算法（以二叉鏈表為存儲結構）：②中序遍歷算法voidInOrder(BiTreeroot){ if(root!=NULL){

InOrder(root->LChild);/*中序遍歷左子樹*/Visit(root->data);/*訪問根結點*/

InOrder(root->RChild);/*中序遍歷右子樹*/ }}396.3二叉樹的遍歷與線索化第6章樹和二叉樹具體的遍歷算法（以二叉鏈表為存儲結構）：③后序遍歷算法voidPostOrder(BiTreeroot){ if(root!=NULL){

PostOrder(root->LChild);/*后序遍歷左子樹*/

PostOrder(root->RChild);/*后序遍歷右子樹*/Visit(root->data);/*訪問根結點*/}}406.3二叉樹的遍歷與線索化第6章樹和二叉樹遍歷算法應用：遍歷算法將走遍二叉樹中的每一個結點，故輸出二叉樹中結點并無次序要求，因此可用任一種算法來完成。voidPreOrder(BiTreeroot){ if(root!=NULL) {

printf(root->data);/*輸出根結點*/ PreOrder(root->LChild);/*先序遍歷左子樹*/ PreOrder(root->RChild);/*先序遍歷右子樹*/ }}①輸出二叉樹中的結點416.3二叉樹的遍歷與線索化第6章樹和二叉樹遍歷算法應用：條件：判斷結點既沒有左孩子，又沒有右孩子時，則輸出該結點。voidPreOrderLeaf(BiTreeroot){if(root!=NULL){

if(root->LChild==NULL&&root->RChild==NULL)

printf(root->data);/*輸出葉結點*/

PreOrderLeaf(root->LChild);/*先序遍歷左子樹*/

PreOrderLeaf(root->RChild);/*先序遍歷右子樹*/}}②輸出二叉樹中的葉子結點426.3二叉樹的遍歷與線索化第6章樹和二叉樹遍歷算法應用：/*LeafCount保存葉子結點數目的全局變量,調用之前初始化值為0*/voidleaf(BiTreeroot){if(root!=NULL){leaf(root->LChild);leaf(root->RChild);

if(root->LChild==NULL&&root->RChild==NULL)

LeafCount++;}}③統計葉子結點數目方法1：436.3二叉樹的遍歷與線索化第6章樹和二叉樹遍歷算法應用：/*采用遞歸算法，如果是空樹，返回0；如果只有一個結點，返回1；否則為左右子樹的葉子結點數之和*/intleaf(BiTreeroot){intLeafCount;

if(root==NULL)

LeafCount=0;

elseif((root->LChild==NULL)&&(root->RChild==NULL))

LeafCount=1;

else

LeafCount=leaf(root->LChild)+leaf(root->RChild);

returnLeafCount;}③統計葉子結點數目方法2：446.3二叉樹的遍歷與線索化第6章樹和二叉樹④求二叉樹的高度設函數表示二叉樹bt的高度，則遞歸定義如下:

若bt為空，則高度為0

若bt非空，其高度應為其左右子樹高度的最大值加1遍歷算法應用：左子樹右子樹bthlhrHigh=max(hl+hr)+1intPostTreeDepth(BiTreebt){inthl,hr,max;if(bt!=NULL){

hl=PostTreeDepth(bt->LChild);hr=PostTreeDepth(bt->RChild);max=hl>hr?hl:hr;return(max+1);

}elsereturn(0);}456.3二叉樹的遍歷與線索化第6章樹和二叉樹⑤建立二叉鏈表方式存儲的二叉樹給定一棵二叉樹，可以得到它的遍歷序列；反過來，給定一個遍歷序列，也可以創(chuàng)建相應的二叉鏈表。在這里所說的遍歷序列是一種“擴展的遍歷序列”，通常用特定的元素表示空子樹。例如.擴展先序序列：AB□DF□□G□□C□E□H□□ABDFGCEH遍歷算法應用：

BiTreeCreateBiTree(){charch;BiTreebt;ch=getchar();if(ch=='□')return(NULL);

bt=(BiTree)malloc(sizeof(BiTNode));

bt->data=ch;

bt->Lchild=CreateBiTree();bt->Rchild=CreateBiTree();returnbt;}466.3二叉樹的遍歷與線索化第6章樹和二叉樹⑥按樹狀打印的二叉樹假設以二叉鏈表存儲的二叉樹中，每個結點所含數據元素均為單字母，要求實現如下圖的打印結果。遍歷算法應用：ABCDEF輸出CFAEDBvoidPrintTree(TreeNodebt,intnLayer){if(bt==NULL)return;PrintTree(bt->Rchild,nLayer+1);

for(inti=0;i<nLayer;i++)printf(“”);printf(“%c\n”,bt->data);PrintTree(bt->Lchild,nLayer+1);}476.3二叉樹的遍歷與線索化第6章樹和二叉樹①中序遍歷二叉樹的非遞歸算法基于棧的遞歸消除：從根開始，當前結點存在或棧不為空，重復如下操作：

1、當前結點進棧，走左子樹，直至左子樹為空；

2、退棧并訪問；

3、走右子樹；48voidInOrder（BiTreeroot）{InitStack(&S);p=root;while(p!=NULL||!IsEmpty(S)){if(p!=NULL)

/*根指針進棧，遍歷左子樹*/{Push(&S,p);p=p->LChild;}else

/*根指針退棧，訪問根結點，遍歷右子樹*/{Pop(&S,&p);Visit(p->data);

p=p->RChild;}}}時間復雜度：O(n)空間復雜度：O(k)第6章樹和二叉樹①中序遍歷二叉樹的非遞歸算法調用棧操作(s[m]表示棧，top表示棧頂指針)Voidinorder(BiTreeroot){do{while(p!=NULL)

{if(top>M)return(‘overflow’);top=top+1;s[top]=p;p=p->Lchild};/*進入左子樹*/if(top!=0){p=s[top];top=top-1;Visit(p->data);

/*訪問根結點*/

p=p->Rchild;}/*進入右子樹*/}while(p!=NULL||top!=0)}第6章樹和二叉樹①中序遍歷二叉樹的非遞歸算法直接實現棧操作算法思想：從根開始，當前結點存在或棧不為空，重復如下操作：

1、當前結點進棧，走左子樹，直至左子樹為空；

2、如果棧頂結點右子樹為空或右子樹已訪問過，則退棧并訪問剛退棧的棧頂結點；

3、否則，走右子樹；判定右子樹是否已訪問過有多種方法，在此采用：q記錄剛訪問過的結點，并判定棧頂結點右孩子是否為q。

后序遍歷非遞歸較上述算法的主要區(qū)別在于：要判定是否應訪問當前棧頂結點p。1.p無右孩子；2.p的右孩子已訪問過，此時應訪問棧頂結點p，除這兩種情況外，均應進入右子樹訪問。

第6章樹和二叉樹②后序遍歷二叉樹的非遞歸算法voidPostOrder（BiTreeroot）{BiTNode*p,*q；BiTreeS[stack-size]；

inttop=0;q=NULL;p=root;while(p!=NULL||top!=0){while(p!=NULL) {top=++;if(top>=stack-size)return(‘overflow’);s[top]=p;p=p->LChild;} if(top>0){p=s[top]; if((p->RChild==NULL)||(p->RChild==q)) {visit(p->data);

q=p;top--;p=NULL;}elsep=p->RChild;}}free(s);}

②后序遍歷二叉樹的非遞歸算法第6章樹和二叉樹526.3二叉樹的遍歷與線索化第6章樹和二叉樹基本概念線索二叉樹

以二叉鏈表作為二叉樹存儲結構時，只能找到結點的左、右孩子信息，不能直接得到結點在遍歷序列中的前驅和后繼信息。若要得到這些信息，可充分利用二叉鏈表中的空鏈域，將遍歷過程中結點的前驅、后繼信息保存下來。

在有n個結點的二叉鏈表中共有2n個鏈域，但只有n-1個有用的非空鏈域，其余n+1個鏈域是空的。LChildLtagDataRtagRChild536.3二叉樹的遍歷與線索化第6章樹和二叉樹結點結構：線索二叉樹Ltag=0LChild域指示結點的左孩子1LChild域指示結點的遍歷前驅Rtag=0RChild域指示結點的右孩子1RChild域指示結點的遍歷后繼546.3二叉樹的遍歷與線索化第6章樹和二叉樹在這種存儲結構中，指向前驅和后繼結點的指針叫做線索。線索二叉樹以這種結構組成的二叉鏈表作為二叉樹的存儲結構，叫做線索鏈表。對二叉樹以某種次序進行遍歷并且加上線索的過程叫做線索化。線索化了的二叉樹稱為線索二叉樹。556.3二叉樹的遍歷與線索化第6章樹和二叉樹線索化實質上是將二叉鏈表中的空指針域填上相應結點的遍歷前驅或后繼結點的地址，而前驅和后繼的地址只能在動態(tài)的遍歷過程中才能得到。因此線索化的過程是在遍歷過程中修改空指針域的過程。對二叉樹按照不同的遍歷次序進行線索化，可以得到不同的線索二叉樹（先序線索二叉樹、中序線索二叉樹和后序線索二叉樹）。二叉樹的線索化566.3二叉樹的遍歷與線索化第6章樹和二叉樹舉例：ABCDGEFH先序序列：ABDGCEHFABCDGEFHNULLABCDGEFH中序序列：DGBAEHCFNULLNULLABCDGEFH后序序列：GDBHEFCANULL576.3二叉樹的遍歷與線索化第6章樹和二叉樹在中序遍歷過程中修改結點的左、右指針域，以保存當前訪問結點的“前驅”和“后繼”信息。遍歷過程中，附設指針pre,并始終保持指針pre指向當前訪問的、指針p所指結點的前驅。建立線索鏈表586.3二叉樹的遍歷與線索化第6章樹和二叉樹中序線索化算法voidInthread(BiTreeroot){if(root!=NULL){Inthread(root->LChild);/*線索化左子樹*/

if(root->LChild==NULL){root->Ltag=1;root->LChild=pre;}if(pre!=NULL&&pre->RChild==NULL){pre->RChild=root;pre->Rtag=1;

}pre=root；

Inthread(root->RChild);/*線索化右子樹*/ }} 596.3二叉樹的遍歷與線索化第6章樹和二叉樹在線索二叉樹中找前驅、后繼結點（以中序為例）①在中序線索樹中找結點前驅：左子樹的“最右下端”結點BiTNode*InPre(BiTNode*p){if(p->Ltag==1)pre=p->LChild;else{

for(q=p->LChild;q->Rtag==0;q=q->RChild);pre=q;}return(pre);}606.3二叉樹的遍歷與線索化第6章樹和二叉樹在線索二叉樹中找前驅、后繼結點（以中序為例）②在中序線索樹中找結點后繼：右子樹的“最左下端”結點BiTNode*InNext(BiTNode*p){if(p->Rtag==1)Next=p->RChild;else{

for(q=p->RChild;q->Ltag==0;q=q->LChild);Next=q;}return(Next);}616.3二叉樹的遍歷與線索化第6章樹和二叉樹線索二叉樹的運算：插入（做某結點的右孩子）FprABCDEABCDEprF①

r->RChild=p->RChild;①②②p->RChild=r;③③r->LChilid=p;可交換順序626.3二叉樹的遍歷與線索化第6章樹和二叉樹線索二叉樹的運算：插入（做某結點的右孩子）FprABCDEGHrABCDEFpGH①s=p->RChild;while(s->Ltag==0)s=s->LChild;①s->LChild=r;②②r->LChild=p;③③r->RChild=p->RChild;④④p->RChild=r;636.3二叉樹的遍歷與線索化第6章樹和二叉樹線索二叉樹的運算：插入（做某結點的右孩子）算法voidInsNode(BiTNode*p,BiTNode*r){if(p->Rtag==1){

r->RChild=p->RChild;r->Rtag=1;p->RChilid=r;r->LChild=p;r->Ltag=1;}else{

s=p->RChild;while(s->Ltag==0)s=s->LChild;s->LChild=r;r->LChild=p;r->Ltag=1;r->RChild=p->RChild;r->Rtag=0;p->RChild=r;}}返回646.4樹、森林與二叉樹的關系第6章樹和二叉樹樹的三種存儲結構①雙親表示法dataparentABCDGEFparentdata結點序號0123456A-1B0C0D1E1F1G2656.4樹、森林與二叉樹的關系第6章樹和二叉樹樹的三種存儲結構①雙親表示法存儲結構#defineMAX100typedefstructTNode{DataTypedata;intparent;}TNode;typedefstruct{TNodetree[MAX];intnodenum;}ParentTree;666.4樹、森林與二叉樹的關系第6章樹和二叉樹樹的三種存儲結構②孩子表示法ABCDGEF0123456ABCDEFG12∧345∧6∧∧∧∧∧676.4樹、森林與二叉樹的關系第6章樹和二叉樹樹的三種存儲結構②孩子表示法存儲結構typedefstructChildNode{intChild;structChildNode*next;}ChildNode;typedefstruct{DataTypedata;ChildNode*FirstChild;}DataNode;typedefstruct{DataNodenodes[MAX];introot;intnum;}ChildTree;686.4樹、森林與二叉樹的關系第6章樹和二叉樹樹的三種存儲結構③孩子兄弟表示法data下一個兄弟結點第一個孩子結點ABCDGEFAB∧DC∧E∧FG∧∧∧∧∧696.4樹、森林與二叉樹的關系第6章樹和二叉樹樹的三種存儲結構③孩子兄弟表示法data下一個兄弟結點第一個孩子結點存儲結構typedefstructCSNode{DataTypedata;structCSNode*FirstChild;structCSNode*NextSibling;}CSNode,*CSTree;706.4樹、森林與二叉樹的關系第6章樹和二叉樹樹、森林與二叉樹的相互轉化①樹→二叉樹轉化規(guī)則：ⅰ.樹中所有相鄰兄弟之間加一條連線；ⅱ.對樹中每一個結點，只保留其與第一個孩子結點之間的連線，刪去其與其他孩子結點之間的連線；ⅲ.以樹的根結點位軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。716.4樹、森林與二叉樹的關系第6章樹和二叉樹樹、森林與二叉樹的相互轉化①樹→二叉樹例如：ABCDGEFHⅰ.樹中所有相鄰兄弟之間加一條連線；ⅱ.對樹中每一個結點，只保留其與第一個孩子結點之間的連線，刪去其與其他孩子結點之間的連線；×××ⅲ.以樹的根結點位軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。GABCDEFH726.4樹、森林與二叉樹的關系第6章樹和二叉樹樹、森林與二叉樹的相互轉化②森林→二叉樹ⅰ.將森林中的每棵樹轉化成相應的二叉樹；ⅱ.第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連接在一起后，所得到的二叉樹就是由森林轉換得到的二叉樹。

轉化規(guī)則：73GHIJ6.4樹、森林與二叉樹的關系第6章樹和二叉樹樹、森林與二叉樹的相互轉化②森林→二叉樹例如：ABCDEFⅰ.將森林中的每棵樹轉化成相應的二叉樹；EFGHIJABCDⅱ.第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連接在一起后，所得到的二叉樹就是由森林轉換得到的二叉樹。

ABCDEFGHIJ746.4樹、森林與二叉樹的關系第6章樹和二叉樹樹、森林與二叉樹的相互轉化③二叉樹→樹或森林ⅰ.若某結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子、…都與該結點的雙親結點用線連起來；ⅱ.刪掉原二叉樹中所有雙親結點與右孩子結點的連線；轉化規(guī)則：ⅲ.整理由前兩步所得到的樹或森林，使之結構層次分明。75GHIJ6.4樹、森林與二叉樹的關系第6章樹和二叉樹樹、森林與二叉樹的相互轉化③二叉樹→樹或森林例如：ABCDEFⅰ.若某結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子、…都與該結點的雙親結點用線連起來；ⅱ.刪掉原二叉樹中所有雙親結點與右孩子結點的連線；ABCDEFGHIJ×××××ⅲ.整理由前兩步所得到的樹或森林，使之結構層次分明。766.4樹、森林與二叉樹的關系第6章樹和二叉樹樹與森林的遍歷①樹的遍歷ⅰ.先根(次序)遍歷:ⅱ.后根(次序)遍歷:可有三條搜索路徑:ⅲ.按層次遍歷:若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。若樹不空，則自上而下自左至右訪問樹中每個結點。776.4樹、森林與二叉樹的關系第6章樹和二叉樹樹與森林的遍歷①樹的遍歷ⅰ.先根(次序)遍歷:ⅱ.后根(次序)遍歷:例如:ⅲ.按層次遍歷:若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。若樹不空，則自上而下自左至右訪問樹中每個結點。AEAABCDGEFHBECFHGDBHFGCDABCDEFGH786.4樹、森林與二叉樹的關系第6章樹和二叉樹樹與森林的遍歷①樹的遍歷voidRootFirst(CSTreeroot){if(root!=NULL){Visit(root->data);p=root->FirstChild;while(p!=NULL){RootFirst(p);p=p->NextSibling;}}}方法1：先根遍歷算法796.4樹、森林與二叉樹的關系第6章樹和二叉樹樹與森林的遍歷①樹的遍歷voidRootFirst(CSTreeroot){if(root!=NULL){Visit(root->data);RootFirst(root->FirstChild);RootFirst(root->NextSibling);}}方法2：先根遍歷算法806.4樹、森林與二叉樹的關系第6章樹和二叉樹樹與森林的遍歷②森林的遍歷若森林不空，則訪問森林中第一棵樹的根結點；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。先序遍歷：GHIJABCDEFABCDEFGHIJ依次從左至右對森林中的每一棵樹進行先根遍歷。816.4樹、森林與二叉樹的關系第6章樹和二叉樹樹與森林的遍歷②森林的遍歷若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結點；中序遍歷森林中(除第一棵樹之外)其

余樹構成的森林。中序遍歷：GHIJABCDEFBCDAFEHJIG依次從左至右對森林中的每一棵樹進行后根遍歷。826.4樹、森林與二叉樹的關系第6章樹和二叉樹樹與森林的遍歷②森林的遍歷若森林不空，則后序遍歷森林中第一棵樹的子樹森林；后序遍歷森林中(除第一棵樹之外)其余樹構成的森林；訪問森林中第一棵樹的根結點。后序遍歷：GHIJABCDEFDCBFJIHGEA836.4樹、森林與二叉樹的關系第6章樹和二叉樹樹的遍歷和二叉樹遍歷的對應關系先根遍歷后根遍歷先序遍歷中序遍歷樹森林二叉樹先序遍歷中序遍歷返回846.5哈夫曼樹及其應用第6章樹和二叉樹基本概念路徑：從一個結點到另一個結點之間的分支序列。路徑長度：從一個結點到另一個結點所經過的分支數目。結點的權：樹中每個結點所賦予的具有某種實際意義的實數。帶權路徑長度：從樹根到某一結點的路徑長度與該結點的權的乘積。樹的帶權路徑長度：樹中從根到所有葉子結點的各個帶權路徑長度之和。記為：WPL=Wi×Li∑i=1nABCD7524WPL=7×2+5×2+2×2+4×2=36856.5哈夫曼樹及其應用第6章樹和二叉樹例如：WPL25497+9×4+5×3+4×2+2×1=8927549WPL5+9）×2+（2=60=7×4=（7++4）×3什么樣的樹的帶權路徑長度WPL最??？

例如：給定一個權值序列{2,4,5,7}，可構造多種二叉樹的形態(tài):2457a75

4b25

42c7WPL(a)＝

36WPL(b)＝

46

WPL(c)＝35

其帶權路徑長度分別為：6.5哈夫曼樹及其應用第6章樹和二叉樹

在各種形態(tài)的含有n個葉子結點的二叉樹中,必存在一棵(幾棵)其帶權路徑長度值WPL最小的樹，被稱為“最優(yōu)二叉樹”。特征：在最優(yōu)二叉樹中沒有度數為1的結點(可用反證法證明);含n個葉子結點的最優(yōu)二叉樹的總結點數為2*n-1(依據二叉樹性質三)。

最優(yōu)二叉樹的構造方法最早由哈夫曼研究，所以又稱為“哈夫曼樹”。6.5哈夫曼樹及其應用第6章樹和二叉樹886.5哈夫曼樹及其應用第6章樹和二叉樹算法步驟：（以二叉樹為例）①根據給定的n個權值{w1,w2,…,wn}，構造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個帶權值為wi

的根結點，其左、右子樹為空樹；②在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；③從F中刪去這兩棵樹，同時加入剛生成的新樹；④重復(2)和(3)兩步，直至F中只含一棵樹為止。896.5哈夫曼樹及其應用第6章樹和二叉樹實例：已知權值W={5,6,2,9,7}，構造哈夫曼樹。①根據給定的n個權值{w1,w2,…,wn}，構造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個帶權值為wi

的根結點，其左、右子樹為空樹；56297②在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；F:√√527③從F中刪去這兩棵樹，同時加入剛生成的新樹；7②在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；√√6713③從F中刪去這兩棵樹，同時加入剛生成的新樹；13②在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；√√916③從F中刪去這兩棵樹，同時加入剛生成的新樹；16√√2929直至F中只含一棵樹為止。哈夫曼算法的實現

n個葉子結點的哈夫曼樹共有2n-1個結點,因此可用有2n-1個元素的數組來存儲哈夫曼樹,結點間的關系用游標表示，即采用靜態(tài)鏈表來存儲哈夫曼樹。

1、存儲結構

每個結點需包含其雙親結點信息和孩子結點信息，所以構成一個靜態(tài)三叉鏈表。

weightparentLchildRchild

權值雙親序號左孩子序號右孩子序號6.5哈夫曼樹及其應用第6章樹和二叉樹靜態(tài)三叉鏈表結構定義#defineN20#defineM2*N-1typedefstruct{intweight;intparent，Lchild，Rchild;}HTNode,HuffmanTree[M+1];

/*0號單元不用*/

靜態(tài)三叉鏈表數組中前n個元素存儲葉子結點，后n-1個元素存儲分支結點即不斷生成的新結點，最后一個元素存儲哈夫曼樹的根結點。

6.5哈夫曼樹及其應用第6章樹和二叉樹哈夫曼算法

初始化：先將n個元素都視為根結點，即孩子和雙親指針全置0。

建哈夫曼樹的過程是：反復在數組中選雙親為0(表示它們當前是樹根)且權值最小的兩結點,將它們作為左右孩子掛在新的結點之下,新結點權值為左右孩子權值之和。6.5哈夫曼樹及其應用第6章樹和二叉樹voidCrtHuffmanTree(HuffmanTreeht,intw[],intn){/*w存放已知的n個權值，構造哈夫曼樹ht*/}

m=2*n-1;for(i=1;i<=n;i++)ht[i]={w[i],0,0,0};for(i=n+1;i<=m;i++)ht[i]={0,0,0,0};for(i=n+1;i<=m;i++){select(ht,i-1,&s1,&s2);/*ht前i-1項選雙親為零且權最小的兩結點*/ht[s1].parent=i; ht[s2].parent=i;ht[i].Lchild=s1; ht[i].Rchild=s2;ht[i].weight=ht[s1].weight+ht[s2].weight;}6.5哈夫曼樹及其應用第6章樹和二叉樹例給定權值:

{5,29,7,8,14,23,3,11

}iwtpar

LchRch150

0

02290

0

03

7

0

0

0480

0

05140

0

06230

0

07

3

0

0

08110

0

0900

0

01000

0

01100

0

01200

0

01300

0

01400

0

01500

0

0801

7991503

410101908

911112905101212420611131358021214141000

13141515for(i=1;i<=n;i++)ht[i]={w[i],0,0,0};for(i=n+1;i<=m;i++)ht[i]={0,0,0,0};for(i=n+1;i<=m;i++){select(ht,i-1,&s1,&s2);ht[s1].parent=i;ht[s2].parent=i;ht[i].Lchild=s1;ht[i].Rchild=s2;ht[i].weight=ht[s1].weight

+ht[s2].weight;95哈夫曼編碼在數據通信中，經常需要將傳送的文字轉換為二進制字符0和1組成的二進制串，我們稱這個過程為編碼。例如，假設要傳送的電文為ABACCADAA，電文中只有A,B,C,D四種字符。如果在編碼時考慮字符在要傳送的電文中出現的次數，讓出現次數越高的字符采用越短的編碼，構造一種不等長編碼，則可使要傳送的電文的代碼長度最短。等長編碼：A:00B:01C:10D:11不等長編碼：A:0B:10C:110D:1116.5哈夫曼樹及其應用第6章樹和二叉樹96

設計不等長編碼，必須保證一個字符的編碼都不是另一個字符的編碼的前綴。6.5哈夫曼樹及其應用第6章樹和二叉樹哈夫曼編碼前綴編碼：任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。利用哈夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。哈夫曼編碼:

對哈夫曼樹中每個左分支賦予0，右分支賦予1，則從根到每個葉子的路徑上，各分支的值構成該葉子的哈夫曼編碼。例：若要傳輸如下單詞

state,seat,act,tea,cat,set,a,eat如何使所傳送的信息編碼長度最短？

為保證信息編碼長度最短，先統計各字符出現的次數，然后以此作為權值,構造哈夫曼樹。6.5哈夫曼樹及其應用第6章樹和二叉樹723515851025000011110010010011編碼:左分支:0\右分支:1；根到葉子路徑上的值構成葉子的編碼。11需傳輸信息：state,seat,act,tea,cat,set,a,eat25783ceats各字符權值：010001011011ceats各字符編碼：

構造哈夫曼樹：結論一：哈夫曼編碼是前綴碼。結論二:哈夫曼編碼是最優(yōu)前綴碼。

若di≠dj(字符不同)，則對應的樹葉不同，因為從根到每個葉子的路徑是不同的，所以一條路徑不可能是另一條路徑的前部（前綴），因此哈夫曼編碼是前綴碼。

用字符出現的頻率(Pi)為權值構造哈夫曼樹,并以此來構造字符的哈夫曼編碼，由于哈夫曼樹的WPL最?。核詡鬏數膱笪拈L度：必定最小。WPL=wi×lii=1n報文長=Pi×lii=1n6.5哈夫曼樹及其應用第6章樹和二叉樹100假設某系統通信聯絡中只可能出現8種字符,其出現概率為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,試設計哈夫曼編碼。例如：設w={5,29,7,8,14,23,3,11}538,8}7815,15}1119,19}1429,29}2342,42}2958,58}100,100}01010101010101000100110011110110111011116.5哈夫曼樹及其應用第6章樹和二叉樹哈夫曼