數(shù)據(jù)結(jié)構(gòu)（Java語言實(shí)現(xiàn)） 課件 陳銳 第5、6章 樹和二叉樹、圖

第5章樹和二叉樹結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS5.1

樹的定義和抽象數(shù)據(jù)類型5.2二叉樹的定義、性質(zhì)5.3二叉樹的遍歷5.6并查集5.4二叉樹的線索化5.5樹、森林與二叉樹5.7哈夫曼樹5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。樹（Tree）是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。其中，當(dāng)n=0時(shí)，稱為空樹。當(dāng)n>0時(shí)，稱為非空樹，該集合滿足以下條件：（1）有且只有一個(gè)稱為根（root）的結(jié)點(diǎn)。（2）當(dāng)n>1時(shí)，其余n-1個(gè)結(jié)點(diǎn)可以劃分為m個(gè)有限集合T1、T2、…、Tm，且這m個(gè)有限集合不相交，其中Ti（1≤i≤m）又是一棵樹，稱為根的子樹。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。圖5.1給出了一棵樹的邏輯結(jié)構(gòu)，它如同一棵倒立的樹。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。樹的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹分支的信息。結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有子樹的個(gè)數(shù)稱為結(jié)點(diǎn)的度。例如，結(jié)點(diǎn)C有3個(gè)子樹，度為3。葉子結(jié)點(diǎn)：也稱為終端結(jié)點(diǎn)，沒有子樹的結(jié)點(diǎn)也就是度為零的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。分支結(jié)點(diǎn)：也稱為非終端結(jié)點(diǎn)，度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)。孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。雙親結(jié)點(diǎn)：也稱父結(jié)點(diǎn)，如果一個(gè)結(jié)點(diǎn)存在孩子結(jié)點(diǎn)，則該結(jié)點(diǎn)就稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。子孫結(jié)點(diǎn)：在一個(gè)根結(jié)點(diǎn)的子樹中的任何一個(gè)結(jié)點(diǎn)都稱為該根結(jié)點(diǎn)的子孫結(jié)點(diǎn)。例如，{G,H,I,M,N}是C的子樹，子樹中的結(jié)點(diǎn)G、H、I、M和N都是C的子孫結(jié)點(diǎn)。祖先結(jié)點(diǎn)：從根結(jié)點(diǎn)開始到達(dá)一個(gè)結(jié)點(diǎn)，所經(jīng)過的所有分支結(jié)點(diǎn)，都稱為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。例如，N的祖先結(jié)點(diǎn)為A、C和I。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。兄弟結(jié)點(diǎn)：一個(gè)雙親結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)之間互相稱為兄弟結(jié)點(diǎn)。例如，E和F是B的孩子結(jié)點(diǎn)，因此，E和F互為兄弟結(jié)點(diǎn)。樹的度：樹中所有結(jié)點(diǎn)的度的最大值。例如，圖5.1中右邊的樹的度為3，因?yàn)榻Y(jié)點(diǎn)C的度為3，該結(jié)點(diǎn)的度是樹中擁有最大的度的結(jié)點(diǎn)。結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始，根結(jié)點(diǎn)為第一層，根結(jié)點(diǎn)的孩子結(jié)點(diǎn)為第二層，依此類推，如果某一個(gè)結(jié)點(diǎn)是第L層，則其孩子結(jié)點(diǎn)位于第L+1層。5.1樹的定義和抽象數(shù)據(jù)類型5.1.1樹的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。樹的深度：也稱為樹的高度，樹中所有結(jié)點(diǎn)的層次最大值稱為樹的深度。例如，圖5.1中右邊的樹的深度為4。有序樹：如果樹中各個(gè)子樹的次序是有先后次序的，則稱該樹為有序樹。無序樹：如果樹中各個(gè)子樹的次序是沒有先后次序，則稱該樹為無序樹。森林：m棵互不相交的樹構(gòu)成一個(gè)森林。如果把一棵非空的樹的根結(jié)點(diǎn)刪除，則該樹就變成了一個(gè)森林，森林中的樹由原來的根結(jié)點(diǎn)各個(gè)子樹構(gòu)成。5.1樹的定義和抽象數(shù)據(jù)類型5.1.2樹的邏輯表示唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。（1）樹形表示法。（2）文氏圖表示法。（3）廣義表表示法。(A(B(E(K,L),F),C(G(M),H,I(N)),D(J)))（4）凹入表示法。5.1樹的定義和抽象數(shù)據(jù)類型5.1.3樹的抽象數(shù)據(jù)類型唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。ADTTree{

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹。若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；（2）若D-{root}≠￠，則存在D-{root}的一個(gè)劃分D1，D2，…，Dm(m>0)，對任意的j≠k(1≤j,k≤m)有Dj∩Dk=￠，且對任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H；（3）對應(yīng)于D-{root}的劃分，H-{<root,x1>},…,<root,xn>}有唯一的一個(gè)劃分H1，H2，…，Hm(m>0)，對任意的j≠k(1≤j,k≤m)有Dj∩Dk=￠，且對任意的i(1≤i≤m)，Hi是Di上的二元關(guān)系，(Di,{Hi})是一棵符合本定義的樹，稱為root的子樹。5.1樹的定義和抽象數(shù)據(jù)類型5.1.3樹的抽象數(shù)據(jù)類型唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。基本操作：（1）InitTree(&T)

初始條件：樹T不存在。操作結(jié)果：構(gòu)造空樹T。（2）DestroyTree(&T)

初始條件：樹T存在。操作結(jié)果：銷毀樹T。（3）CreateTree(&T)

初始條件：樹T存在。操作結(jié)果：根據(jù)給定條件構(gòu)造樹T。5.1樹的定義和抽象數(shù)據(jù)類型5.1.3樹的抽象數(shù)據(jù)類型唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。（10）DeleteChild(&T,p,i)

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤d，d為p所指向結(jié)點(diǎn)的度。操作結(jié)果：將p所指向的結(jié)點(diǎn)的第i棵子樹刪除。如果刪除成功，返回1，否則返回0。（11）TraverseTree(T)

初始條件：樹T存在。操作結(jié)果：按照某種次序?qū)的每個(gè)結(jié)點(diǎn)訪問且僅訪問一次。（12）TreeDepth(T)

初始條件：樹T存在。操作結(jié)果：若樹T非空，返回樹的深度，如果是空樹，返回0。}ADTTree5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.1二叉樹的定義二叉樹（BinaryTree）是另一種樹結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只有兩棵子樹。樹可以轉(zhuǎn)化為唯一一棵二叉樹，二叉樹可以簡化樹的處理。下面給出二叉樹的五種基本形態(tài)，如圖5.4所示。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.1二叉樹的定義一個(gè)由12個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹如圖5.5所示。F是C的左孩子結(jié)點(diǎn)，G是C的右孩子結(jié)點(diǎn)，L是G的右孩子結(jié)點(diǎn)，G的左孩子結(jié)點(diǎn)不存在。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型滿二叉樹和完全二叉樹每層結(jié)點(diǎn)都是滿的二叉樹稱為滿二叉樹，即在滿二叉樹中，每一層的結(jié)點(diǎn)都具有最大的結(jié)點(diǎn)個(gè)數(shù)。圖5.6所示就是一棵滿二叉樹。在滿二叉樹中，每個(gè)結(jié)點(diǎn)的度或者為2，或者為0（即葉子結(jié)點(diǎn)），不存在度為1的結(jié)點(diǎn)。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型滿二叉樹和完全二叉樹如果一棵二叉樹有n個(gè)結(jié)點(diǎn)，并且二叉樹的n個(gè)結(jié)點(diǎn)的結(jié)構(gòu)與滿二叉樹的前n個(gè)結(jié)點(diǎn)的結(jié)構(gòu)完全相同，則稱這樣的二叉樹為完全二叉樹。完全二叉樹及對應(yīng)編號如圖5.8所示。而圖5.9所示就不是一棵完全二叉樹。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（1）性質(zhì)1：在二叉樹中，第m(m≥1)層上至多有2m-1個(gè)結(jié)點(diǎn)（規(guī)定根結(jié)點(diǎn)為第一層）。證明：利用數(shù)學(xué)歸納法證明。當(dāng)m=1時(shí)，即根結(jié)點(diǎn)所在的層次，有2m-1=21-1=20=1，命題成立。假設(shè)當(dāng)m=k時(shí)，命題成立，即第k層至多有2k-1個(gè)結(jié)點(diǎn)。因?yàn)樵诙鏄渲?，每個(gè)結(jié)點(diǎn)的度最大為2，則在第k+1層，結(jié)點(diǎn)的個(gè)數(shù)最多是第k層的2倍，即2×2k-1=2k-1+1=2k。即當(dāng)m=k+1時(shí)，命題成立。思考：第i層上至少有

1

個(gè)結(jié)點(diǎn)？5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（2）性質(zhì)2：深度為k(k≥1)的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。證明：第i層結(jié)點(diǎn)的最多個(gè)數(shù)2i-1，將深度為k的二叉樹中的每一層的結(jié)點(diǎn)的最大值相加，就得到二叉樹中結(jié)點(diǎn)的最大值，因此深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多有：

思考：深度為k時(shí)至少有

個(gè)結(jié)點(diǎn)？k5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（3）性質(zhì)3：對任何一棵二叉樹T，如果葉子結(jié)點(diǎn)總數(shù)為n0，度為2的結(jié)點(diǎn)總數(shù)為n2，則有n0=n2+1。證明：假設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，度為1的結(jié)點(diǎn)總數(shù)為n1。則：n=n0+n1+n2。假設(shè)二叉樹的分支數(shù)為Y，有n=Y+1。二叉樹的所有分支都是由度為1和度為2的結(jié)點(diǎn)發(fā)出，所以分支數(shù)Y=n1+2×n2。故n=Y+1=n1+2×n2+1。聯(lián)合兩式，得到n0+n1+n2=n1+2×n2+1，即n0=n2+1。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（4）性質(zhì)4：如果完全二叉樹有n個(gè)結(jié)點(diǎn)，則深度為

log2n

+1。符號表示不大于x的最大整數(shù)。證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k。k層完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)介于k-1層滿二叉樹與k層滿二叉樹結(jié)點(diǎn)個(gè)數(shù)之間。根據(jù)性質(zhì)2，k-1層滿二叉樹的結(jié)點(diǎn)總數(shù)為n1=2k-1-1，k層滿二叉樹的結(jié)點(diǎn)總數(shù)為n2=2k-1。因此有n1<n≤n2，即n1+1≤n<n2+1，又n1=2k-1-1和n2=2k-1，故得到2k-1-1≤n<2k-1，同時(shí)對不等式兩邊取對數(shù)，有k-1≤log2n<k。因?yàn)閗是整數(shù)，k-1也是整數(shù)，所以k-1=

log2n

，即k=

log2n

+1。命題成立。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（5）性質(zhì)5：如果完全二叉樹有n個(gè)結(jié)點(diǎn)，按照從上到下、從左到右的順序，對二叉樹中的每個(gè)結(jié)點(diǎn)從1到n進(jìn)行編號，則對于任意結(jié)點(diǎn)i有以下性質(zhì)： 如果i=1，則序號i對應(yīng)的結(jié)點(diǎn)就是根結(jié)點(diǎn)，該結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)。如果i>1，則序號為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號為。 如果2×i>n，則序號為i的結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)。如果2×i≤n，則序號為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號為2×i。 如果2×i+1>n，則序號為i的結(jié)點(diǎn)沒有右孩子結(jié)點(diǎn)。如果2×i+1≤n，則序號為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)序號為2×i+1。

一棵完全二叉樹有2000個(gè)結(jié)點(diǎn)，則其葉結(jié)點(diǎn)的個(gè)數(shù)是（）。10005.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.3二叉樹的抽象數(shù)據(jù)類型ADTBinaryTree{

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D=￠，則稱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中存在唯一的元素xl，<root,xl>∈H，且存在Dl上的關(guān)系HlH；若Dr≠￠，則Dr中存在唯一的元素xr，<root,xr>∈H，且存在Dr上的關(guān)系HrH；H={<root,xl>,<root,xr>,Hl,Hr}；（4）(Dl，{Hl})是一棵符合本定義的二叉樹，稱為根的左子樹，(Dr,{Hr})是一棵符合本定義的二叉樹，稱為根的右子樹。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.3二叉樹的抽象數(shù)據(jù)類型基本操作P：（1）InitBiTree(&T)

初始條件：二叉樹T不存在。操作結(jié)果：構(gòu)造空二叉樹T。（2）CreateBiTree(&T)

初始條件：給出了二叉樹T的定義。操作結(jié)果：創(chuàng)建一棵非空的二叉樹T。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.3二叉樹的抽象數(shù)據(jù)類型（10）PreOrderTraverse(T)

初始條件：二叉樹T存在。操作結(jié)果：先序遍歷二叉樹T，即先訪問根結(jié)點(diǎn)、再訪問左子樹、最后訪問右子樹，對二叉樹中的每個(gè)結(jié)點(diǎn)訪問且僅訪問一次。（11）InOrderTraverse(T)

初始條件：二叉樹T存在。操作結(jié)果：中序遍歷二叉樹T，即先訪問左子樹、再訪問根結(jié)點(diǎn)、最后訪問右子樹，對二叉樹中的每個(gè)結(jié)點(diǎn)訪問，且僅訪問一次。（12）PostOrderTraverse(T)

初始條件：二叉樹T存在。操作結(jié)果：后序遍歷二叉樹T，即先訪問左子樹、再訪問右子樹、最后訪問根結(jié)點(diǎn)，對二叉樹中的每個(gè)結(jié)點(diǎn)訪問，且僅訪問一次。（13）LevelTraverse(T)

初始條件：二叉樹T存在。操作結(jié)果：對二叉樹進(jìn)行層次遍歷。即按照從上到下、從左到右，依次對二叉樹中的每個(gè)結(jié)點(diǎn)進(jìn)行訪問。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.4二叉樹的存儲表示1.二叉樹的順序存儲我們已經(jīng)知道，完全二叉樹中每個(gè)結(jié)點(diǎn)的編號可以通過公式計(jì)算得到，因此，完全二叉樹的存儲可以按照從上到下、從左到右的順序依次存儲在一維數(shù)組中。

5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.4二叉樹的存儲表示對于非完全二叉樹來說，這種存儲方式會浪費(fèi)內(nèi)存空間的浪費(fèi)。在最壞的情況下，如果每個(gè)結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)，而沒有左孩子結(jié)點(diǎn)，則需要占用2k-1個(gè)存儲單元，而實(shí)際上，該二叉樹只有k個(gè)結(jié)點(diǎn)。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.4二叉樹的存儲表示2.二叉樹的鏈?zhǔn)酱鎯υ诙鏄渲校總€(gè)結(jié)點(diǎn)有一個(gè)雙親結(jié)點(diǎn)和兩個(gè)孩子結(jié)點(diǎn)。從一棵二叉樹的根結(jié)點(diǎn)開始，通過結(jié)點(diǎn)的左右孩子地址就可以找到二叉樹的每一個(gè)結(jié)點(diǎn)。因此二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)包括三個(gè)域：數(shù)據(jù)域、左孩子指針域和右孩子指針域。5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.4二叉樹的存儲表示為了方便找到結(jié)點(diǎn)的雙親結(jié)點(diǎn)，在二叉鏈表的存儲結(jié)構(gòu)中增加一個(gè)指向雙親結(jié)點(diǎn)的指針域parent。這種存儲結(jié)構(gòu)稱為三叉鏈表結(jié)點(diǎn)存儲結(jié)構(gòu)。classBiTreeNode//二叉樹的結(jié)點(diǎn)類型{chardata;BiTreeNodelchild,rchild;BiTreeNode(chardata)

{this.data=data;lchild=null;rchild=null;}}5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型創(chuàng)建二叉樹算法實(shí)現(xiàn)如下：BiTreeNodeCreateBiTree(charstr[])

{

if(str[pi]=='#')//本層是構(gòu)建root、root.lchild、root.rchild三個(gè)結(jié)點(diǎn){

++pi;

returnnull;

}

BiTreeNoderoot=newBiTreeNode();

root.data=str[pi];

++pi;

root.lchild=CreateBiTree(str);//構(gòu)造左子樹

root.rchild=CreateBiTree(str);//構(gòu)造右子樹

returnroot;//遞歸結(jié)束返回構(gòu)造好的樹的根結(jié)點(diǎn)

}5.3二叉樹的遍歷學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力二叉樹的遍歷，即按照某種規(guī)律對二叉樹的每個(gè)結(jié)點(diǎn)進(jìn)行訪問，使得每個(gè)結(jié)點(diǎn)僅被訪問一次的操作。這里的訪問，可以是對結(jié)點(diǎn)的輸出、統(tǒng)計(jì)結(jié)點(diǎn)的個(gè)數(shù)等。如果限定先左后右的次序，則在以上6種遍歷方案中，只剩下3種方案：DLR、LDR和LRD。其中，DLR稱為先序遍歷，LDR稱為中序遍歷，LRD稱為后序遍歷。5.3.1二叉樹遍歷的定義5.3二叉樹的遍歷學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力5.3.2二叉樹的先序遍歷二叉樹的先序遍歷的遞歸定義如下：如果二叉樹為空，則執(zhí)行空操作。如果二叉樹非空，則執(zhí)行以下操作：（1）訪問根結(jié)點(diǎn)。（2）先序遍歷左子樹。（3）先序遍歷右子樹。根據(jù)二叉樹的先序遞歸定義，得到圖5.16所示的二叉樹的先序序列為：A、B、D、G、E、H、I、C、F、J。5.3二叉樹的遍歷學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力二叉樹的先序遞歸算法。publicvoidPreOrderTraverse(BiTreeNodeT)

//先序遍歷二叉樹的遞歸實(shí)現(xiàn)

{

if(T!=null){

System.out.print(T.data+"");//訪問根結(jié)點(diǎn)

PreOrderTraverse(T.lchild);//先序遍歷左子樹

PreOrderTraverse(T.rchild);//先序遍歷右子樹

}

}5.3二叉樹的遍歷二叉樹的先序非遞歸遍歷從二叉樹的根結(jié)點(diǎn)開始，訪問根結(jié)點(diǎn)，然后將根結(jié)點(diǎn)的指針入棧，重復(fù)執(zhí)行以下兩個(gè)步驟：（1）如果該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存在，訪問左孩子結(jié)點(diǎn)，并將左孩子結(jié)點(diǎn)的指針入棧。重復(fù)執(zhí)行此操作，直到結(jié)點(diǎn)的左孩子不存在；（2）將棧頂?shù)脑兀ㄖ羔槪┏鰲＃绻撝羔樦赶虻挠液⒆咏Y(jié)點(diǎn)存在，則將當(dāng)前指針指向右孩子結(jié)點(diǎn)。重復(fù)執(zhí)行以上兩個(gè)步驟，直到?？諡橹?。5.3二叉樹的遍歷publicvoidPreOrderTraverse2(BiTreeNodeT)

//先序遍歷二叉樹的非遞歸實(shí)現(xiàn)

{

BiTreeNodestack[]=newBiTreeNode[MAXSIZE];//定義一個(gè)棧，用于存放結(jié)點(diǎn)的指針

inttop=0;BiTreeNodep=T;

while(p!=null||top>0){

while(p!=null)//如果p不空，訪問根結(jié)點(diǎn)，遍歷左子樹

{

System.out.print(p.data+"");//訪問根結(jié)點(diǎn)

stack[top++]=p;

p=p.lchild;//遍歷左子樹

}

if(top>0)//如果棧不空

{

p=stack[--top];//棧頂元素出棧

p=p.rchild;//遍歷右子樹

}

}

}5.3二叉樹的遍歷5.3.3二叉樹的中序遍歷二叉樹的中序遍歷的遞歸定義如下：如果二叉樹為空，則執(zhí)行空操作。如果二叉樹非空，則執(zhí)行以下操作：（1）中序遍歷左子樹。（2）訪問根結(jié)點(diǎn)。（3）中序遍歷右子樹。根據(jù)二叉樹的中序遞歸定義，圖5.16的二叉樹的中序序列為：D、G、B、H、E、I、A、F、J、C。。5.3二叉樹的遍歷（1）如果該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存在，將左孩子結(jié)點(diǎn)的指針入棧。重復(fù)執(zhí)行此操作，直到結(jié)點(diǎn)的左孩子不存在；（2）將棧頂?shù)脑兀ㄖ羔槪┏鰲?，并訪問該指針指向的結(jié)點(diǎn)，如果該指針指向的右孩子結(jié)點(diǎn)存在，則將當(dāng)前指針指向右孩子結(jié)點(diǎn)。重復(fù)執(zhí)行以上（1）和（2），直到?？諡橹埂ublicvoidInOrderTraverse2(BiTreeNodeT)//中序遍歷二叉樹的非遞歸實(shí)現(xiàn){BiTreeNodestack[]=newBiTreeNode[MAXSIZE];//定義一個(gè)棧，用于存放結(jié)點(diǎn)的指針

inttop=0;//定義棧頂指針,初始化棧

BiTreeNodep=T;while(p!=null||top>0){while(p!=null)//如果p不空，則遍歷左子樹

{stack[top++]=p;//將p入棧

p=p.lchild;//遍歷左子樹

}if(top>0)//如果棧不空

{p=stack[--top];//棧頂元素出棧

System.out.print(p.data+"");//訪問根結(jié)點(diǎn)

p=p.rchild;//遍歷右子樹

}}}5.3二叉樹的遍歷5.3.4二叉樹的后序遍歷二叉樹的后序遍歷的遞歸定義如下：如果二叉樹為空，則執(zhí)行空操作。如果二叉樹非空，則執(zhí)行以下操作：（1）后序遍歷左子樹。（2）后序遍歷右子樹。（3）訪問根結(jié)點(diǎn)。根據(jù)二叉樹的后序遞歸定義，圖6.16所示的二叉樹的后序序列為：G、D、H、I、E、B、J、F、C、A。publicvoidPostOrderTraverse(BiTreeNodeT)//后序遍歷二叉樹的遞歸實(shí)現(xiàn){if(T!=null)//如果二叉樹不為空

{PostOrderTraverse(T.lchild);

PostOrderTraverse(T.rchild);

System.out.print(T.data+"");

}}5.3二叉樹的遍歷（1）如果該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存在，將左孩子結(jié)點(diǎn)的指針入棧。重復(fù)執(zhí)行此操作，直到結(jié)點(diǎn)的左孩子不存在；（2）取棧頂元素（指針）并賦給p，如果p沒有右孩子或右孩子結(jié)點(diǎn)已經(jīng)訪問過，則訪問根結(jié)點(diǎn)。否則，則執(zhí)行p=p.rchild。重復(fù)執(zhí)行以上（1）和（2），直到棧空為止。publicvoidPostOrderTraverse2(BiTreeNodeT)//后序遍歷二叉樹的非遞歸實(shí)現(xiàn){BiTreeNodestack[]=newBiTreeNode[MAXSIZE];

inttop=0;BiTreeNodep=T;BiTreeNodeq=null;

//初始化結(jié)點(diǎn)的指針

while(p!=null||top>0){while(p!=null)//如果p不空，則遍歷左子樹

{stack[top++]=p;//將p入棧

p=p.lchild;//遍歷左子樹

}if(top>0)//如果棧不空

{p=stack[top-1];//取棧頂元素

if(p.rchild==null||p.rchild==q)//如果p沒有右孩子結(jié)點(diǎn)，或右孩子結(jié)點(diǎn)已經(jīng)訪問過

{System.out.print(p.data+"");//訪問根結(jié)點(diǎn)

q=p;//記錄剛剛訪問過的結(jié)點(diǎn)

p=null;//為遍歷右子樹做準(zhǔn)備

top--;//出棧

}

elsep=p.rchild;

}}}分析：n個(gè)結(jié)點(diǎn)，則共有2n個(gè)鏈域。除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)鏈域指向自身，因此，有n－1個(gè)結(jié)點(diǎn)的鏈域存放有指針?？罩羔槀€(gè)數(shù)＝2n－(n-1)=n+1在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有

個(gè)空指針域。AB

D

E

F

CG^^^^^^^^n+15.4二叉樹的線索化5.4二叉樹的線索化為了區(qū)分指針域指向的是左孩子結(jié)點(diǎn)還是直接前驅(qū)結(jié)點(diǎn)、右孩子結(jié)點(diǎn)還是直接后繼結(jié)點(diǎn)，增加兩個(gè)標(biāo)志域ltag和rtag。結(jié)點(diǎn)的存儲結(jié)構(gòu)如圖5.20所示。其中，當(dāng)ltag=0時(shí)，lchild指示結(jié)點(diǎn)的左孩子；當(dāng)ltag=1時(shí)，lchild指示結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。當(dāng)rtag=0時(shí)，rchild指示結(jié)點(diǎn)的右孩子；當(dāng)rtag=1時(shí)，rchild指示結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。：5.4二叉樹的線索化二叉樹按照某種遍歷方式使二叉樹變?yōu)榫€索二叉樹的過程稱為二叉樹的線索化。圖5.21所示就是將二叉樹進(jìn)行先序、中序和后序遍歷得到的線索二叉樹。5.4二叉樹的線索化線索二叉樹的存儲結(jié)構(gòu)類型描述如下：classBiThrNode//線索二叉樹結(jié)點(diǎn){Stringdata;BiThrNodelchild,rchild;intltag,rtag;BiThrNode()

{this.data="NULL";//二叉樹的結(jié)點(diǎn)值

this.lchild=null;//左孩子

this.rchild=null;//右孩子

this.ltag=0;//線索標(biāo)志域

this.rtag=0;//線索標(biāo)志域

}5.4二叉樹的線索化為了方便，在二叉樹的線索化時(shí)，可增加一個(gè)頭結(jié)點(diǎn)。使頭結(jié)點(diǎn)的指針域lchild指向二叉樹的根結(jié)點(diǎn)，指針域rchild指向二叉樹中序遍歷時(shí)的最后一個(gè)結(jié)點(diǎn)，二叉樹中的第一個(gè)結(jié)點(diǎn)的線索指針指向頭結(jié)點(diǎn)。初始化時(shí)，使二叉樹的頭結(jié)點(diǎn)指針域lchild和rchild均指向頭結(jié)點(diǎn)，并將頭結(jié)點(diǎn)的標(biāo)志域ltag置為Link，標(biāo)志域rtag置為Thread。5.4二叉樹的線索化publicBiThrNodeInOrderThreading(BiThrNodeT)

//通過中序遍歷二叉樹T，使T中序線索化。thrt是指向頭結(jié)點(diǎn)的指針

{

BiThrNodethrt=newBiThrNode();

//將頭結(jié)點(diǎn)線索化

thrt.ltag=0;//修改前驅(qū)線索標(biāo)志

thrt.rtag=1;//修改后繼線索標(biāo)志

thrt.rchild=thrt;//將頭結(jié)點(diǎn)的rchild指針指向自己

if(T==null)//如果二叉樹為空，則將lchild指針指向自己

thrt.lchild=thrt;

else{

thrt.lchild=T;//將頭結(jié)點(diǎn)的左指針指向根結(jié)點(diǎn)

pre=thrt;//將pre指向已經(jīng)線索化的結(jié)點(diǎn)

T=InThreading(T);//中序遍歷進(jìn)行中序線索化

//將最后一個(gè)結(jié)點(diǎn)線索化

pre.rchild=thrt;//將最后一個(gè)結(jié)點(diǎn)的右指針指向頭結(jié)點(diǎn)

pre.rtag=1;//修改最后一個(gè)結(jié)點(diǎn)的rtag標(biāo)志域

thrt.rchild=pre;//將頭結(jié)點(diǎn)的rchild指針指向最后一個(gè)結(jié)點(diǎn)

thrt.lchild=T;//將頭結(jié)點(diǎn)的左指針指向根結(jié)點(diǎn)

}

returnthrt;

}5.4二叉樹的線索化publicBiThrNodeInThreading(BiThrNodep){

//二叉樹中序線索化

if(p!=null){

InThreading(p.lchild);//左子樹線索化

if(p.lchild==null)//前驅(qū)線索化

{

p.ltag=1;

p.lchild=pre;

}

if(pre.rchild==null)//后繼線索化

{

pre.rtag=1;

pre.rchild=p;

}

pre=p;//pre指向的結(jié)點(diǎn)線索化完畢，使p指向的結(jié)點(diǎn)成為前驅(qū)

InThreading(p.rchild);//右子樹線索化

}

returnp;

}5.4二叉樹的線索化查找指定結(jié)點(diǎn)的中序直接前驅(qū)的算法實(shí)現(xiàn)如下。publicBiThrNodeInOrderPre(BiThrNodep)

//在中序線索樹中找結(jié)點(diǎn)p的中序直接前趨

{

if(p.ltag==1)//如果p的標(biāo)志域ltag為線索，則p的左子樹結(jié)點(diǎn)即為前驅(qū)

returnp.lchild;

else{

pre=p.lchild;//查找p的左孩子的最右下端結(jié)點(diǎn)

while(pre.rtag==0)//右子樹非空時(shí)，沿右鏈往下查找

pre=pre.rchild;

returnpre;//pre就是最右下端結(jié)點(diǎn)

}

}5.4.3線索二叉樹的遍歷5.4二叉樹的線索化中序遍歷線索二叉樹的算法實(shí)現(xiàn)如下。publicvoidInOrderTraverse(BiThrNodeT)

//中序遍歷線索二叉樹

{

BiThrNodep=T.lchild;//將根結(jié)點(diǎn)賦給p

while(p!=T){

while(p!=T&&p.ltag==0)//順著左孩子線索進(jìn)行搜索

p=p.lchild;

Print(p);

while(p.rtag==1&&p.rchild!=T){//如果存在右孩子線索，搜索后繼結(jié)點(diǎn)

p=p.rchild;

Print(p);

}

p=p.rchild;

}

}5.4二叉樹的線索化【例5.1】編寫程序，建立如圖5-21所示的二叉樹，并將其中序線索化。任輸入一個(gè)結(jié)點(diǎn)，輸出該結(jié)點(diǎn)的中序前驅(qū)和中序后繼。例如，結(jié)點(diǎn)’D’的中序直接前驅(qū)是’G’，其中序直接后繼是’A’。線索二叉樹的輸出序列：0 Thread B Link 1 Thread G Thread 2 Link D Thread 3 Link A Link 4 Thread E Link 5 Thread H Thread 6 Link C Link 7 Thread F Thread 元素D的中序直接前驅(qū)元素是:G元素D的中序直接后繼元素是:A元素E的中序直接前驅(qū)元素是:A元素E的中序直接后繼元素是:H5.5樹、森林與二叉樹1.雙親表示法雙親表示法是利用一組連續(xù)的存儲單元存儲樹的每個(gè)結(jié)點(diǎn)，并利用一個(gè)指示器表示結(jié)點(diǎn)的雙親結(jié)點(diǎn)在樹中的相對位置。通常在Java語言中，利用數(shù)組實(shí)現(xiàn)連續(xù)的單元的存儲。樹的雙親表示法如圖5-23所示。5.5.1樹的存儲結(jié)構(gòu)5.5樹、森林與二叉樹classPNode//雙親表示法的結(jié)點(diǎn)定義

{

Stringdata;

intparent;//指示結(jié)點(diǎn)的雙親

}

classPTree//雙親表示法的類型定義

{

PNodenode[];

intnum;//結(jié)點(diǎn)的個(gè)數(shù)

PTree()

{

node=newPNode[num];

}

}5.5.1樹的存儲結(jié)構(gòu)5.5樹、森林與二叉樹2.孩子表示法把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，看成是一個(gè)線性表，且以單鏈表作為存儲結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表），這樣的鏈表稱為孩子鏈表。5.5樹、森林與二叉樹classChildNode//孩子結(jié)點(diǎn)的類型定義{intchild;ChildNodenext;//指向下一個(gè)結(jié)點(diǎn)}classDataNode//n個(gè)結(jié)點(diǎn)數(shù)據(jù)與孩子鏈表的指針構(gòu)成一個(gè)結(jié)構(gòu){intdata;ChildNodefirstchild;//孩子鏈表的指針}孩子表示法classCTree//孩子表示法類型定義{DataNodenode[];intnum;//結(jié)點(diǎn)的個(gè)數(shù)

introot;//根結(jié)點(diǎn)在順序表中的位置

CTree(){node=newDataNode[num];num=0;root=-1;}}5.5樹、森林與二叉樹3.孩子兄弟表示法孩子兄弟表示法，也稱為樹的二叉鏈表表示法。即以二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)，分別命名為firstchild域和nextsibling域。5.5樹、森林與二叉樹3.孩子兄弟表示法樹的孩子兄弟表示法的類型描述如下。classCSNode//孩子兄弟表示法的類型定義{Stringdata;CSNodefirstchild,nextsibling;//指向第一個(gè)孩子和下一個(gè)兄弟}5.5樹、森林與二叉樹5.5.2樹轉(zhuǎn)換為二叉樹從樹的孩子兄弟表示和二叉樹的二叉鏈表表示來看，它們在物理上的存儲方式是相同的，也就是說，從它們的相同的物理結(jié)構(gòu)可以得到一棵樹，也可以得到一棵二叉樹。5.5樹、森林與二叉樹5.5.2樹轉(zhuǎn)換為二叉樹按照以下步驟，可以將一棵樹轉(zhuǎn)換為對應(yīng)的二叉樹。（1）在樹中的兄弟結(jié)點(diǎn)之間加一條連線。（2）在樹中，只保留雙親結(jié)點(diǎn)與第一個(gè)孩子結(jié)點(diǎn)之間的連線，將雙親結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)的連線刪除。（3）將樹中的各個(gè)分支，以某個(gè)結(jié)點(diǎn)為中心進(jìn)行旋轉(zhuǎn)，子樹以根結(jié)點(diǎn)成對稱形狀。5.5樹、森林與二叉樹5.5.3森林轉(zhuǎn)換為二叉樹按照以下步驟，可以將一棵樹轉(zhuǎn)換為對應(yīng)的二叉樹。（1）把森林中的所有樹都轉(zhuǎn)換為對應(yīng)的二叉樹。（2）從第二棵樹開始，將轉(zhuǎn)換后的二叉樹作為前一棵樹根結(jié)點(diǎn)的右孩子，插入到前一棵樹中。然后將轉(zhuǎn)換后的二叉樹進(jìn)行相應(yīng)的旋轉(zhuǎn)。5.5樹、森林與二叉樹5.5.4二叉樹轉(zhuǎn)換為樹和森林（1）在二叉樹中，將某結(jié)點(diǎn)的所有右孩子結(jié)點(diǎn)、右孩子的右孩子結(jié)點(diǎn)等等，都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線條連接。（2）刪除掉二叉樹中雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的原來的連線。（3）調(diào)整轉(zhuǎn)換后的樹或森林，使結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)處于同一層次。5.6并查集對于并查集，在一些有N個(gè)元素的集合應(yīng)用問題中，初始時(shí)通常將每個(gè)元素看成是一個(gè)單元素的集合，然后按一定次序?qū)儆谕唤M的元素所在的集合兩兩合并，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。5.6并查集1.初始化每個(gè)元素代表一棵樹。假設(shè)有n個(gè)編號分別為1、2、...、n的元素，使用列表parent存儲每個(gè)元素的父結(jié)點(diǎn)，初始化時(shí)，先將父結(jié)點(diǎn)設(shè)為自身。publicclassDisjointSet{finalintMAXSIZE=100;intparent[];intrank[];DisjointSet(intn)

{parent=newint[n+1];rank=newint[n+1];for(inti=0;i<n+1;i++)parent[i]=i;}}5.6并查集將a和f所在的集合（即把a(bǔ)和f兩棵樹）合并后，使a成為兩個(gè)結(jié)點(diǎn)構(gòu)成樹的父結(jié)點(diǎn)。如圖5-32(b)所示。如圖5-32(c)所示。繼續(xù)將其他結(jié)點(diǎn)進(jìn)行合并操作，直到所有結(jié)點(diǎn)構(gòu)成一棵樹。5.6并查集查找publicintFind(intx){

if(parent[x]==x)

returnx;

else

returnFind(parent[x]);

}5.6并查集查找publicintFind2(intx){

if(parent[x]==x)

returnx;

parent[x]=Find2(x);

returnparent[x];

}帶路徑壓縮的查找算法實(shí)現(xiàn)如下：publicintFind_NonRec(intx)

{introot=x;

while(parent[root]!=root)//查找根結(jié)點(diǎn)root

root=parent[root];

inty=x;

while(y!=root)//路徑壓縮

{parent[y]=root;

y=parent[y];

}

returnroot;

}5.6并查集3.合并合并算法主要思想：找到x和y所屬子樹的根結(jié)點(diǎn)root_x和root_y，若root_x==root_y，則表明它們屬于同一棵子樹，不需合并；否則，需要比較兩棵子樹的高度，即秩，使合并后的子樹高度盡可能?。航o你一個(gè)由'1'（陸地）和'0'（水）組成的的二維網(wǎng)格，請你計(jì)算網(wǎng)格中島嶼的數(shù)量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。grid=[

["1","1","0","0","0"],

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]5.6并查集算法思想：該題要找到島嶼的數(shù)量，就是一個(gè)利用并查集的合并操作，將所有的元素都合并完，再去還剩下多少個(gè)獨(dú)立集合的問題。每一個(gè)島嶼就是一個(gè)獨(dú)立的集合。這里有一個(gè)注意點(diǎn)就是需要區(qū)分不同的樣本，顯然要進(jìn)行合并的樣本的值都是字符’1’。5.6并查集發(fā)送電文過程中，要將待傳字符轉(zhuǎn)換成二進(jìn)制的字符串，怎樣編碼才能使轉(zhuǎn)換后的報(bào)文盡快發(fā)送？BAAACCCADB010000001010100011010000011100100原則：頻率高的字符編碼盡可能地短5.7哈夫曼樹哈夫曼（Huffman）樹，也稱最優(yōu)二叉樹。它是一種帶權(quán)路徑長度最短的樹。A：00B：01C：10D：11A：0B：00C：1D：01編碼短注意：在編碼時(shí)，必須保證任何一個(gè)字符的編碼不能是其他字符編碼的前綴字符串。AAAAAAAABBAAABBA歧義BAAACCCADB00000111001005.7哈夫曼樹A：0B：00C：1D：01DCAB000111A：110B：111C：10D：0

1111101101101010101100111BAAACCCADBACDB000111A：0B：110C：10D：111

10100011111101111105.7哈夫曼樹使用二叉樹對結(jié)點(diǎn)進(jìn)行編碼是無歧義的，這種編碼就是前綴編碼譯碼時(shí)，從根結(jié)點(diǎn)出發(fā)，掃描字符串，遇到0訪問左孩子結(jié)點(diǎn)，遇到1訪問右孩子結(jié)點(diǎn)，直到葉子結(jié)點(diǎn)，葉子結(jié)點(diǎn)的字符即為該編碼對應(yīng)的字符。BAAACCCADB特點(diǎn)：每一個(gè)字符的編碼都不是其他字符編碼的前綴，絕不會錯(cuò)譯!稱為前綴碼5.7哈夫曼樹1010001111110111110ACDB0001115.7哈夫曼樹1.路徑和路徑長度路徑是指在樹中，從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所走過的路程。路徑長度是一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的分支數(shù)目。2.樹的帶權(quán)路徑長度在一些實(shí)際應(yīng)用中，根據(jù)結(jié)點(diǎn)的重要程度，將樹中的某一個(gè)結(jié)點(diǎn)賦予一個(gè)有意義的值，則這個(gè)值就是結(jié)點(diǎn)的權(quán)。（1）WPL=8×2+4×2+2×2+3×2=38（2）WPL=8×2+4×3+2×3+3×1=37（3）WPL=8×1+4×2+2×3+3×3=315.7哈夫曼樹（1）由給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)成n棵只有根結(jié)點(diǎn)的二叉樹集合F={T1,T2,…,Tn}，每個(gè)結(jié)點(diǎn)的左右子樹均為空。（2）在二叉樹集合F中，找兩個(gè)根結(jié)點(diǎn)的權(quán)值最小和次小的樹，作為左、右子樹構(gòu)造一棵新的二叉樹，新二叉樹的根結(jié)點(diǎn)的權(quán)重為左、右子樹根結(jié)點(diǎn)的權(quán)重之和。（3）在二叉樹集合F中，刪除作為左、右子樹的兩個(gè)二叉樹，并將新二叉樹加入到集合F中。（4）重復(fù)執(zhí)行步驟（2）和（3），直到集合F中只剩下一棵二叉樹為止。這顆二叉樹就是要構(gòu)造的哈夫曼樹。5.7哈夫曼樹例如，假設(shè)給定一組權(quán)值{1,3,6,9}，按照哈夫曼構(gòu)造的算法對集合的權(quán)重構(gòu)造哈夫曼樹的過程如圖5.38所示。classHTNode//哈夫曼樹類型定義

{

intweight;

intparent,lchild,rchild;

HTNode()

{

this.weight=weight;

this.parent=parent;

this.lchild=lchild;

this.rchild=rchild;

}

}5.7哈夫曼樹若一棵哈夫曼樹的葉子結(jié)點(diǎn)為n個(gè)，則該哈夫曼樹結(jié)點(diǎn)總數(shù)為2n-1算法實(shí)現(xiàn)：定義一個(gè)類型為HuffmanCode的變量HT，用來存放每一個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼。初始時(shí)，將每一個(gè)葉子結(jié)點(diǎn)的雙親結(jié)點(diǎn)域、左孩子域和右孩子域初始化為0。如果有n個(gè)葉子結(jié)點(diǎn)，則非葉子結(jié)點(diǎn)有n-1個(gè)，所以總共結(jié)點(diǎn)數(shù)目是2*n-1個(gè)。5.7哈夫曼樹若n=4,w={1,3,6,9}，請構(gòu)造哈夫曼樹和哈夫曼編碼結(jié)點(diǎn)總個(gè)數(shù)：m=2*4-1=7weightparentlchrch11000230003600049000567weightparentlchrch1150023500366004970054612610753719046a9c6a1b35.7哈夫曼樹初始狀態(tài)最終狀態(tài)000publicvoidHuffmanCoding(HTNodeHT[],StringHC[],intw[],intn)//構(gòu)造哈夫曼樹HT，哈夫曼樹的編碼存放在HC中，w為n個(gè)字符的權(quán)值{if(n<=1)return;intm=2*n-1;for(inti=1;i<=n;i++)//初始化n個(gè)葉子結(jié)點(diǎn)

{HT[i]=newHTNode();HT[i].weight=w[i-1];HT[i].parent=0；

HT[i].lchild=HT[i].rchild=0;}for(inti=n+1;i<=m;i++)//將n-1個(gè)非葉子結(jié)點(diǎn)的雙親結(jié)點(diǎn)初始化化為0

{HT[i]=newHTNode();HT[i].parent=0;}for(inti=n+1;i<=m;i++)//構(gòu)造哈夫曼樹

{List<Integer>s=Select(HT,i-1);//查找樹中權(quán)值最小的兩個(gè)結(jié)點(diǎn)

ints1=s.get(0),s2=s.get(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;}5.7哈夫曼樹

//從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)求每個(gè)字符的哈夫曼編碼

//求n個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼

for(inti=1;i<=n;i++)

{charcd[]=newchar[n+1];intstart=n-1;for(intc=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)求編碼

{if(HT[f].lchild==c)cd[--start]='0';

elsecd[--start]='1';}HC[i]=newString()；

Stringstr=newString(cd);HC[i]=str;//將當(dāng)前求出結(jié)點(diǎn)的哈夫曼編碼復(fù)制到HC}}5.7哈夫曼樹請輸入葉子結(jié)點(diǎn)的個(gè)數(shù):4請輸入第1個(gè)結(jié)點(diǎn)的權(quán)值:1請輸入第2個(gè)結(jié)點(diǎn)的權(quán)值:3請輸入第3個(gè)結(jié)點(diǎn)的權(quán)值:6請輸入第4個(gè)結(jié)點(diǎn)的權(quán)值:9哈夫曼編碼:100哈夫曼編碼:101哈夫曼編碼:11哈夫曼編碼:0"100101011"的譯碼結(jié)果：ABDC【例5.6】通過鍵盤輸入一個(gè)表達(dá)式，如6+(7-1)*3+9/2，將其轉(zhuǎn)換為二叉樹，即表達(dá)式樹，然后通過二叉樹的遍歷操作求解表達(dá)式的值。1）初始化棧，并將’#’入棧；2）若當(dāng)前讀入的字符?2是操作數(shù)，則將該操作數(shù)壓入ExpTreeStack棧，并讀入下一個(gè)字符；3）若當(dāng)前字符?2是運(yùn)算符，則將?2與棧頂?shù)倪\(yùn)算符?1比較。（1）若?1優(yōu)先級低于?2，則將?2壓入OptrStack棧，繼續(xù)讀入下一個(gè)字符；（2）若?1優(yōu)先級高于?2，則從OptrStack棧中彈出?1，將其作為子樹的根結(jié)點(diǎn)，并使ExpTreeStack棧執(zhí)行兩次出棧操作，彈出的兩個(gè)表達(dá)式rcd和lcd分別作為?1的右子樹和左子樹，從而創(chuàng)建二叉樹，并將該二叉樹的根結(jié)點(diǎn)壓入ExpTreeStack棧中。（3）若?1的優(yōu)先級與?2相等，且?1為’(‘，?2為’)’，則將?1出棧，繼續(xù)讀入下一個(gè)字符；4）如果?2的優(yōu)先級與?1相等，且?1和?2都為’#‘，從OptrStack棧中將?1彈出，則OptrStack棧為空。則完成中綴表達(dá)式轉(zhuǎn)換為表達(dá)式樹，ExpTreeStack的棧頂元素就是表達(dá)式樹的根結(jié)點(diǎn)，算法結(jié)束。重復(fù)執(zhí)行2）~4），直到所有字符讀取完畢且OptrStack為空。請輸入算術(shù)表達(dá)式串：6+(7-1)*3+9/2#先序遍歷：++6*-713/92中序遍歷：6+7-1*3+9/2表達(dá)式的值：28.55.8小結(jié)樹中結(jié)點(diǎn)與結(jié)點(diǎn)之間是一種一對多的關(guān)系。樹的定義是遞歸的。一棵樹或者為空，或者是由m棵子樹T1、T2、…、Tm組成，這m棵子樹又是由其他子樹構(gòu)成的。樹中的孩子結(jié)點(diǎn)沒有次序之分，是一種無序樹。二叉樹的兩棵子樹有次序之分。二叉樹也是遞歸定義的，二叉樹的兩棵子樹又是由左子樹和右子樹構(gòu)成。在二叉樹中，有兩種特殊的樹：滿二叉樹和完全二叉樹。滿二叉樹中每個(gè)非葉子結(jié)點(diǎn)都存在左子樹和右子樹，所有的葉子結(jié)點(diǎn)都處在同一層次上。完全二叉樹是指與滿二叉樹的前n個(gè)結(jié)點(diǎn)結(jié)構(gòu)相同，滿二叉樹是一種特殊的完全二叉樹。5.8小結(jié)二叉樹的遍歷分為先序遍歷、中序遍歷和后序遍歷。二叉樹遍歷的過程就是將二叉樹這種非線性結(jié)構(gòu)轉(zhuǎn)換成線性結(jié)構(gòu)。通過將二叉樹線索化，不僅可充分利用二叉鏈表中的空指針域，還能很方便地找到指定結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。在哈夫曼樹中，只有葉子結(jié)點(diǎn)和度為2的結(jié)點(diǎn)。哈夫曼樹是帶權(quán)路徑最小的二叉樹，通常用于解決最優(yōu)化問題。感謝聆聽主講：結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)第6章圖結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS6.1

圖的定義及相關(guān)概念6.2圖的存儲結(jié)構(gòu)6.3圖的遍歷6.6最短路徑6.4圖的連通性問題6.5有向無環(huán)圖6.7小結(jié)6.1圖的定義及相關(guān)概念6.1.1圖的定義圖由數(shù)據(jù)元素集合與邊的集合構(gòu)成。數(shù)據(jù)元素常稱為頂點(diǎn)（Vertex），頂點(diǎn)集合（V）不能為空，邊（E）表示頂點(diǎn)之間的關(guān)系，用連線表示。圖（G）的形式化定義為：G=(V,E)，其中，V={x|x∈數(shù)據(jù)元素集合}，E={<x,y>|Path(x,y)/\(x∈V,y∈V)}。Path(x,y)表示從x與y的關(guān)系屬性。如果<x,y>∈E，則<x,y>表示從頂點(diǎn)x到頂點(diǎn)y的一條?。ˋrc），x稱為弧尾（Tail）或起始點(diǎn)（Initialnode），y稱為弧頭（Head）或終端點(diǎn)（Terminalnode）。6.1圖的定義及相關(guān)概念6.1.1圖的定義如果<x,y>∈E且有<y,x>∈E，則用無序?qū)?x,y)代替有序?qū)?lt;x,y>和<y,x>，表示x與y之間存在一條邊（Edge），將這樣的圖稱為無向圖。6.1圖的定義及相關(guān)概念6.1.1圖的定義對于無向圖，邊數(shù)e的取值范圍為0~n(n-1)/2。將具有n(n-1)/2條邊的無向圖稱為完全圖。對于有向圖，弧度e的取值范圍是0~n(n-1)。將具有n(n-1)條弧的有向圖稱為有向完全圖。具有e<nlogn條弧或邊的圖，稱為稀疏圖（Sparsegraph）。具有e>nlogn條弧或邊的圖，稱為稠密圖（Densegraph）。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念1.鄰接點(diǎn)在無向圖G=(V,E)中，如果存在邊(vi,vj)∈E，則稱vi和vj互為鄰接點(diǎn)（Adjacent），即vi和vj相互鄰接。邊(vi,vj)依附于頂點(diǎn)vi和vj，或者稱邊(vi,vj)與頂點(diǎn)vi和vj相互關(guān)聯(lián)。2.頂點(diǎn)的度在無向圖中，頂點(diǎn)v的度是指與v相關(guān)聯(lián)的邊的數(shù)目，記作TD(v)。在有向圖中，以頂點(diǎn)v為弧頭的數(shù)目稱為頂點(diǎn)v的入度（InDegree），記作ID(v)。以頂點(diǎn)v為弧尾的數(shù)目稱為v的出度（OutDegree），記作OD(v)。頂點(diǎn)v的度為以v為頂點(diǎn)的入度和出度之和，即TD(v)=ID(v)+OD(v)。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念3.路徑在圖中，從頂點(diǎn)vi出發(fā)經(jīng)過一系列的頂點(diǎn)序列到達(dá)頂點(diǎn)vj稱為從頂點(diǎn)vi到vj的路徑（Path）。路徑的長度是路徑上弧或邊的數(shù)目。4.子圖假設(shè)存在兩個(gè)圖G={V,E}和G’={V’,E’}，如果G’的頂點(diǎn)和關(guān)系都是V的子集，即有V’V，E’E，則G’為G的子圖。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念5.連通圖和強(qiáng)連通圖在無向圖中，如果從頂點(diǎn)vi到頂點(diǎn)vj存在路徑，則稱頂點(diǎn)vi到vj是連通的。推廣到圖的所有頂點(diǎn)，如果圖中的任何兩個(gè)頂點(diǎn)之間都是連通的，則稱圖是連通圖（ConnectedGraph）。無向圖中的極大連通子圖稱為連通分量（ConnectedComponent）。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念6.生成樹一個(gè)連通圖（假設(shè)有n個(gè)頂點(diǎn)）的生成樹是一個(gè)極小連通子圖，它含有圖中的全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念7.網(wǎng)在實(shí)際應(yīng)用中，圖的邊或弧往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或花費(fèi)等信息。這種帶權(quán)的圖稱為帶權(quán)圖或網(wǎng)。一個(gè)網(wǎng)如圖6.6所示。6.1圖的定義及相關(guān)概念6.1.3圖的抽象數(shù)據(jù)類型7.網(wǎng)在實(shí)際應(yīng)用中，圖的邊或弧往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或花費(fèi)等信息。這種帶權(quán)的圖稱為帶權(quán)圖或網(wǎng)。一個(gè)網(wǎng)如圖6.6所示。ADTGraph{

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}VR={<x,y>|x,y∈V且P(x,y>，<x,y>表示從x到y(tǒng)的弧，謂詞P(x,y>定義了弧<x,y>的意義或信息}6.1圖的定義及相關(guān)概念6.1.3圖的抽象數(shù)據(jù)類型基本操作：

（1）CreateGraph(&G)

初始條件：圖G不存在。

操作結(jié)果：創(chuàng)建一個(gè)圖G。

（2）DestroyGraph(&T)

初始條件：圖G存在。

操作結(jié)果：銷毀圖G。

（3）LocateVertex(G,v)

初始條件：圖G存在，頂點(diǎn)v合法。

操作結(jié)果：若圖G存在頂點(diǎn)v，則返回頂點(diǎn)v在圖G中的位置。若圖G中沒有頂點(diǎn)v，則函數(shù)返回值為空。

（4）GetVertex(G,i)

初始條件：圖G存在。

操作結(jié)果：返回圖G中序號i對應(yīng)的值。i是圖G某個(gè)頂點(diǎn)的序號，返回圖G中序號i對應(yīng)的值。6.1圖的定義及相關(guān)概念6.1.3圖的抽象數(shù)據(jù)類型（5）FirstAdjVertex(G,v)

初始條件：圖G存在，頂點(diǎn)v的值合法。操作結(jié)果：返回圖G中v的第一個(gè)鄰接頂點(diǎn)。若v無鄰接頂點(diǎn)或圖G中無頂點(diǎn)v，則函數(shù)返回-1。（6）NextAdjVertex(G,v,w)

初始條件：圖G存在，w是圖G中頂點(diǎn)v的某個(gè)鄰接頂點(diǎn)。操作結(jié)果：返回頂點(diǎn)v的下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接頂點(diǎn)，則函數(shù)返回-1。（11）DFSTraverseGraph(G)

初始條件：圖G存在。操作結(jié)果：從圖中的某個(gè)頂點(diǎn)出發(fā)，對圖進(jìn)行深度遍歷。（12）BFSTraverseGraph(G)

初始條件：圖G存在。操作結(jié)果：從圖中的某個(gè)頂點(diǎn)出發(fā)，對圖進(jìn)行廣度遍歷。}ADTGraph6.2圖的存儲結(jié)構(gòu)6.2.1鄰接矩陣表示法圖的鄰接矩陣表示（AdjacencyMatrix）也稱為數(shù)組表示。它采用兩個(gè)數(shù)組來表示圖：一個(gè)是用于存儲頂點(diǎn)信息的一維數(shù)組，另一個(gè)是用于存儲圖中頂點(diǎn)之間的關(guān)聯(lián)關(guān)系的二維數(shù)組，這個(gè)關(guān)聯(lián)關(guān)系數(shù)組稱為鄰接矩陣。6.2圖的存儲結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力兩個(gè)圖弧和邊的集合分別為A={<A,B>,<A,C>,<A,D>,<C,A>,<C,B>,<D,A>}和E={(A,B),(A,D),(B,C),(B,D),(C,D)}。它們的鄰接矩陣表示如圖6.7所示。6.2圖的存儲結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力enumKind{DG,DN,UG,UN}//圖的類型publicclassMGraph{Stringve