第5章-樹和二叉樹

2024年12月28日

數(shù)據(jù)結(jié)構(gòu)

2024年12月28日

樹形結(jié)構(gòu):線性結(jié)構(gòu):有唯一的前驅(qū)，唯一的后繼abcdefghi有唯一的前驅(qū)，多個的后繼

2024年12月28日

第5章樹和二叉樹5.1樹的定義和基本術(shù)語5.2二叉樹5.3遍歷二叉樹與線索二叉樹5.4樹和森林5.5霍夫曼樹及其應用

2024年12月28日

5.1樹的定義和基本術(shù)語樹(Tree)是ｎ(n≥0)個結(jié)點的有限集,它或者為空樹(n=0)；或為非空樹，對于非空樹Ｔ:(1)有且僅有一個稱之為根的結(jié)點(2)除根結(jié)點以外的其余結(jié)點可分為ｍ(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。

2024年12月28日

樹(Tree)是ｎ(n≥0)個結(jié)點的有限集,它或者為空樹(n=0)；或為非空樹，對于非空樹Ｔ:(1)有且僅有一個稱之為根的結(jié)點(2)除根結(jié)點以外的其余結(jié)點可分為ｍ(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。T1T2T3

2024年12月28日

凹入表示嵌套集合廣義表樹的其它表示方式

2024年12月28日

結(jié)點：即樹的數(shù)據(jù)元素結(jié)點的度：結(jié)點掛接的子樹數(shù)樹的度：所有結(jié)點度中的最大值葉子：度為０的結(jié)點稱為葉子或終端結(jié)點(沒有后繼)分支結(jié)點：度不為０的結(jié)點稱為分支結(jié)點或非終端結(jié)點內(nèi)部結(jié)點：除根節(jié)點之外的分支結(jié)點稱為內(nèi)部節(jié)點根：即根結(jié)點(沒有前驅(qū))基本術(shù)語

2024年12月28日

雙親和孩子：結(jié)點的子樹的根稱為該結(jié)點的孩子，相應地，該節(jié)點稱為孩子的雙親。(一個結(jié)點的雙親是該節(jié)點的直接前驅(qū)，孩子是該節(jié)點的直接后繼)兄弟：同一雙親下的孩子之間互稱兄弟。祖先：即從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。子孫：以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫?；拘g(shù)語

2024年12月28日

結(jié)點的層次：從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）。樹中任一結(jié)點的層次等于其雙親結(jié)點的層次加１。堂兄弟：即雙親位于同一層的結(jié)點（但并非同一雙親）。樹的深度(或高度)：樹中結(jié)點的最大層次稱為樹的深度或高度。層次1234基本術(shù)語

2024年12月28日

有序樹：結(jié)點各子樹從左至右有序，不能互換（左為第一）無序樹：結(jié)點各子樹可互換位置?；拘g(shù)語T1T2T3

2024年12月28日

森林：指m棵不相交的樹的集合?；拘g(shù)語例如，刪除A后的子樹集合

2024年12月28日

ADTTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTTree若D為空集，則稱為空樹；//允許n=0若D中僅含一個數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于數(shù)據(jù)元素的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有15個樹的抽象數(shù)據(jù)類型定義教材p95

2024年12月28日

5.2二叉樹普通樹（多叉樹）若不轉(zhuǎn)化為二叉樹，則運算很難實現(xiàn)為何要重點研究每結(jié)點最多只有兩個“叉”的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；可以證明，所有樹都能轉(zhuǎn)為唯一對應的二叉樹，不失一般性。

2024年12月28日

二叉樹基本特點：結(jié)點的度小于等于2有序樹（子樹有序，不能顛倒）二叉樹的五種不同形態(tài)

2024年12月28日

具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？普通樹呢？

練習5種/2種

2024年12月28日

ADTBinaryTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于數(shù)據(jù)元素的說明④……//關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個二叉樹的抽象數(shù)據(jù)類型定義教材p98

2024年12月28日

性質(zhì)1:在二叉樹的第i層上至多有2i-1個結(jié)點二叉樹的性質(zhì)提問：第i層上至少有

個結(jié)點？性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點提問：深度為k時至少有

個結(jié)點？1k

2024年12月28日

性質(zhì)3:對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)n0必定為n2＋1（即n0=n2+1）

2024年12月28日

北京林業(yè)大學信息學院滿二叉樹：一棵深度為k且有2k-1個結(jié)點的二叉樹。（特點：每層都“充滿”了結(jié)點）特殊形態(tài)的二叉樹完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應只有最后一層葉子不滿，且全部集中在左邊

2024年12月28日

北京林業(yè)大學信息學院滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。滿二叉樹和完全二叉樹的區(qū)別

2024年12月28日

北京林業(yè)大學信息學院一棵完全二叉樹有5000個結(jié)點，可以計算出其葉結(jié)點的個數(shù)是（）。練習2500

2024年12月28日

北京林業(yè)大學信息學院性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為＋1k層nk-1層

2024年12月28日

北京林業(yè)大學信息學院性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2。

2024年12月28日

北京林業(yè)大學信息學院二叉樹的順序存儲實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素。

2024年12月28日

北京林業(yè)大學信息學院abcde####fg1234567891011abcdefg特點：結(jié)點間關(guān)系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹二叉樹的順序存儲

單支樹

2024年12月28日

北京林業(yè)大學信息學院DATAPARENTLCHILDRCHILD二叉樹的鏈式存儲

2024年12月28日

北京林業(yè)大學信息學院ABCDEFGABCDEFG^^^^^^^^二叉鏈表typedef

struct

BiNode{

TElemTypedata;

struct

BiNode*lchild,*rchild;//左右孩子指針}BiNode,*BiTree;lchilddatarchild

2024年12月28日

北京林業(yè)大學信息學院分析：必有2n個鏈域。除根結(jié)點外，每個結(jié)點有且僅有一個雙親，所以只會有n－1個結(jié)點的鏈域存放指針，指向非空子女結(jié)點?？罩羔様?shù)目＝2n－(n-1)=n+1在n個結(jié)點的二叉鏈表中，有

個空指針域練習ABCDEFG^^^^^^^^n+1

2024年12月28日

北京林業(yè)大學信息學院三叉鏈表ABCDEFGABCDEFG^^^^^^^^^lchilddataparentrchildtypedef

struct

TriTNode

{TelemTypedata;

struct

TriTNode

*lchild,*parent,*rchild;

}TriTNode,*TriTree;

2024年12月28日

北京林業(yè)大學信息學院5.3遍歷二叉樹和線索二叉樹遍歷定義——指按某條搜索路線遍訪每個結(jié)點且不重復（又稱周游）。遍歷用途——它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。

2024年12月28日

北京林業(yè)大學信息學院DLR遍歷規(guī)則左子樹ROOT右子樹DLRLDRLRDDRLRDLRLD子樹先左后右先序遍歷：若二叉樹為空，則空操作，否則

訪問根結(jié)點(D)

先序遍歷左子樹(L)

先序遍歷右子樹(R)DLR——先序遍歷LDR——中序遍歷LRD——后序遍歷先序遍歷

2024年12月28日

北京林業(yè)大學信息學院ALRBLR先序遍歷序列：ABCDEFGH先序遍歷ABFCD

EGHCLRDLRELRFLRGLRHLR23456781中序遍歷：若二叉樹為空，則空操作，否則

中序遍歷左子樹(L)

訪問根結(jié)點(D)

中序遍歷右子樹(R)DLR——先序遍歷LDR——中序遍歷LRD——后序遍歷中序遍歷

2024年12月28日

北京林業(yè)大學信息學院LARLBR中序遍歷序列：BDCEAFHG中序遍歷ABFCD

EGHLCRLDRLFRLGRLHR23456781LER后序遍歷：若二叉樹為空，則空操作，否則

后序遍歷左子樹(L)

后序遍歷右子樹(R)訪問根結(jié)點(D)DLR——先序遍歷LDR——中序遍歷LRD——后序遍歷后序遍歷

2024年12月28日

北京林業(yè)大學信息學院L

RALRB后序遍歷序列：DECBHGFA后序遍歷ABFCD

EGHLRCLRD

LRFLRG

LRH

23456781LRE

2024年12月28日

北京林業(yè)大學信息學院先序遍歷：中序遍歷：后序遍歷：ABCDEABDECDBEACDEBCA

2024年12月28日

c用二叉樹表示算術(shù)表達式dbef-*a+/-a+b*(c-d)–e/f

2024年12月28日

c用二叉樹表示算術(shù)表達式dbef-*a+/-先序遍歷–

+a*b–

cd/ef前綴表示中序遍歷a+b*c

–

d

–e/f中綴表示后序遍歷abcd–*+ef/–后綴表示層序遍歷–

+/a

*

efb–cd

2024年12月28日

+*A*/EDCB先序遍歷+**/ABCDE前綴表示中序遍歷A/B*C*D+E中綴表示后序遍歷AB/C*D*E+后綴表示層序遍歷+*E*D/CAB用二叉樹表示算術(shù)表達式

2024年12月28日

北京林業(yè)大學信息學院若二叉樹中各結(jié)點的值均不相同，則：由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。重要結(jié)論

2024年12月28日

北京林業(yè)大學信息學院練習已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG

和

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

2024年12月28日

北京林業(yè)大學信息學院中序遍歷：BDCEAFHG

后序遍歷：DECBHGFAA的左子樹:中序:BDCE后序:DECBAA的右子樹:中序:FHG后序:HGF

2024年12月28日

北京林業(yè)大學信息學院中序遍歷：BDCEAFHG

后序遍歷：DECBHGFAB的右子樹:中序:DCE后序:DECABCDE

2024年12月28日

北京林業(yè)大學信息學院中序遍歷：BDCEAFHG

后序遍歷：DECBHGFAABCDEFGHF的右子樹:中序:HG后序:HG

2024年12月28日

北京林業(yè)大學信息學院DLRADLRDLR>B>>D>>CDLRADBC先序遍歷序列：ABDC遍歷的算法實現(xiàn)－先序遍歷若二叉樹為空，則空操作否則

訪問根結(jié)點(D)

前序遍歷左子樹(L)

前序遍歷右子樹(R)

2024年12月28日

北京林業(yè)大學信息學院則三種遍歷算法可寫出:遍歷的算法實現(xiàn)－－用遞歸形式格外簡單！longFactorial(longn){if(n==0)return1;//基本項

elsereturnn*Factorial(n-1);//歸納項}回憶:

2024年12月28日

北京林業(yè)大學信息學院StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉樹

else{

cout<<T->data;//訪問根結(jié)點

PreOrderTraverse(T->lchild);

//遞歸遍歷左子樹

PreOrderTraverse(T->rchild);

//遞歸遍歷右子樹

}}

先序遍歷算法

2024年12月28日

北京林業(yè)大學信息學院StatusPreOrderTraverse(BiTreeT){

if(T==NULL)returnOK;else{

cout<<T->data;

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->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

2024年12月28日

北京林業(yè)大學信息學院遍歷的算法實現(xiàn)－中序遍歷若二叉樹為空，則空操作否則:

中序遍歷左子樹(L)

訪問根結(jié)點(D)

中序遍歷右子樹(R)ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC

2024年12月28日

北京林業(yè)大學信息學院StatusInOrderTraverse(BiTreeT){

if(T==NULL)returnOK;//空二叉樹

else{

InOrderTraverse(T->lchild);

//遞歸遍歷左子樹

cout<<T->data;//訪問根結(jié)點

InOrderTraverse(T->rchild);

//遞歸遍歷右子樹

}}

中序遍歷算法

2024年12月28日

北京林業(yè)大學信息學院遍歷的算法實現(xiàn)－后序遍歷若二叉樹為空，則空操作否則

后序遍歷左子樹(L)

后序遍歷右子樹(R)

訪問根結(jié)點(D)ADBCLRDLRDLRDA>>D>>CLRDB后序遍歷序列：DBCA

2024年12月28日

北京林業(yè)大學信息學院StatusPostOrderTraverse(BiTreeT){

if(T==NULL)returnOK;//空二叉樹

else{

PostOrderTraverse(T->lchild);

//遞歸遍歷左子樹

PostOrderTraverse(T->rchild);

//遞歸遍歷右子樹

cout<<T->data;//訪問根結(jié)點

}}

后序遍歷算法

2024年12月28日

北京林業(yè)大學信息學院StatusPreOrderTraverse(BiTreeT){

if(T==NULL)returnOK;else{

cout<<T->data;

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);

}}

StatusPostOrderTraverse(BiTreeT){

if(T==NULL)returnOK;else{

PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

cout<<T->data;}}

StatusInOrderTraverse(BiTreeT){

if(T==NULL)returnOK;else{

InOrderTraverse(T->lchild);

cout<<T->data;

InOrderTraverse(T->rchild);

}}

遍歷算法的分析

2024年12月28日

北京林業(yè)大學信息學院如果去掉輸出語句，從遞歸的角度看，三種算法是完全相同的，或說這三種算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同。AFEDCBG遍歷算法的分析AFEDCBG

2024年12月28日

北京林業(yè)大學信息學院如果去掉輸出語句，從遞歸的角度看，三種算法是完全相同的，或說這三種算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同。從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過3次。AFEDCBG第1次經(jīng)過時訪問＝先序遍歷第2次經(jīng)過時訪問＝中序遍歷第3次經(jīng)過時訪問＝后序遍歷遍歷算法的分析

2024年12月28日

北京林業(yè)大學信息學院AFEDCBG中序遍歷二叉樹的非遞歸算法ABDPush(A)Push(B)Push(D)…Pop(D)Push(E)EPop(B)visit(B)visit(D)

2024年12月28日

北京林業(yè)大學信息學院AFEDCBGAPop(A)visit(A)Push(C)C中序遍歷二叉樹的非遞歸算法…

2024年12月28日

北京林業(yè)大學信息學院AFEDCBGC？中序遍歷二叉樹的非遞歸算法…voidInOrderTraverse(BiTreeT){//中序遍歷二叉樹的非遞歸算法

InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){

push(S,p);p=p->lchild;}else{

pop(S,p);

cout<<p->data;p=p->rchild;}}//while}//InOrderTraverseAFEDCBG中序遍歷二叉樹的非遞歸算法

2024年12月28日

北京林業(yè)大學信息學院AFEDCBG時間效率:O(n)

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

//棧占用的最大輔助空間遍歷算法的分析abdc左單支樹時，棧占用的最大輔助空間

2024年12月28日

北京林業(yè)大學信息學院ABC二叉樹的建立先序序列：ABCABCABCABCABC

2024年12月28日

北京林業(yè)大學信息學院二叉樹的建立AB##C##ABCABCABCABCABCABC####AB#C###A#BC###A#B#C##

2024年12月28日

北京林業(yè)大學信息學院ABCDEFG二叉樹的建立先序序列為：

ABC##DE#G##F###ABCDEFG

2024年12月28日

北京林業(yè)大學信息學院ABCDEFG二叉樹的建立先序序列為：

ABC##DE#G##F###

ABC#D#EFG######

2024年12月28日

北京林業(yè)大學信息學院A^B^C^D^E^F^^G^二叉樹的建立ABCDEFG先序序列為：

ABC##DE#G##F###

2024年12月28日

北京林業(yè)大學信息學院二叉樹的建立先序序列為：

ABC##DE#G##F###

ABC#D#EFG######ABCDEFG^^^^^^^^

2024年12月28日

二叉樹的建立（算法5.3）voidCreateBiTree(BiTree&T){ //按先序次序輸入二叉樹中結(jié)點的值（一個字符），//創(chuàng)建二叉鏈表表示的二叉樹T charch;

cin>>ch;

if(ch=='#')T=NULL; //遞歸結(jié)束，建空樹

else{ T=newBiTNode; T->data=ch;//生成根結(jié)點//遞歸創(chuàng)建左子樹

CreateBiTree(T->lchild);

//遞歸創(chuàng)建右子樹

CreateBiTree(T->rchild);

}//else} //CreateBiTree訪問節(jié)點

2024年12月28日

北京林業(yè)大學信息學院復制二叉樹計算二叉樹深度計算二叉樹結(jié)點總數(shù)二叉樹遍歷算法的應用

2024年12月28日

北京林業(yè)大學信息學院復制二叉樹（算法5.4）二叉樹遍歷算法的應用voidCopy(BiTreeT,BiTree&NewT){if(T==NULL){

NewT=NULL;return;}else{

NewT=newBiTNode;

NewT->data=T->data;

copy(T->lchild,NewT->lchild);

copy(T->rchild,NewT->rchild);}}訪問節(jié)點

2024年12月28日

北京林業(yè)大學信息學院計算二叉樹深度（算法5.5）二叉樹遍歷算法的應用intDepth(BiTreeT){if(T==NULL)return0;else{m=Depth(T->lchild);n=Depth(T->rchild);if(m>n)return(m+1);elsereturn(n+1);}}

2024年12月28日

北京林業(yè)大學信息學院計算二叉樹結(jié)點總數(shù)（算法5.6）二叉樹遍歷算法的應用int

NodeCount(BiTreeT){if(T==NULL)return0;elsereturnNodeCount(T->lchild)+NodeCount(T->rchild)+1;}

2024年12月28日

北京林業(yè)大學信息學院二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——可以用它來存放當前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。思考線索化二叉樹在n個結(jié)點的二叉鏈表中，有n+1個空指針域ABCDEFG^^^^^^^^

2024年12月28日

北京林業(yè)大學信息學院空指針域可以用來存放當前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。ABCDEFG^^^^^^^線索化二叉樹^先序遍歷結(jié)果：A

BCDEGF

2024年12月28日

北京林業(yè)大學信息學院普通二叉樹只能找到結(jié)點的左右孩子信息，而該結(jié)點的直接前驅(qū)和直接后繼只能在遍歷過程中獲得若將遍歷后對應的有關(guān)前驅(qū)和后繼預存起來，則從第一個結(jié)點開始就能很快“順藤摸瓜”而遍歷整個樹例如中序遍歷結(jié)果：BDCEAFHG，實際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！可能是根、或最左（右）葉子線索化二叉樹

2024年12月28日

北京林業(yè)大學信息學院兩種解決方法增加兩個域：fwd和bwd；利用空鏈域（n+1個空鏈域）如何保存這類信息？線索化二叉樹

2024年12月28日

北京林業(yè)大學信息學院1）若結(jié)點有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)

。為了避免混淆，增加兩個標志域lchildLTagdataRTagrchild線索化二叉樹

2024年12月28日

北京林業(yè)大學信息學院LTag:若LTag=0,lchild域指向左孩子；

若LTag=1,lchild域指向其前驅(qū)。RTag:若RTag=0,rchild域指向右孩子；

若RTag=1,rchild域指向其后繼。

lchildLTagdataRTagrchild線索化二叉樹

2024年12月28日

北京林業(yè)大學信息學院線索：指向結(jié)點前驅(qū)和后繼的指針線索二叉樹：加上線索的二叉樹（圖形式樣）線索化二叉樹的幾個術(shù)語先序序列：ABCDEABCDENULL線索鏈表：加上線索二叉鏈表線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程

2024年12月28日

北京林業(yè)大學信息學院ABCDEABDCET先序序列：ABCDE00001111^11

lchildLTagdataRTagrchild先序線索二叉樹LTag=0,lchild域指向左孩子

LTag=1,lchild域指向其前驅(qū)RTag=0,rchild域指向右孩子

RTag=1,rchild域指向其后繼

先序線索鏈表

2024年12月28日

北京林業(yè)大學信息學院ABCDEABDCET中序序列：BCAED00001111^11^

lchildLTagdataRTagrchild中序線索二叉樹中序線索鏈表

2024年12月28日

北京林業(yè)大學信息學院

lchildLTagdataRTagrchildABCDEABDCET后序序列：CBEDA0000111111^后序線索二叉樹后序線索鏈表…………prepprep中序序列12ii+1i+2n中序線索化構(gòu)造線索化二叉樹中序遍歷二叉樹給pre加上右線索，給p加上左線索算法5.7以結(jié)點p為根的子樹中序線索化構(gòu)造線索化二叉樹voidInThreading(BiThrTreep){//pre是全局變量，初始化時其//右孩子指針為空，便于在樹的//最左點開始建線索if(p){

InThreading(p->lchild);

if(!p->lchild){p->LTag=1;p->lchild=pre;}

if(!pre->rchild){pre->RTag=1;pre->rchild=p;}pre=p;

InThreading(p->rchild);}

2024年12月28日

北京林業(yè)大學信息學院ABCGEIDHFroot懸空？懸空？該二叉樹中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,G畫出以下二叉樹對應的中序線索二叉樹。為避免懸空態(tài)，應增設(shè)一個頭結(jié)點練習

2024年12月28日

北京林業(yè)大學信息學院對應的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,G0--root0

2024年12月28日

北京林業(yè)大學信息學院畫出與二叉樹對應的中序線索二叉樹

2825405560330854因為中序遍歷序列是：5540256028083354對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。NILNIL練習

2024年12月28日

北京林業(yè)大學信息學院平衡樹——排序樹——判定樹——帶權(quán)樹——最優(yōu)樹——特點：左右子樹深度差≤1特點：“左小右大”例如，12個球只稱3次分出輕重特點：路徑長度帶權(quán)值帶權(quán)路徑長度最短的樹，又稱Huffman樹，用途之一是通信中的壓縮編碼。二叉樹的應用5.5霍夫曼樹

2024年12月28日

北京林業(yè)大學信息學院5.4樹和森林樹的存儲結(jié)構(gòu)－－雙親表示法R-1A0B0D1C0F3K6G6H6E10123456789數(shù)組下標dataparent

2024年12月28日

北京林業(yè)大學信息學院RC

D

E

B

A

FG

H

K

datachild1child2…childd樹的存儲結(jié)構(gòu)－－孩子表示法多重鏈表

2024年12月28日

北京林業(yè)大學信息學院C1B0A2

datadegreechild1…childdR3F3K0E0G0D0E0樹的存儲結(jié)構(gòu)－－孩子表示法多重鏈表data指向孩子鏈表的指針樹的存儲結(jié)構(gòu)－－孩子表示法孩子鏈表雙親

data指向孩子鏈表的指針樹的存儲結(jié)構(gòu)－－孩子表示法帶雙親的孩子鏈表

2024年12月28日

北京林業(yè)大學信息學院樹的存儲結(jié)構(gòu)－－二叉鏈表表示法ABCDEFGRHK二叉樹的節(jié)點n，n的左孩子是n在樹中的第一個孩子，n的右孩子是n在樹中右兄弟.樹轉(zhuǎn)換為二叉樹

2024年12月28日

北京林業(yè)大學信息學院樹的存儲結(jié)構(gòu)－－二叉鏈表表示法ABCR二叉樹的節(jié)點n，n的左孩子是n在樹中的第一個孩子，n的右孩子是n在樹中右兄弟.樹轉(zhuǎn)換為二叉樹

2024年12月28日

樹的存儲結(jié)構(gòu)－－二叉鏈表表示法ABCDEFGRHK二叉樹的節(jié)點n，n的左孩子是n在樹中的第一個孩子，n的右孩子是n在樹中右兄弟.樹轉(zhuǎn)換為二叉樹注意：由于樹根沒有兄弟，故二叉樹的樹根沒有右孩子

2024年12月28日

北京林業(yè)大學信息學院樹的存儲結(jié)構(gòu)－－二叉鏈表表示法ABCDEFGRHK二叉樹的節(jié)點n，n的左孩子是n在樹中的第一個孩子，n的右孩子是n在樹中右兄弟.ARBCDEFGHK二叉樹轉(zhuǎn)換為樹

2024年12月28日

北京林業(yè)大學信息學院樹的存儲結(jié)構(gòu)－－二叉鏈表表示法

對應

2024年12月28日

北京林業(yè)大學信息學院樹的存儲結(jié)構(gòu)－－二叉鏈表表示法

2024年12月28日

北京林業(yè)大學信息學院樹的存儲結(jié)構(gòu)－－二叉鏈表表示法

2024年12月28日

樹二叉樹

對應

存儲

解釋

解釋

2024年12月28日

北京林業(yè)大學信息學院樹的存儲結(jié)構(gòu)－－二叉鏈表表示法typedef

struct

CSNode{

ElemTypedata;

struct

CSNode

*firstchild,*nextsibling;}CSNode,*CSTree;說明:CS中，C—Child,S—SiblingBACDFEGJHIBACDFEGJHI樹與二叉樹對應BACDFEGJHI

對應樹根相連森林與二叉樹的轉(zhuǎn)換－－森林轉(zhuǎn)換為二叉樹BACDFEGJHIBACDFEGJHI拆開樹根BACDFEGJHI

對應二叉樹與樹對應森林與二叉樹的轉(zhuǎn)換－－二叉樹轉(zhuǎn)換為森林樹和森林的遍歷樹的遍歷——先序遍歷（先根遍歷）先訪問樹的根節(jié)點，然后依次先序遍歷根的每棵子樹。RADEBCFGHK先序序列：RADEBCFGHK先序序列：RADEBCFGHK先序遍歷一棵樹恰好等價于先序遍歷該樹對應的二叉樹樹和森林的遍歷樹的遍歷——后序遍歷（后根遍歷）先依次后序遍歷根的每棵子樹。然后訪問樹的根節(jié)點。DEABGHKFCR后序遍歷：DEABGHKFCR中序遍歷：DEABGHKFCR后序遍歷一棵樹恰好等價于中序遍歷該樹對應的二叉樹樹和森林的遍歷樹和森林的遍歷按照森林和樹的相互遞歸定義，可以推出森林的兩種遍歷方法。1、樹的先序遍歷推出森林的先序遍歷樹和森林的遍歷森林的遍歷——先序遍歷(1)訪問森林中第一棵樹的根節(jié)點(2)先序遍歷第一棵樹的根節(jié)點的子樹森林(3)先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林即，依次對每一棵樹進行先序遍歷。Part2RootPart1BACDFEGJHI樹和森林的遍歷森林的遍歷——先序遍歷先序序列：ADCDEFGHIJBACDFEGJHIBACDFEGJHI先序序列：ABCDEFGHIJ先序序列：ABCDEFGHIJ先序遍歷森林等同于先序遍歷該森林對應的二叉樹。樹和森林的遍歷按照森林和樹的相互遞歸定義，可以推出森林的兩種遍歷方法。2、樹的后序遍歷推出森林的中序遍歷樹和森林的遍歷森林的遍歷——中序遍歷(1)中序遍歷森林中第一棵樹的根節(jié)點的子樹森林(2)訪問第一棵樹的根節(jié)點(3)中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林Part2Part1Root即，依次對每一棵樹進行后序遍歷。BACDFEGJHI樹和森林的遍歷森林的遍歷——中序遍歷中序序列：BCDAFEHJIGBACDFEGJHIBACDFEGJHI中序遍歷森林等同于中序遍歷該森林對應的二叉樹。中序序列：BCDAFEHJIG中序序列：BCDAFEHJIG

2024年12月28日

北京林業(yè)大學信息學院5.5霍夫曼樹及其應用路徑：路徑長度：帶權(quán)路徑長度：樹的帶權(quán)路徑長度：霍夫曼樹：由一結(jié)點到另一結(jié)點間的分支所構(gòu)成路徑上的分支數(shù)目結(jié)點到根的路徑長度與結(jié)點上權(quán)的乘積debacfg樹中所有葉子結(jié)點的帶權(quán)路徑長度之和帶權(quán)路徑長度最小的樹a→e的路徑長度＝2WPL=

wklk

k=1n

2024年12月28日

北京林業(yè)大學信息學院dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=7*2+5*2+2*2+4*2=36權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹

2024年12月28日

北京林業(yè)大學信息學院a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4霍夫曼樹的構(gòu)造過程操作要點：對權(quán)值的合并、刪除與替換，總是合并當前值最小的兩個基本思想：使權(quán)大的結(jié)點靠近根

2024年12月28日

北京林業(yè)大學信息學院根據(jù)給定的n個權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點的二叉樹。在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和。在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。重復上述兩步，直到只含一棵樹為止，這棵樹即霍夫曼樹?；舴蚵鼧涞臉?gòu)造過程

2024年12月28日

北京林業(yè)大學信息學院Ch5_8.ctypedef

struct{int

weght;

intparent;

int

lchild,rchild;}*HuffmanTree;霍夫曼樹構(gòu)造算法的實現(xiàn)（算法5.10）采用順序存儲結(jié)構(gòu)——一維結(jié)構(gòu)數(shù)組結(jié)點類型定義一棵有n個葉子結(jié)點的Huffman樹有

個結(jié)點2n-1

2024年12月28日

北京林業(yè)大學信息學院1)初始化HT[1..2n-1]：lchild=rchild=parent=02)輸入初始n個葉子結(jié)點：置HT[1..n]的weight值3)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中選兩個未被選過的weight最小的兩個結(jié)點HT[s1]和HT[s2](從parent=0的結(jié)點中選)3.2)修改HT[s1]和HT[s2]的parent值：parent=i3.3)置HT[i]：weight=HT[s1].weight+HT[s2].weight,

lch=s1,rch=s2霍夫曼樹構(gòu)造算法的實現(xiàn)529782314113霍夫曼樹的葉節(jié)點數(shù)n=8,所有節(jié)點數(shù)m=2n-1=15已知w=(5,29,7,8,14,23,3,11),試構(gòu)造一棵霍夫曼樹.1)初始化HT[1..2n-1]：lchild=rchild=parent=0529782314113n=82)輸入初始n個葉子結(jié)點：置HT[1..n]的weight值529782314113n=8

2024年12月28日

北京林業(yè)大學信息學院3)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.1)……3.2)……3.3)……霍夫曼樹構(gòu)造算法的實現(xiàn)iiiiiii529782314113100292914781558428115319235297823141132978231411538結(jié)點iweightparentlchildrchild1500229000370004800051400062300073008110009010-000…………099i801700-3)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中選兩個未被選過的weight最小的兩個結(jié)點HT[s1]和HT[s2](從parent=0的結(jié)點中選)s2s13)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.2)修改HT[s1]和HT[s2]的parent值:

HT[s1].parent=i,HT[s2].parent=i3)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.3)置HT[i]：

HT[i].lchild=s1,HT[i].rchild=s2

HT[i].

weight=HT[s1].weight+HT[s2].weight

2978231411538結(jié)點iweightparentlchildrchild15900229000370048005140006230007390081100098017100…………01010415300-29782314115382923141153878150is2s13)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中選兩個未被選過的weight最小的兩個結(jié)點HT[s1]和HT[s2](從parent=0的結(jié)點中選)3)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.2)修改HT[s1]和HT[s2]的parent值：

HT[s1].parent=i,HT[s2].parent=i3)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.3)置HT[i]：

HT[i].lchild=s1,HT[i].rchild=s2，

HT[i].weight=HT[s1].weight+HT[s2].weight

結(jié)點iweightparentlchildrchild15900229000371000481000514000623000739008110098171015034110…………01111819900-2923141153878150292314781511538193)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中選兩個未被選過的weight最小的兩個結(jié)點HT[s1]和HT[s2](從parent=0的結(jié)點中選)is2s13)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.2)修改HT[s1]和HT[s2]的parent值：

HT[s1].parent=i,HT[s2].parent=i3)進行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.3)置HT[i]：

HT[i].lchild=s1,HT[i].rchild=s2，HT[i].weight=HT[s1].weight+HT[s2].weight

2024年12月28日

算法voidCreatHuffmanTree(HuffmanTree

HT,intn){if(n<=1)return;m=2*n-1;HT=newHTNode[m+1];//0號單元未用，HT[m]表示根結(jié)點

for(i=1;i<=m;++i){HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(i=1;i<=n;++i)cin>>HT[i].weight;

weightparentlch

ildrchild1．．．８９．．15529781423311000000000000000例:設(shè)n=8,w={5,29,7,8,14,23,3,11}試設(shè)計huffmancode(m=2*8-1=15)000000000000000000000000000000

2024年12月28日

北京林業(yè)大學信息學院for(i=n+1;i<=m;++i)//構(gòu)造Huffman樹

{

Select(HT,i-1,s1,s2);

//在HT[k](1≤k≤i-1)中選擇兩個其雙親域為0,

//且權(quán)值最小的結(jié)點,

//并返回它們在HT中的序號s1和s2HT[s1].parent=i;HT[s2].parent=i;

//表示從F中刪除s1,s2

HT[i].lchild=s1;HT[i].rchild=s2;

//s1,s2分別作為i的左右孩子

HT[i].weight=HT[s1].weight+HT[s2].weight;

//i的權(quán)值為左右孩子權(quán)值之和

}}100292914781558428115319238115319529782314113297823141153815782923141153815782923142914781581153192923428115319232914781529292914781558428115319231002929147815584281153192310029291478155842811531923注意：按程序構(gòu)造出的赫夫曼樹是唯一的!100292914781558428115319230010111111000000011001111111111011010字符的赫夫曼編碼算法的實現(xiàn)已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符,其概率分別為:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,試設(shè)計哈夫曼編碼.首先,用赫夫曼算法求以概率(乘以100)為權(quán)的最優(yōu)2元樹.這里w=(5,29.7.8.14,23,3,11).然后,對每個字符進行編碼.1.a(0.05,5):01102.b(0.29,29):103.c(0.07,7):11104.d(0.08,8):11115.e(0.14,14):1106.f(0.23,23):007.g(0.03,3):01118.h(0.11,11):010010100292914781558428115319230010111111000000010011001111111111011010iiiiiiii//逐個字符求赫夫曼編碼for(i=1;i<=n;++i){ //求出第i個字符的編碼}字符的霍夫曼編碼算法的實現(xiàn)100292914781558428115319230111111010029291478155842811531923cfcfccff11101110c=i;f=i的雙親節(jié)點;

while(f是樹中結(jié)點){

if(f的左孩子==c)生成代碼0else生成代碼1;c=f;f=f的雙親;//回溯

}

}cf10029291478155842811531923cfcfccff11101110結(jié)點iweightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229155101342156111458152121510001314for(i=1;i<=n;++i){c=i;f=HT[i].parent;