第5章-樹和二叉樹

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

樹(Tree)是ｎ(n≥0)個(gè)結(jié)點(diǎn)的有限集,它或者為空樹(n=0)；或?yàn)榉强諛洌瑢τ诜强諛洌?(1)有且僅有一個(gè)稱之為根的結(jié)點(diǎn)(2)除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)可分為ｍ(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹(SubTree)。T1T2T3

2024年12月28日

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

2024年12月28日

結(jié)點(diǎn)：即樹的數(shù)據(jù)元素結(jié)點(diǎn)的度：結(jié)點(diǎn)掛接的子樹數(shù)樹的度：所有結(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)稱為內(nèi)部節(jié)點(diǎn)根：即根結(jié)點(diǎn)(沒有前驅(qū))基本術(shù)語

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

森林：指m棵不相交的樹的集合。基本術(shù)語例如，刪除A后的子樹集合

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

練習(xí)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個(gè)二叉樹的抽象數(shù)據(jù)類型定義教材p98

2024年12月28日

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

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

個(gè)結(jié)點(diǎn)？1k

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

單支樹

2024年12月28日

北京林業(yè)大學(xué)信息學(xué)院DATAPARENTLCHILDRCHILD二叉樹的鏈?zhǔn)酱鎯?chǔ)

2024年12月28日

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

struct

BiNode{

TElemTypedata;

struct

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

2024年12月28日

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

個(gè)空指針域練習(xí)ABCDEFG^^^^^^^^n+1

2024年12月28日

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

struct

TriTNode

{TelemTypedata;

struct

TriTNode

*lchild,*parent,*rchild;

}TriTNode,*TriTree;

2024年12月28日

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

2024年12月28日

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

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

先序遍歷左子樹(L)

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

2024年12月28日

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

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

中序遍歷左子樹(L)

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

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

2024年12月28日

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

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

后序遍歷左子樹(L)

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

2024年12月28日

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

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

EGHLRCLRD

LRFLRG

LRH

23456781LRE

2024年12月28日

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

2024年12月28日

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

2024年12月28日

c用二叉樹表示算術(shù)表達(dá)式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ù)表達(dá)式

2024年12月28日

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

2024年12月28日

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

和

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

2024年12月28日

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

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

2024年12月28日

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

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

2024年12月28日

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

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

2024年12月28日

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

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

前序遍歷左子樹(L)

前序遍歷右子樹(R)

2024年12月28日

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

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

2024年12月28日

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

else{

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

PreOrderTraverse(T->lchild);

//遞歸遍歷左子樹

PreOrderTraverse(T->rchild);

//遞歸遍歷右子樹

}}

先序遍歷算法

2024年12月28日

北京林業(yè)大學(xué)信息學(xué)院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è)大學(xué)信息學(xué)院遍歷的算法實(shí)現(xiàn)－中序遍歷若二叉樹為空，則空操作否則:

中序遍歷左子樹(L)

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

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

2024年12月28日

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

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

else{

InOrderTraverse(T->lchild);

//遞歸遍歷左子樹

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

InOrderTraverse(T->rchild);

//遞歸遍歷右子樹

}}

中序遍歷算法

2024年12月28日

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

后序遍歷左子樹(L)

后序遍歷右子樹(R)

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

2024年12月28日

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

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

else{

PostOrderTraverse(T->lchild);

//遞歸遍歷左子樹

PostOrderTraverse(T->rchild);

//遞歸遍歷右子樹

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

}}

后序遍歷算法

2024年12月28日

北京林業(yè)大學(xué)信息學(xué)院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è)大學(xué)信息學(xué)院如果去掉輸出語句，從遞歸的角度看，三種算法是完全相同的，或說這三種算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。AFEDCBG遍歷算法的分析AFEDCBG

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

北京林業(yè)大學(xué)信息學(xué)院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è)大學(xué)信息學(xué)院AFEDCBG時(shí)間效率:O(n)

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

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

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

2024年12月28日

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

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

ABC#D#EFG######

2024年12月28日

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

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

2024年12月28日

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

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

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

2024年12月28日

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

cin>>ch;

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

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

CreateBiTree(T->lchild);

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

CreateBiTree(T->rchild);

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

2024年12月28日

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

2024年12月28日

北京林業(yè)大學(xué)信息學(xué)院復(fù)制二叉樹（算法5.4）二叉樹遍歷算法的應(yīng)用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é)點(diǎn)

2024年12月28日

北京林業(yè)大學(xué)信息學(xué)院計(jì)算二叉樹深度（算法5.5）二叉樹遍歷算法的應(yīng)用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è)大學(xué)信息學(xué)院計(jì)算二叉樹結(jié)點(diǎn)總數(shù)（算法5.6）二叉樹遍歷算法的應(yīng)用int

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

2024年12月28日

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

2024年12月28日

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

BCDEGF

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

。為了避免混淆，增加兩個(gè)標(biāo)志域lchildLTagdataRTagrchild線索化二叉樹

2024年12月28日

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

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

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

lchildLTagdataRTagrchild線索化二叉樹

2024年12月28日

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

2024年12月28日

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

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

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

RTag=1,rchild域指向其后繼

先序線索鏈表

2024年12月28日

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

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

2024年12月28日

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

lchildLTagdataRTagrchildABCDEABDCET后序序列：CBEDA0000111111^后序線索二叉樹后序線索鏈表…………prepprep中序序列12ii+1i+2n中序線索化構(gòu)造線索化二叉樹中序遍歷二叉樹給pre加上右線索，給p加上左線索算法5.7以結(jié)點(diǎn)p為根的子樹中序線索化構(gòu)造線索化二叉樹voidInThreading(BiThrTreep){//pre是全局變量，初始化時(shí)其//右孩子指針為空，便于在樹的//最左點(diǎn)開始建線索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è)大學(xué)信息學(xué)院ABCGEIDHFroot懸空？懸空？該二叉樹中序遍歷結(jié)果為:

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

2024年12月28日

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

2024年12月28日

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

2825405560330854因?yàn)橹行虮闅v序列是：5540256028083354對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。NILNIL練習(xí)

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

D

E

B

A

FG

H

K

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

2024年12月28日

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

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

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

對應(yīng)

2024年12月28日

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

2024年12月28日

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

2024年12月28日

樹二叉樹

對應(yīng)

存儲(chǔ)

解釋

解釋

2024年12月28日

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

struct

CSNode{

ElemTypedata;

struct

CSNode

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

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

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

2024年12月28日

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

wklk

k=1n

2024年12月28日

北京林業(yè)大學(xué)信息學(xué)院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個(gè)葉子結(jié)點(diǎn)的二叉樹

2024年12月28日

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

2024年12月28日

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

2024年12月28日

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

struct{int

weght;

intparent;

int

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

個(gè)結(jié)點(diǎn)2n-1

2024年12月28日

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

3.1)在HT[1..i-1]中選兩個(gè)未被選過的weight最小的兩個(gè)結(jié)點(diǎn)HT[s1]和HT[s2](從parent=0的結(jié)點(diǎn)中選)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)造算法的實(shí)現(xiàn)529782314113霍夫曼樹的葉節(jié)點(diǎn)數(shù)n=8,所有節(jié)點(diǎn)數(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個(gè)葉子結(jié)點(diǎn)：置HT[1..n]的weight值529782314113n=8

2024年12月28日

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

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

3.1)在HT[1..i-1]中選兩個(gè)未被選過的weight最小的兩個(gè)結(jié)點(diǎn)HT[s1]和HT[s2](從parent=0的結(jié)點(diǎn)中選)s2s13)進(jìn)行以下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)進(jìn)行以下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é)點(diǎn)iweightparentlchildrchild15900229000370048005140006230007390081100098017100…………01010415300-29782314115382923141153878150is2s13)進(jìn)行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中選兩個(gè)未被選過的weight最小的兩個(gè)結(jié)點(diǎn)HT[s1]和HT[s2](從parent=0的結(jié)點(diǎn)中選)3)進(jìn)行以下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)進(jìn)行以下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é)點(diǎn)iweightparentlchildrchild15900229000371000481000514000623000739008110098171015034110…………01111819900-2923141153878150292314781511538193)進(jìn)行以下n-1次合并，依次產(chǎn)生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中選兩個(gè)未被選過的weight最小的兩個(gè)結(jié)點(diǎn)HT[s1]和HT[s2](從parent=0的結(jié)點(diǎn)中選)is2s13)進(jìn)行以下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)進(jìn)行以下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é)點(diǎn)

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è)計(jì)huffmancode(m=2*8-1=15)000000000000000000000000000000

2024年12月28日

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

{

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

//在HT[k](1≤k≤i-1)中選擇兩個(gè)其雙親域?yàn)?,

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

//并返回它們在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字符的赫夫曼編碼算法的實(shí)現(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è)計(jì)哈夫曼編碼.首先,用赫夫曼算法求以概率(乘以100)為權(quán)的最優(yōu)2元樹.這里w=(5,29.7.8.14,23,3,11).然后,對每個(gè)字符進(jìn)行編碼.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//逐個(gè)字符求赫夫曼編碼for(i=1;i<=n;++i){ //求出第i個(gè)字符的編碼}字符的霍夫曼編碼算法的實(shí)現(xiàn)100292914781558428115319230111111010029291478155842811531923cfcfccff11101110c=i;f=i的雙親節(jié)點(diǎn);

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

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

}

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