數(shù)據(jù)結(jié)構(gòu)樹和二叉樹學(xué)習(xí)教案

會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)PPT樹和二叉樹數(shù)據(jù)結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。前面幾章主要研究的是線性結(jié)構(gòu)。一般的，線性結(jié)構(gòu)只能用來描述數(shù)據(jù)元素之間的線性順序關(guān)系，而很難反映元素之間的層次(分支)關(guān)系。本章將要討論一種非線性數(shù)據(jù)結(jié)構(gòu)，所謂非線性結(jié)構(gòu)是指在結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素，它具有兩個(gè)或兩個(gè)以上的直接后繼或直接前驅(qū)。樹形結(jié)構(gòu)，是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，它用于描述數(shù)據(jù)元素之間的層次關(guān)系。樹形結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹來形象表示。經(jīng)常用到的兩種結(jié)構(gòu)是樹和二叉樹。本章先介紹樹、二叉樹的定義、性質(zhì)及存儲(chǔ)結(jié)構(gòu)，重點(diǎn)討論二叉樹的存儲(chǔ)結(jié)構(gòu)及其各種操作，并研究樹和森林與二叉樹之間的轉(zhuǎn)換關(guān)系，最后介紹樹的應(yīng)用。

引言第1頁/共188頁內(nèi)容提要6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.6赫夫曼樹及其應(yīng)用小結(jié)第2頁/共188頁6.1樹的定義和基本術(shù)語第3頁/共188頁樹(Tree)是包含n(n≧0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：（1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；(2)當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集又是一棵樹，并稱其為子樹(Subtree)。樹也可以這樣定義：樹是由根結(jié)點(diǎn)和若干棵子樹構(gòu)成的?？梢钥闯?，在樹的定義中用了遞歸的概念，即在樹的定義中又用到樹的定義，它道出了樹的固有特性，因此遞歸算法是樹結(jié)構(gòu)算法的顯著特點(diǎn)。

樹的定義第4頁/共188頁上圖(a)是只有一個(gè)根結(jié)點(diǎn)的樹；圖(b)是有13個(gè)結(jié)點(diǎn)的樹，其中A是根，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集：T1={B，E，F(xiàn)，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1、T2和T3都是根A的子樹，且本身也是一棵樹。例如T1，其根為B，其余結(jié)點(diǎn)分為兩個(gè)互不相交的子集；T11={E，K，L}，T12={F}。T11和T12都是B的子樹。而T11中E是根結(jié)點(diǎn)，{K}和{L}是E的兩棵互不相交的子樹，其本身又是只有一個(gè)根結(jié)點(diǎn)的樹。第5頁/共188頁數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；

(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關(guān)系R：ADTTree{第6頁/共188頁

基本操作：查找類

插入類刪除類第7頁/共188頁

Root(T)//求樹的根結(jié)點(diǎn)

查找類：Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值

Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷第8頁/共188頁InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結(jié)點(diǎn)p的第i棵子樹第9頁/共188頁

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹第10頁/共188頁樹的表示方法有四種，各用于不同的目的。(1)直觀表示法：就是一棵樹的直觀表示。(2)廣義表示法：下圖(a)是以廣義表的形式表示的，根作為由子樹森林組成的表的名字寫在表的左邊。樹的形式化表示法主要用于樹的理論描述。(3)凹入表示法：下圖(b)用的是凹入表示法(類似書的編目)。樹的凹入表示法主要用于樹的屏幕和打印顯示。(4）嵌套集合表示法：參見P120圖6.2。表示方法的多樣性，正說明了樹結(jié)構(gòu)在日常生活中及計(jì)算機(jī)程序設(shè)計(jì)中的重要性。一般來說，分等級的分類方案都可用層次結(jié)構(gòu)來表示，也就是說，都可產(chǎn)生一個(gè)樹結(jié)構(gòu)。

樹的表示形式第11頁/共188頁ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:第12頁/共188頁第13頁/共188頁基本術(shù)語第14頁/共188頁結(jié)點(diǎn):結(jié)點(diǎn)的度:樹的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素及若干指向子樹的分支擁有的子樹數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM第15頁/共188頁(從根到結(jié)點(diǎn)的)路徑：結(jié)點(diǎn)的層次:樹的深度：

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次孩子結(jié)點(diǎn)：結(jié)點(diǎn)子樹的根雙親結(jié)點(diǎn)：孩子結(jié)點(diǎn)的直接前驅(qū)兄弟結(jié)點(diǎn)：同一雙親的孩子間堂兄弟：雙親在同一層的結(jié)點(diǎn)祖先結(jié)點(diǎn)：從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)第16頁/共188頁(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。第17頁/共188頁任何一棵非空樹是一個(gè)二元組

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點(diǎn)

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF第18頁/共188頁對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)第19頁/共188頁~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點(diǎn)

(無前驅(qū))最后一個(gè)數(shù)據(jù)元素

(無后繼)多個(gè)葉子結(jié)點(diǎn)

(無后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)第20頁/共188頁6.2

二叉樹第21頁/共188頁6.2.1二叉樹的定義

二叉樹（BinaryTree）或?yàn)榭諛?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹第22頁/共188頁二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹第23頁/共188頁抽象數(shù)據(jù)類型二叉數(shù)定義ADTBinaryTree｛數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：

若D=

，則R=

，稱BinaryTree為空二叉樹;

若D≠

，則R={H}，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

(2)若D－{root｝≠φ，則存在D－｛root｝={DL，Dr},DL∩Dr=φ

，

(3)若DL

≠φ,則DL存在唯一的數(shù)據(jù)元素xL，有<root,xL>

H;且存在DL上的關(guān)系HL

H；若Dr≠φ，則Dr存在唯一的數(shù)據(jù)元素xr，有<root,xr>

H;且存在Dr上的關(guān)系Hr

H,H=｛<root,xL>，<root,xr>,HL,Hr｝;(4)（DL,{HL}）是一棵符合本定義的二叉樹，稱為根root的左子樹，（Dr,{Hr}）是一棵符合本定義的二叉樹，稱為根root的右子樹，第24頁/共188頁二叉樹的主要基本操作：查找類插入類刪除類第25頁/共188頁

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());第26頁/共188頁

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);第27頁/共188頁ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);第28頁/共188頁6.2.2二叉樹

的性質(zhì)第29頁/共188頁

性質(zhì)1：

在二叉樹的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時(shí)，只有一個(gè)根結(jié)點(diǎn)：

2i-1=20=1；假設(shè)對所有的j，1≤j

i，命題成立；二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-2

2=2i-1

。第30頁/共188頁性質(zhì)2：

深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)（k≥1）。證明：

基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為

20+21+

+2k-1=2k-1

。第31頁/共188頁

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為

2

的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。第32頁/共188頁兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號為1至n的結(jié)點(diǎn)一一對應(yīng)。123456789101112131415abcdefghij第33頁/共188頁性質(zhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n

+1。證明：設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1≤n<2k

即

k-1≤log2n<k

因?yàn)閗只能是整數(shù)，因此，k=log2n

+1。第34頁/共188頁性質(zhì)5：若對含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1

至n

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

的結(jié)點(diǎn)：

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

i/2

的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；

(2)若2i>n，則該結(jié)點(diǎn)無左孩子，

否則，編號為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1>n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，

否則，編號為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。第35頁/共188頁第36頁/共188頁6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一、二叉樹的順序存儲(chǔ)結(jié)構(gòu)第37頁/共188頁#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;一、二叉樹的順序存儲(chǔ)結(jié)構(gòu)第38頁/共188頁按照順序存儲(chǔ)結(jié)構(gòu)的定義，在此約定，用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)二叉樹上的結(jié)點(diǎn)元素。因此，必須把結(jié)點(diǎn)安排成一個(gè)適當(dāng)?shù)木€性序列，使得結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。在一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上層到下層，每層從左到右地給結(jié)點(diǎn)編號，就能得到一個(gè)足以反映整個(gè)二叉樹結(jié)構(gòu)的線性序列，如下圖所示。二叉樹的順序存儲(chǔ)結(jié)構(gòu)第39頁/共188頁第40頁/共188頁第41頁/共188頁第42頁/共188頁練習(xí):ABCDEF

ABDCEF

0123456789101112131401326第43頁/共188頁二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表第44頁/共188頁ADEBCF

rootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表二叉鏈表第45頁/共188頁ABCDEF二叉樹第46頁/共188頁typedefstruct

BiTNode

{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:第47頁/共188頁ADEBCF

root

2．三叉鏈表parent

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):第48頁/共188頁

typedefstruct

TriTNode

{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指針

structTriTNode

*parent;//雙親指針

}TriTNode,*TriTree;parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:第49頁/共188頁0123456dataparent結(jié)點(diǎn)結(jié)構(gòu):3．雙親鏈表LRTagLRRRL第50頁/共188頁

typedefstruct

BPTNode

{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

int

*parent;//指向雙親的指針

charLRTag;//左、右孩子標(biāo)志域

}BPTNode

typedefstructBPTree{//樹結(jié)構(gòu)

BPTNodenodes[MAX_TREE_SIZE];

intnum_node;//結(jié)點(diǎn)數(shù)目

introot;//根結(jié)點(diǎn)的位置

}BPTree第51頁/共188頁6.3.1二叉樹的遍歷6.3遍歷二叉樹和線索二叉樹第52頁/共188頁一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、中序遍歷算法的非遞歸描述五、遍歷算法的應(yīng)用舉例第53頁/共188頁

如何按著某條搜索路徑巡訪二叉樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。一、問題的提出“訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。第54頁/共188頁

“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，

每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。第55頁/共188頁二叉樹的遍歷方法二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：L：遍歷左子樹

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

R：遍歷右子樹

有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD約定先左后右,有三種遍歷方法：

DLR、LDR、LRD

，分別稱為

先序遍歷、中序遍歷、后序遍歷

A

F

G

E

D

C

B第56頁/共188頁58

先序遍歷（

DLR

）

若二叉樹非空（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹；

先序遍歷序列：

A

F

G

E

D

C

B例：先序遍歷右圖所示的二叉樹（1）訪問根結(jié)點(diǎn)A（2）先序遍歷左子樹：即按DLR的順序遍歷左子樹（3）先序遍歷右子樹：即按DLR的順序遍歷右子樹ABCDFGE二、先左后右的遍歷算法第57頁/共188頁59中序遍歷（

LDR

）若二叉樹非空（1）中序遍歷左子樹（2）訪問根結(jié)點(diǎn)（3）中序遍歷右子樹

中序遍歷序列：

A

F

G

E

D

C

B例：中序遍歷右圖所示的二叉樹（1）中序遍歷左子樹：即按LDR的順序遍歷左子樹

（2）訪問根結(jié)點(diǎn)A（3）中序遍歷右子樹：即按LDR的順序遍歷右子樹DBCGFAE第58頁/共188頁60后序遍歷（LRD）若二叉樹非空（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根結(jié)點(diǎn)

后序遍歷序列：例：后序遍歷右圖所示的二叉樹（1）后序遍歷左子樹：即按LRD的順序遍歷左子樹

（2）后序遍歷右子樹：即按LRD的順序遍歷右子樹（3）訪問根結(jié)點(diǎn)A

A

F

G

E

D

C

BDGCEAFB第59頁/共188頁61

e

d

c

b

f

a

+

*

/

-

-

后序遍歷序列：

中序遍歷序列：

先序遍歷序列：例：先中序遍歷序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹前綴表達(dá)式中綴表達(dá)式后綴表達(dá)式-+a*b-cd/efa+b*c-d-e/fabcd-*+ef/-第60頁/共188頁R^A^DE^^C^H^F^G^B^K^^練習(xí)：求下列二叉鏈表和二叉樹的三種遍歷次序ABCDEFGHK第61頁/共188頁這實(shí)際上是先序遍歷的遞歸定義，我們知道遞歸定義包括兩個(gè)部分：1）基本項(xiàng)（也叫終止項(xiàng)）；2）遞歸項(xiàng)

若二叉樹非空（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹（3）先序遍歷右子樹；先序遍歷遞歸定義遞歸項(xiàng)上面介紹了三種遍歷方法，顯然是用遞歸的方式給出的三種遍歷方法，以先序?yàn)槔合刃虮闅v（DLR）的定義：該定義隱含著若二叉樹為空，結(jié)束三、算法的遞歸描述第62頁/共188頁上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束——基本項(xiàng)（也叫終止項(xiàng)）若二叉樹非空——遞歸項(xiàng)

（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹（3）先序遍歷右子樹；

下面給出先序、中序、后序遍歷遞歸算法，為了增加算法的可讀性，這里對書上算法作了簡化，沒有考慮訪問結(jié)點(diǎn)出錯(cuò)的情況（即我們假設(shè)調(diào)用函數(shù)visit()訪問結(jié)點(diǎn)總是成功的。第63頁/共188頁先序遍歷遞歸算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉鏈表存貯二叉樹，visit()是訪問結(jié)點(diǎn)的函數(shù)。本算法//先序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)//Visit()

if(T){//若二叉樹為空，結(jié)束返回

//若二叉樹不為空，訪問根結(jié)點(diǎn)；遍歷左子樹，遍歷右子樹Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse最簡單的Visit函數(shù)是：

StatusPrintElement(TElemTypee){//輸出元素e的值

printf(e);returnOK;}

∧D

A

B

C

∧∧E

∧F∧T第64頁/共188頁2中序遍歷遞歸算法

voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹，visit()是訪問結(jié)點(diǎn)的函數(shù)。本算法中序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit()

if(T){//若二叉樹為空，結(jié)束返回

//若二叉樹不為空，遍歷左子樹，訪問根結(jié)點(diǎn)，遍歷右子樹

InOrderTraverse(T->lchild,Visit);Visit(T->data)；

InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse你能寫出后序遍歷遞歸算法了吧?第65頁/共188頁3后序遍歷遞歸算法

voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹，visit()是訪問結(jié)點(diǎn)的函數(shù)。本算法中序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit()

if(T){//若二叉樹為空，結(jié)束返回

//若二叉樹不為空，遍歷左子樹，遍歷右子樹，訪問根結(jié)點(diǎn)

PostOrderTraverse(T->lchild,Visit);

PostOrderTraverse(T->rchild,Visit);Visit(T->data)；

}//PostOrderTraverse第66頁/共188頁任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為二叉樹的包線，這條包線對于理解二叉樹的遍歷過程很有用。GHDEFBCA第67頁/共188頁四、中序遍歷算法的非遞歸描述StatusInOrderTraverse(BiTreeT,Status(*Visit)(ElemType)){//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用//函數(shù).中序遍歷二叉樹T的非遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)//用函數(shù)Visit。

InitStack(S);Push(S,T);//根指針進(jìn)棧

while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到盡頭

Pop(S,p);//空指針退棧

if(!StackEmpty(S)){//訪問結(jié)點(diǎn)，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR;Push(S,p->rchild);}}returnOK;}//InOrderTraverse第68頁/共188頁StatusInOrderTraverse(BiTreeT,Status(*Visit)(ElemType)){//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用//函數(shù)。中序遍歷二叉樹T的非遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)//用函數(shù)Visit。

InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}//非空指針進(jìn)棧，繼續(xù)左進(jìn)

else{//上層指針退棧，訪問其所指結(jié)點(diǎn)，再向右進(jìn)

Pop(S,p);if(!Visit(p->data))returnERROR;p=p->rchild;}}returnOK;}//InOrderTraverse第69頁/共188頁中序遍歷二叉樹的非遞歸算法

示意圖CBDFAGEABCDGEFABCNULLSGetTop<--pAS

PoppCBDFA第70頁/共188頁五、遍歷算法的應(yīng)用舉例1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)

(先序遍歷)2、求二叉樹的深度(后序遍歷)3、復(fù)制二叉樹(后序遍歷)4、建立二叉樹的存儲(chǔ)結(jié)構(gòu)第71頁/共188頁1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想:

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增1。第72頁/共188頁void

CountLeaf

(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;//對葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf第73頁/共188頁2、求二叉樹的深度(后序遍歷)算法基本思想:

從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為：求得左、右子樹深度的最大值，然后加1。

首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。第74頁/共188頁int

Depth(BiTreeT){//返回二叉樹的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}第75頁/共188頁3、復(fù)制二叉樹其基本操作為：生成一個(gè)結(jié)點(diǎn)。根元素T左子樹右子樹根元素NEWT左子樹右子樹左子樹右子樹(后序遍歷)第76頁/共188頁BiTNode

*GetTreeNode(TElemTypeitem,

BiTNode

*lptr,BiTNode*rptr){

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

T->data=item;

T->lchild=lptr;T->rchild=rptr;

returnT;}

生成一個(gè)二叉樹的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr)第77頁/共188頁BiTNode

*CopyTree(BiTNode*T){

if(!T)returnNULL;

if(T->lchild)

newlptr=CopyTree(T->lchild);//復(fù)制左子樹

elsenewlptr=NULL;

if(T->rchild)

newrptr=CopyTree(T->rchild);//復(fù)制右子樹

elsenewrptr=NULL;

newT=GetTreeNode(T->data,newlptr,newrptr);

returnnewT;}//CopyTree第78頁/共188頁ABCDEFGHK^D^C^^B^H^^K^G^F^E^A例如：下列二叉樹的復(fù)制過程如下：newT第79頁/共188頁4、建立二叉樹的存儲(chǔ)結(jié)構(gòu)

為二叉樹建立二叉鏈表

輸入：二叉樹的先序序列

結(jié)果：二叉樹的二叉鏈表

遍歷操作訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次。是否可在利用遍歷，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接？基本思想：輸入（在空子樹處添加*的二叉樹的）先序序列（設(shè)每個(gè)元素是一個(gè)字符）按先序遍歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接第80頁/共188頁∧D

A

B

∧C

∧∧E

∧∧F

∧T

先序序列：ABDFCE（在空子樹處添加*的二叉樹的）先序序列：ABD*F***CE***

A

F

E

D

C

B*******

A

F

E

D

C

B第81頁/共188頁StatusCreateBiTree(BiTree&T){//輸入（在空子樹處添加*的二叉樹的）先序序列（設(shè)每個(gè)元//素是一個(gè)字符）按先序遍歷的順序，建立二叉鏈表，并將//該二叉鏈表根結(jié)點(diǎn)指針賦給Tscanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’則T=NULL返回

else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;//建立（根）結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹

CreateBiTree(T->rchild);//構(gòu)造右子樹

}returnOK;}//CreateBiTree第82頁/共188頁84

分析：若二叉樹的任意兩個(gè)結(jié)點(diǎn)的值都不相同，則二叉樹的前序序列和中序序列能唯一確定一棵二叉樹。另外，由前序序列和中序序列的定義可知，前序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn)，而在中序序列中，根結(jié)點(diǎn)剛好是左、右子樹的分界點(diǎn)，因此，可按如下方法建立二叉樹：由二叉樹的先序和中序序列建立二叉樹二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根第83頁/共188頁851.用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn);2.在中序序列中查找根結(jié)點(diǎn)的位置，并以此為界將中序序列劃分為左、右兩個(gè)序列(左、右子樹);3.根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是左、右子樹的前序序列;4.對左、右子樹的前序序列和中序序列遞歸地實(shí)施同樣方法，直到所得左、右子樹為空。假設(shè)前序序列為ABDGHCEFI，中序序列為GDHBAECIF，則得到的二叉樹如下頁所示第84頁/共188頁861.A為根結(jié)點(diǎn)ABDGHCEFIGDHBAECIFBDGHCEFIA2.B為左子樹的根結(jié)點(diǎn)BDGHGDHBCEFIDHGBA3.D為左子樹的左子樹的根結(jié)點(diǎn)第85頁/共188頁874.C為右子樹的根結(jié)點(diǎn)5.F為右子樹的右子樹的根結(jié)點(diǎn)CEFIECIF第86頁/共188頁abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列第87頁/共188頁練習(xí)：已知結(jié)點(diǎn)的先序序列和中序序列，求整棵二叉樹。先序序列：ABCDEFG中序序列：CBEDAFGAC

B

E

DFGABCDEFGABCFDEG第88頁/共188頁6.3.2

線索二叉樹

線索二叉樹的定義線索的描述建立線索二叉樹線索二叉樹上的運(yùn)算第89頁/共188頁遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA一、線索二叉樹的定義第90頁/共188頁

在這樣的線性序列中，很容易求得某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼。然而，有時(shí)我們希望不進(jìn)行遍歷就能快速找到某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼，這樣，就應(yīng)該把每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼記錄下來。為了做到這一點(diǎn)，可以在原來的二叉鏈表結(jié)點(diǎn)中，再增加兩個(gè)指針域，一個(gè)指向前驅(qū)，一個(gè)指向后繼，但這樣做將會(huì)浪費(fèi)大量存貯單元，存貯空間的利用率相當(dāng)?shù)?一個(gè)結(jié)點(diǎn)中有4個(gè)指針，1個(gè)指左孩子，1個(gè)指右孩子，1個(gè)指前驅(qū)，1個(gè)指后繼)，而原來的左、右孩子域有許多空指針又沒有利用起來。為了不浪費(fèi)存貯空間，我們利用原有的孩子指針為空時(shí)來存放直接前驅(qū)和后繼，這樣的指針稱為“線索”，加線索的過程稱為線索化，加了線索的二叉樹，稱為線索二叉樹，對應(yīng)的二叉鏈表稱為線索二叉鏈表。一、線索二叉樹的定義第91頁/共188頁指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”加了線索的二叉樹，稱作“線索二叉樹”包含“線索”的二叉鏈表，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^第92頁/共188頁

在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼。但是，我們怎樣來區(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅(qū)或直接后繼信息呢?為此，在二叉鏈表結(jié)點(diǎn)中，還必須增加兩個(gè)標(biāo)志域ltag、rtag。

ltag和rtag定義如下：

0lchild域指向結(jié)點(diǎn)的左孩子ltag=1lchild域指向結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)

0rchild域指向結(jié)點(diǎn)的右孩子rtag=1rchild域指向結(jié)點(diǎn)在某種遍歷下的直接后繼

第93頁/共188頁

這樣，二叉鏈表中每個(gè)結(jié)點(diǎn)還是有5個(gè)域，但其中只有2個(gè)指針，較原來的4個(gè)指針要方便。增加線索后的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)可描述如下：第94頁/共188頁typedefstruct

BiThrNod{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指針

PointerThrLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;二、線索的描述：1、類型定義：typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索第95頁/共188頁2．線索的畫法

在二叉樹或二叉鏈表中，若左孩子為空，則畫出它的直接前驅(qū)，右孩子為空時(shí)，則畫出它的直接后繼，左右孩子不為空時(shí)，不需畫前驅(qū)和后繼。這樣就得到了線索二叉樹或線索二叉鏈表。第96頁/共188頁先序序列為：ABCD第97頁/共188頁中序序列為：BADC第98頁/共188頁后序序列為：BDCA第99頁/共188頁ABCDE第100頁/共188頁ABCDEABDCET先序序列：ABCDE先序線索二叉鏈表00001111^11第101頁/共188頁ABCDEABDCET中序序列：BCAED中序線索二叉鏈表00001111^11^第102頁/共188頁ABCDEABDCET后序序列：CBEDA后序線索二叉鏈表0000111111^第103頁/共188頁ABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉鏈表

0

1頭結(jié)點(diǎn)：ltag=0,lchild指向根結(jié)點(diǎn)rtag=1,rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的lchild域和最后一個(gè)結(jié)點(diǎn)的rchild域都指向頭結(jié)點(diǎn)ABDCET中序序列：BCAED中序線索二叉鏈表00001111^11^第104頁/共188頁

建立線索二叉樹，或者說對二叉樹線索化，實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，訪問結(jié)點(diǎn)的操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過程，設(shè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便增設(shè)線索。此外，在對一棵二叉樹加線索時(shí)，必須首先申請一個(gè)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹的根結(jié)點(diǎn)的指向關(guān)系，對二叉樹線索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索。

三、建立線索二叉樹第105頁/共188頁void

InThreading(BiThrTreep)

{

if(p){//對以p為根的非空二叉樹進(jìn)行線索化

InThreading(p->lchild);

//左子樹線索化

if(!p->lchild)//建前驅(qū)線索

{p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=p;}

pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);

//右子樹線索化

}//if}//InThreading第106頁/共188頁StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//構(gòu)建中序線索鏈表

if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加頭結(jié)點(diǎn)

returnOK;}//InOrderThreading

……第107頁/共188頁if(!T)

Thrt->lchild=Thrt;

else{Thrt->lchild=T;

pre=Thrt;InThreading(T);

pre->rchild=Thrt;//處理最后一個(gè)結(jié)點(diǎn)

pre->RTag=Thread;

Thrt->rchild=pre;

}第108頁/共188頁四、線索二叉樹上的運(yùn)算1．線索二叉樹上的查找

（1）查找指定結(jié)點(diǎn)在中序線索二叉樹中的的直接后繼

若所找結(jié)點(diǎn)右標(biāo)志rtag=1，則右孩子域指向中序后繼，否則，中序后繼應(yīng)為遍歷右子樹時(shí)的第一個(gè)訪問結(jié)點(diǎn),即右子樹中最左下的結(jié)點(diǎn)（參見下圖）。從下圖中可知，x的后繼為xk

。第109頁/共188頁（2）查找指定結(jié)點(diǎn)在中序線索二叉樹中的的直接前驅(qū)

若所找結(jié)點(diǎn)左標(biāo)志ltag=1，則左孩子域指向中序前驅(qū)，否則，中序前驅(qū)應(yīng)為遍歷左子樹時(shí)的最后一個(gè)訪問結(jié)點(diǎn)，即左子樹中最右下的結(jié)點(diǎn)（參見下圖）。從下圖中可知，x的前驅(qū)為xk

。第110頁/共188頁

(3)查找指定點(diǎn)在先序線索二叉樹中的直接后繼

先序后繼的查找比較方便，若Ｐ無左孩子，右孩子為后繼，否則左孩子為后繼。

(4)查找指定結(jié)點(diǎn)在后序線索二叉樹中的直接前驅(qū)

后序前驅(qū)的查找也比較方便，若左孩子為空，左鏈指前驅(qū)，否則，若右子樹為空，左孩子為前驅(qū)，否則右孩子為前驅(qū)。

求后序后繼和先序前驅(qū)都比較麻煩，在此不再作進(jìn)一步介紹。第111頁/共188頁2．線索二叉樹上的遍歷

遍歷某種次序的線索二叉樹，只要從該次序下的開始結(jié)點(diǎn)出發(fā)，反復(fù)找到結(jié)點(diǎn)在該次序下的后繼，直到后繼為空。這對于中序線索和前序線索二叉樹很方便，但對于后序線索二叉樹較麻煩(因求后序后繼較麻煩)。故后序線索對于遍歷沒有什么意義。第112頁/共188頁中序線索鏈表的遍歷算法

※中序遍歷的第一個(gè)結(jié)點(diǎn)？

※在中序線索化鏈表中結(jié)點(diǎn)的后繼？左子樹上處于“最左下”（沒有左子樹）的結(jié)點(diǎn)。若無右子樹，則為后繼線索所指結(jié)點(diǎn)；否則為對其右子樹進(jìn)行中序遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)。第113頁/共188頁voidInOrderTraverse_Thr(BiThrTreeT,

void(*Visit)(TElemTypee)){p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T){//空樹或遍歷結(jié)束時(shí)，p==Twhile(p->LTag==Link)p=p->lchild;//第一個(gè)結(jié)點(diǎn)

if(!Visit(p->data))returnERROR;

while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//訪問后繼結(jié)點(diǎn)

}p=p->rchild;//p進(jìn)至其右子樹根

}}//InOrderTraverse_Thr第114頁/共188頁

從上面算法可知，線索二叉樹上的遍歷較一般二叉樹要方便得多。但是這種方便是以增加線索為代價(jià)的，增加線索本身要花費(fèi)大量時(shí)間。所以二叉樹是以二叉鏈表表示，還是以線索二叉鏈表示，可根據(jù)具體問題而定。3．線索二叉樹的插入和刪除

線索二樹上的查找、遍歷都較一般二叉樹方便，但線索二叉樹也存在其缺點(diǎn)，就插入和刪除運(yùn)算而言，線索二叉樹比一般二叉樹的時(shí)間花費(fèi)大，因?yàn)槌薷闹羔樛猓€要修改相應(yīng)線索。線索二叉樹的扦入和刪除較麻煩，因此本書不再介紹算法第115頁/共188頁

6.4樹和森林

第116頁/共188頁6.4.1樹的存儲(chǔ)結(jié)構(gòu)一、雙親表示法二、孩子表示法三、孩子-兄弟（樹的二叉鏈表）存儲(chǔ)表示法第117頁/共188頁

它是以一組地址連續(xù)的存儲(chǔ)單元來存放樹中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有兩個(gè)域：一個(gè)是data域，存放結(jié)點(diǎn)信息，另一個(gè)是parent域，用來存放雙親的位置(指針)。該結(jié)構(gòu)的具體描述見下圖。

一、雙親表示法:第118頁/共188頁ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6dataparent例:第119頁/共188頁

typedefstructPTNode{TElemTypedata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述:第120頁/共188頁typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹結(jié)構(gòu):第121頁/共188頁

將一個(gè)結(jié)點(diǎn)所有孩子鏈接成一個(gè)單鏈表，而樹中有若干個(gè)結(jié)點(diǎn)，故有若干個(gè)單鏈表，每個(gè)單鏈表有一個(gè)表頭結(jié)點(diǎn)，所有表頭結(jié)點(diǎn)用一個(gè)數(shù)組來描述，具體描述參見下圖

二、孩子表示法:第122頁/共188頁typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextC語言的類型描述:第123頁/共188頁

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

}CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)

datafirstchild第124頁/共188頁typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}CTree;樹結(jié)構(gòu):第125頁/共188頁

雙親孩子表示法

將第1、2兩種方法結(jié)合起來，則得到雙親孩子表示法，具體參見下圖。第126頁/共188頁ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6datafirstchild123456例:-1000224第127頁/共188頁

類似于二叉鏈表，但第一個(gè)鏈指向第一個(gè)孩子，第二個(gè)鏈指向下一個(gè)兄弟。將左圖的樹用孩子兄弟表示法表示，見右圖。三、孩子-兄弟（樹的二叉鏈表）表示法第128頁/共188頁ABCDEFGABCEDFGrootABCEDFG

例第129頁/共188頁typedefstructCSNode{ElemTypedata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsibling第130頁/共188頁1．樹轉(zhuǎn)換成二叉樹可以分為三步：（1）

連線指相鄰兄弟之間連線。（2）

抹線指抹掉雙親與除左孩子外其它孩子之間的連線。

（3）

旋轉(zhuǎn)只需將樹作適當(dāng)?shù)男D(zhuǎn)。

具體實(shí)現(xiàn)過程見下圖。

6.4.2森林與二叉樹的轉(zhuǎn)換第131頁/共188頁第132頁/共188頁2．森林轉(zhuǎn)換成二叉樹

（1）將森林中每一棵樹分別轉(zhuǎn)換成二叉樹

這在剛才的樹轉(zhuǎn)換成二叉樹中已經(jīng)介紹過。（2）合并

使第n棵樹接入到第n-1棵的右邊并成為它的右子樹，第n-1棵二叉樹接入到第n-2棵的右邊并成為它的右子樹，…，第2棵二叉樹接入到第1棵的右邊并成為它的右子樹，直到最后剩下一棵二叉樹為止。第133頁/共188頁第134頁/共188頁3．二叉樹還原成樹或森林

（1）右鏈斷開

將二叉樹的根結(jié)點(diǎn)的右鏈及右鏈的右鏈等全部斷開，得到若干棵無右子樹的二叉樹。具體操作見下圖(b)。

（2）二叉樹還原成樹

將（1）中得到的每一棵二叉樹都還原成樹（與樹轉(zhuǎn)換成二叉樹的步驟剛好相反）。具體操作步驟見下圖(c)。

第135頁/共188頁第136頁/共188頁6.4.3樹和森林的遍歷第137頁/共188頁一、樹的遍歷二、森林的遍歷第138頁/共188頁樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。

若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。

若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。第139頁/共188頁ABCDEFGHIJK

先根遍歷時(shí)頂點(diǎn)的訪問次序：

后根遍歷時(shí)頂點(diǎn)的訪問次序：

層次遍歷時(shí)頂點(diǎn)的訪問次序：KJIHGFBCDEAADGHKCFIJBEKJIHGDBEFCA第140頁/共188頁

BCDEFGHIJK1．森林中第一棵樹的根結(jié)點(diǎn)；2．森林中第一棵樹的子樹森林；3．森林中其它樹構(gòu)成的森林。森林由三部分構(gòu)成：第141頁/共188頁1.先序遍歷森林的遍歷

若森林不空，則訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進(jìn)行先根遍歷。第142頁/共188頁２．中序遍歷

若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷森林中(除第一棵樹之外)其

余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進(jìn)行后根遍歷。第143頁/共188頁

樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷第144頁/共188頁6.6赫夫曼樹

及其應(yīng)用

最優(yōu)二叉樹（赫夫曼樹）

如何構(gòu)造赫夫曼樹赫夫曼編碼

第145頁/共188頁6.6.1最優(yōu)二叉樹（赫夫曼樹）

1．路徑和路徑長度

在二叉樹中，一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。在路徑上的分支數(shù)目被稱為路徑長度。

樹的路徑長度是從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和

2．結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度

若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。

結(jié)點(diǎn)的帶權(quán)路徑長度為：從該結(jié)點(diǎn)到樹根之間的的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。

第146頁/共188頁

3．樹的帶權(quán)路徑長度

樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為wpl=，其中n為葉子結(jié)點(diǎn)數(shù)目，wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li

為第i個(gè)葉子結(jié)點(diǎn)的路徑長度。

4．赫夫曼樹的定義

假設(shè)有n個(gè)權(quán)值{w1，w2，…，wn}，試構(gòu)造一棵有n個(gè)葉子的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi，則其中帶權(quán)路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹。第147頁/共188頁下面我們討論一下權(quán)值、樹形與帶權(quán)的路徑長度之間的關(guān)系。假設(shè)有6個(gè)權(quán)值分別為{3，6，9，10，7，11}，以這6個(gè)權(quán)值作為葉子結(jié)點(diǎn)的權(quán)值可以構(gòu)造出下面三棵二叉樹。第148頁/共188頁36791011(a)這棵二叉樹的帶權(quán)路徑長度為：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117第149頁/共188頁11109763(b)這棵二叉樹的帶權(quán)路徑長度為：WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177第150頁/共188頁11103679(c)這棵二叉樹的帶權(quán)路徑長度為：WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158第151頁/共188頁WPL(T)=72+52+22+42=36WPL(T)=71+52+23+43=35WPL(T)=73+53+42+21=46第152頁/共188頁

根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合

F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空樹；5、如何構(gòu)造赫夫曼樹(1)(赫夫曼算法)以二叉樹為例：第153頁/共188頁

在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；(2)第154頁/共188頁

從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹；

重復(fù)

(2)

和

(3)

兩步，直至F中只含一棵樹為止。(3)(4)第155頁