第六章-樹和二叉樹2課件

第六章樹和二叉樹(2)第六章樹和二叉樹(2)1主要內容樹的定義和基本術語二叉樹遍歷二叉樹線索二叉樹樹、森林與二叉樹赫夫曼樹及其應用主要內容樹的定義和基本術語24、線索二叉樹4.1何謂線索二叉樹？4.2線索二叉樹的存儲結構4.3線索二叉樹的遍歷4、線索二叉樹34.1何謂線索二叉樹？為什么要線索？1）二叉樹的存儲結構中沒有反映出某結點的直接前驅結點和直接后繼結點是什么。2）二叉樹的二叉鏈表存儲結構中的那些空指針域可利用。4.1何謂線索二叉樹？為什么要線索？1）二叉樹的存儲結構中4ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA遍歷二叉樹的結果是，求得結點的一個線性序列。ABCDEFGHK例如:先序序列:中序序列:后序序列:遍歷二5ABCDEFGHK^

D^

C^^

B

E^指向該線性序列中的“前驅”和“后繼”的指針，稱作“線索”。包含“線索”的存儲結構，稱作“線索鏈表”。加上線索的二叉樹，稱作“線索二叉樹”。ABCDEFGH6lchild

ltag

data

rtag

rchild0:lchild指向該結點的左孩子1:lchild指向該結點的前驅結點0:rchild指向該結點的右孩子1:rchild指向該結點的后繼結點ltag=rtag=4.2線索二叉樹的存儲結構結點結構線索鏈表如此定義的二叉樹的存儲結構稱作“線索鏈表”。lchildltagdatartagrchild07第六章--樹和二叉樹2課件8第六章--樹和二叉樹2課件9先序線索二叉樹：先序序列為：ABCD線索二叉樹畫法先序線索二叉樹：線索二叉樹畫法10中序線索二叉樹：中序序列為：BADC中序線索二叉樹：11后序線索二叉樹：后序序列為：BDCA后序線索二叉樹：125、樹、森林與二叉樹5.1樹的三種存儲結構5.2樹、森林和二叉樹的轉換5、樹、森林與二叉樹135.1樹的三種存儲結構一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟） 存儲表示法5.1樹的三種存儲結構一、雙親表示法二、孩子鏈表表示法三、14ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、雙親表示法:ABCDEFG0A-1datapare15

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}

PTNode;

dataparent#defineMAX_TREE_SIZE100結點結構:C語言的類型描述:typedefstructPTNode{dat16typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結點的位置和結點個數(shù)

}

PTree;樹結構:typedefstruct{樹結構:17ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4

datafirstchild123456二、孩子鏈表表示法:-1000224ABCDEFG0A-1datafir18typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結點結構:

childnextC語言的類型描述:typedefstructCTNode{孩子結點結構:19

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}

CTBox;雙親結點結構

datafirstchildtypedefstruct{雙親結點結構data20typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結點數(shù)和根結點的位置

}

CTree;樹結構:typedefstruct{樹結構:21ABCDEFG

ABCEDFGroot

ABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFGAroot22typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結點結構:

firstchilddatanextsiblingtypedefstructCSNode{C語言的類型描述235.2樹、森林和二叉樹的轉換樹和二叉樹之間的對應關系

樹：兄弟關系二叉樹：雙親和右孩子樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG5.2樹、森林和二叉樹的轉換樹和二叉樹之間的對應關系AEB241.兄弟加線.樹轉換為二叉樹示例ABCDEFG1.兄弟加線.樹轉換為二叉樹示例ABCDEFG252.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG1.兄弟加線.樹轉換為二叉樹示例2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDE263.順時針轉動,使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.ABCDEFG樹轉換為二叉樹示例3.順時針轉動,使之層次分明.2.保留雙親與第一孩子連線,刪273.順時針轉動,使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.GDABECF樹轉換為二叉樹示例3.順時針轉動,使之層次分明.2.保留雙親與第一孩子連線,刪28樹轉換為二叉樹步驟⑴加線——樹中所有相鄰兄弟之間加一條連線。

⑵去線——對樹中的每個結點，只保留它與第一個孩子結點之間的連線，刪去它與其它孩子結點之間的連線。

⑶層次調整——以根結點為軸心，將樹順時針轉動一定的角度，使之層次分明。

樹轉換為二叉樹步驟⑴加線——樹中所有相鄰兄弟之間加一條連線29森林轉換為二叉樹步驟⑴將森林中的每棵樹轉換成二叉樹；⑵從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連起來后，此時所得到的二叉樹就是由森林轉換得到的二叉樹。森林轉換為二叉樹步驟⑴將森林中的每棵樹轉換成二叉樹；30二叉樹轉換為樹或森林步驟⑴加線——若某結點x是其雙親y的左孩子，則把結點x的右孩子、右孩子的右孩子、……，都與結點y用線連起來；⑵去線——刪去原二叉樹中所有的雙親結點與右孩子結點的連線；⑶

層次調整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

二叉樹轉換為樹或森林步驟⑴加線——若某結點x是其雙親y的31FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調整IHGBCDAFE二叉樹轉換為樹或森林示例FHGEAICDBFHGDCEBAIFEDCBAHGI加線去326、赫夫曼樹及其應用6.1相關概念6.2如何構造最優(yōu)二叉樹（赫夫曼樹）6.3赫夫曼樹應用——赫夫曼編碼6、赫夫曼樹及其應用6.1相關概念336.1相關概念葉子結點的權值：對葉子結點賦予的一個有意義的數(shù)值量。

二叉樹的帶權路徑長度：設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和。記為：WPL=?=nkkklw1第k個葉子的權值；從根結點到第k個葉子的路徑長度最優(yōu)二叉樹（赫夫曼樹）：在所有含n個葉子結點、并帶相同權值的二叉樹中，必存在一棵其帶權路徑長度取最小值的二叉樹，稱為“最優(yōu)二叉樹”。6.1相關概念葉子結點的權值：對葉子結點賦予的一個有意義的3427975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=735赫夫曼樹的特點：1.權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。2.只有度為0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點.

2347WPL=32WPL=41WPL=3023477423赫夫曼樹的特點：2347WPL=32366.2如何構造最優(yōu)樹赫夫曼算法基本思想：⑴初始化：由給定的n個權值{w1，w2，…，wn}構造n棵只有一個根結點的二叉樹，從而得到一個二叉樹集合F＝{T1，T2，…，Tn}；⑵選取與合并：在F中選取根結點的權值最小的兩棵二叉樹分別作為左、右子樹構造一棵新的二叉樹，這棵新二叉樹的根結點的權值為其左、右子樹根結點的權值之和；⑶刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；

⑷

重復⑵、⑶兩步，當集合F中只剩下一棵二叉樹時，這棵二叉樹便是赫夫曼樹。

6.2如何構造最優(yōu)樹赫夫曼算法基本思想：37例：W＝{2，3，4，5}

赫夫曼樹的構造過程重復第2步5432

554

9重復第3步

554

932例：W＝{2，3，4，5}赫夫曼樹的構造過程重復第2步54386.3赫夫曼樹應用——赫夫曼編碼編碼：給每一個對象標記一個二進制位串來表示一組對象。前綴編碼：一組編碼中任一編碼都不是其它任何一個編碼的前綴。前綴編碼保證了在解碼時不會有多種可能。利用赫夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。6.3赫夫曼樹應用——赫夫曼編碼編碼：給每一個對象標記一39例：一組字符{A,B,C,D,E,F,G}出現(xiàn)的頻率分別是{9,11,5,7,8,2,3}，設計最經濟的編碼方案。9523510191126871545000000111111ABDCEFG編碼方案：A：00B：10C：010D：110E：111F：0110G：0111例：一組字符{A,B,C,D,E,F,G}出現(xiàn)的40本章小結1.理解二叉樹線索化的實質是建立結點與其在相應序列中的前驅或后繼之間的直接聯(lián)系。2.熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉換方法。3.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。本章小結1.理解二叉樹線索化的實質是建立結點與其在相應序41作業(yè)：（11月5日交（一））（一）本或紙1、對于下圖所示的二叉樹，請將它轉換成森林。2、設F＝{T1,T2,T3}是森林，請畫出其對應的二叉樹。其森林如下圖所示。ABCDEFGHIJABCDEFGHJIK作業(yè)：（11月5日交（一））（一）本或紙ABCDEFGHIJ423、以數(shù)據(jù)集{2,5,7,9,13}為權值構造一棵赫夫曼樹，并計算其帶權路徑長度。（二）上機（不交）1、赫夫曼樹演示2、赫夫曼樹實驗，體會各算法運算過程3、以數(shù)據(jù)集{2,5,7,9,13}為權值構造一棵赫夫曼樹，43第六章樹和二叉樹(2)第六章樹和二叉樹(2)44主要內容樹的定義和基本術語二叉樹遍歷二叉樹線索二叉樹樹、森林與二叉樹赫夫曼樹及其應用主要內容樹的定義和基本術語454、線索二叉樹4.1何謂線索二叉樹？4.2線索二叉樹的存儲結構4.3線索二叉樹的遍歷4、線索二叉樹464.1何謂線索二叉樹？為什么要線索？1）二叉樹的存儲結構中沒有反映出某結點的直接前驅結點和直接后繼結點是什么。2）二叉樹的二叉鏈表存儲結構中的那些空指針域可利用。4.1何謂線索二叉樹？為什么要線索？1）二叉樹的存儲結構中47ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA遍歷二叉樹的結果是，求得結點的一個線性序列。ABCDEFGHK例如:先序序列:中序序列:后序序列:遍歷二48ABCDEFGHK^

D^

C^^

B

E^指向該線性序列中的“前驅”和“后繼”的指針，稱作“線索”。包含“線索”的存儲結構，稱作“線索鏈表”。加上線索的二叉樹，稱作“線索二叉樹”。ABCDEFGH49lchild

ltag

data

rtag

rchild0:lchild指向該結點的左孩子1:lchild指向該結點的前驅結點0:rchild指向該結點的右孩子1:rchild指向該結點的后繼結點ltag=rtag=4.2線索二叉樹的存儲結構結點結構線索鏈表如此定義的二叉樹的存儲結構稱作“線索鏈表”。lchildltagdatartagrchild050第六章--樹和二叉樹2課件51第六章--樹和二叉樹2課件52先序線索二叉樹：先序序列為：ABCD線索二叉樹畫法先序線索二叉樹：線索二叉樹畫法53中序線索二叉樹：中序序列為：BADC中序線索二叉樹：54后序線索二叉樹：后序序列為：BDCA后序線索二叉樹：555、樹、森林與二叉樹5.1樹的三種存儲結構5.2樹、森林和二叉樹的轉換5、樹、森林與二叉樹565.1樹的三種存儲結構一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟） 存儲表示法5.1樹的三種存儲結構一、雙親表示法二、孩子鏈表表示法三、57ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、雙親表示法:ABCDEFG0A-1datapare58

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}

PTNode;

dataparent#defineMAX_TREE_SIZE100結點結構:C語言的類型描述:typedefstructPTNode{dat59typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結點的位置和結點個數(shù)

}

PTree;樹結構:typedefstruct{樹結構:60ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4

datafirstchild123456二、孩子鏈表表示法:-1000224ABCDEFG0A-1datafir61typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結點結構:

childnextC語言的類型描述:typedefstructCTNode{孩子結點結構:62

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}

CTBox;雙親結點結構

datafirstchildtypedefstruct{雙親結點結構data63typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結點數(shù)和根結點的位置

}

CTree;樹結構:typedefstruct{樹結構:64ABCDEFG

ABCEDFGroot

ABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFGAroot65typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結點結構:

firstchilddatanextsiblingtypedefstructCSNode{C語言的類型描述665.2樹、森林和二叉樹的轉換樹和二叉樹之間的對應關系

樹：兄弟關系二叉樹：雙親和右孩子樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG5.2樹、森林和二叉樹的轉換樹和二叉樹之間的對應關系AEB671.兄弟加線.樹轉換為二叉樹示例ABCDEFG1.兄弟加線.樹轉換為二叉樹示例ABCDEFG682.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG1.兄弟加線.樹轉換為二叉樹示例2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDE693.順時針轉動,使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.ABCDEFG樹轉換為二叉樹示例3.順時針轉動,使之層次分明.2.保留雙親與第一孩子連線,刪703.順時針轉動,使之層次分明.2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.GDABECF樹轉換為二叉樹示例3.順時針轉動,使之層次分明.2.保留雙親與第一孩子連線,刪71樹轉換為二叉樹步驟⑴加線——樹中所有相鄰兄弟之間加一條連線。

⑵去線——對樹中的每個結點，只保留它與第一個孩子結點之間的連線，刪去它與其它孩子結點之間的連線。

⑶層次調整——以根結點為軸心，將樹順時針轉動一定的角度，使之層次分明。

樹轉換為二叉樹步驟⑴加線——樹中所有相鄰兄弟之間加一條連線72森林轉換為二叉樹步驟⑴將森林中的每棵樹轉換成二叉樹；⑵從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連起來后，此時所得到的二叉樹就是由森林轉換得到的二叉樹。森林轉換為二叉樹步驟⑴將森林中的每棵樹轉換成二叉樹；73二叉樹轉換為樹或森林步驟⑴加線——若某結點x是其雙親y的左孩子，則把結點x的右孩子、右孩子的右孩子、……，都與結點y用線連起來；⑵去線——刪去原二叉樹中所有的雙親結點與右孩子結點的連線；⑶

層次調整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

二叉樹轉換為樹或森林步驟⑴加線——若某結點x是其雙親y的74FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調整IHGBCDAFE二叉樹轉換為樹或森林示例FHGEAICDBFHGDCEBAIFEDCBAHGI加線去756、赫夫曼樹及其應用6.1相關概念6.2如何構造最優(yōu)二叉樹（赫夫曼樹）6.3赫夫曼樹應用——赫夫曼編碼6、赫夫曼樹及其應用6.1相關概念766.1相關概念葉子結點的權值：對葉子結點賦予的一個有意義的數(shù)值量。

二叉樹的帶權路徑長度：設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和。記為：WPL=?=nkkklw1第k個葉子的權值；從根結點到第k個葉子的路徑長度最優(yōu)二叉樹（赫夫曼樹）：在所有含n個葉子結點、并帶相同權值的二叉樹中，必存在一棵其帶權路徑長度取最小值的二叉樹，稱為“最優(yōu)二叉樹”。6.1相關概念葉子結點的權值：對葉子結點賦予的一個有意義的7727975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=778赫夫曼樹的特點：1.權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。2.只有度為0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點.

2347WPL=32WPL=41WPL=3023477423赫夫曼樹的特點：2347WPL=32796.2如何構造最優(yōu)樹赫夫曼算法基本思想：⑴初始化：由給定的n個權值{w1，w2，…，wn}構造n棵只有一個根結點的二叉樹，從而得到一個二叉樹集合F＝{T1，T2