第6章樹和二叉樹

DATA1065865ABCDEFG數(shù)據(jù)結(jié)構(gòu)第6章樹和二叉樹主講：李澤平2/1/20231學(xué)習(xí)提要

第6章樹

1.熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。

2.熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍。

3.熟練掌握各種遍歷策略的遞歸和非遞歸算法。

4.熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。

5.熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。

6.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。2/1/20232

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)

2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲

B鏈?zhǔn)酱鎯€性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個主要問題串、數(shù)組和廣義表2/1/20233線性結(jié)構(gòu)

A,B,C,·······，X,Y,Z學(xué)生成績表86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學(xué)號線性表——結(jié)點間是以線性關(guān)系聯(lián)結(jié)2/1/20234

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)

2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲

B鏈?zhǔn)酱鎯€性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面2/1/20235樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式2/1/20236ABCDEFGH樹形結(jié)構(gòu)——結(jié)點間具有分層次的連接關(guān)系HBCDEFGA2/1/202376樹的定義和基本術(shù)語1.樹的定義：由一個或多個結(jié)點組成的有限集合。僅有一個根結(jié)點，結(jié)點間有明顯的層次結(jié)構(gòu)關(guān)系。

A

C

GT2D

HIT3J

M

BEL

KT1F現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。2/1/20238樹是一種常用的非線性結(jié)構(gòu)。我們可以這樣定義：樹是n（n≥0）個結(jié)點的有限集合。

若n=0，則稱為空樹；否則，有且僅有一個特定的結(jié)點被稱為根。

當(dāng)n>1時，其余結(jié)點被分成m（m>0）個互不相交的子集T1，T2，...，Tm，每個子集又是一棵樹。

由此可以看出，樹的定義是遞歸。2/1/20239KLMEFGHIJBCDAA(a)(b)(c)2/1/202310介紹幾個概念：

結(jié)點：數(shù)據(jù)元素的內(nèi)容及其指向其子樹根的分支統(tǒng)稱為結(jié)點。

結(jié)點的度：結(jié)點的分支數(shù)。

終端結(jié)點（葉子）：度為0的結(jié)點。

非終端結(jié)點：度不為0的結(jié)點。

結(jié)點的層次：樹中根結(jié)點的層次為1，根結(jié)點子樹的根為第2層，以此類推。

樹的度：樹中所有結(jié)點度的最大值。

樹的深度：樹中所有結(jié)點層次的最大值。

有序樹、無序樹：如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。

A

C

G

T2D

HI

T3J

M

BEL

KT1F2/1/202311

森林:

是m（m≥0）棵互不相交的樹的集合。在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系又可以用家族關(guān)系描述，定義如下：

孩子、雙親:

結(jié)點子樹的根稱為這個結(jié)點的孩子，而這個結(jié)點又被稱為孩子的雙親。子孫:

以某結(jié)點為根的子樹中的所有結(jié)點都被稱為是該結(jié)點的子孫。祖先:

從根結(jié)點到該結(jié)點路徑上的所有結(jié)點。

兄弟:

同一個雙親的孩子之間互為兄弟。

堂兄弟:

雙親在同一層的結(jié)點互為堂兄弟。

A

C

GT2D

HIT3J

M

BEL

KT1F2/1/202312

2.樹的基本運(yùn)算常用操作：（1）構(gòu)造一個樹CreateTree(T)

（2）清空以T為根的樹ClearTree(T)

（3）判斷樹是否為空TreeEmpty(T)

（4）獲取給定結(jié)點的第i個孩子Child(T,node,i)

（5）獲取給定結(jié)點的雙親Parent(T,node)

（6）遍歷樹Traverse(T)

對樹遍歷的主要目的是將非線性結(jié)構(gòu)通過遍歷過程線性化，即獲得一個線性序列。樹的遍歷順序有兩種，一種是先序遍歷，即先訪問根結(jié)點，然后再依次用同樣的方法訪問每棵子樹；另一種是后序遍歷。2/1/2023136.2二叉樹（BinaryTree）1、二叉樹的定義及其性質(zhì)

(1)二叉樹的定義二叉樹的五種基本形態(tài)二叉樹一種特殊的樹型結(jié)構(gòu)，特點是樹中每個結(jié)點只有兩棵子樹，且子樹有左右之分，次序不能顛倒?？斩鏄?/p>

僅有根結(jié)點

右子樹為空左子樹為空左右子樹均非空因為樹的每個結(jié)點的度不同，存儲困難，使對樹的處理算法很復(fù)雜。所以引出二叉樹的討論。2/1/202314

二叉樹是n(n0)個結(jié)點的有限集合。它或為空樹(n=0),或由一個根結(jié)點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉樹組成。

特別要注意：二叉樹不是樹的特殊情況。aabb兩棵不同的二叉樹二叉樹也可以用遞歸的形式定義。即：二叉樹是n（n≥0）個結(jié)點的有限集合。當(dāng)n=0時，稱為空二叉樹；當(dāng)n>0時，有且僅有一個結(jié)點為二叉樹的根，其余結(jié)點被分成兩個互不相交的子集，一個作為左子集，另一個作為右子集，每個子集又是一個二叉樹。2/1/202315

1．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別?！?分】

樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。

樹和二叉樹的區(qū)別有二：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下，也必須指出是左子樹還是右子樹，樹無此限制，當(dāng)只有一個孩子時，不知為左/右孩子。

2．樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？【4分】

樹和二叉樹邏輯上都是樹形結(jié)構(gòu)，區(qū)別有以上題1所述三點。二叉樹不是樹的特例。

3．請分析線性表、樹、廣義表的主要結(jié)構(gòu)特點，以及相互的差異與關(guān)聯(lián)?！?0】

線性表屬于約束最強(qiáng)的線性結(jié)構(gòu)，在非空線性表中，只有一個“第一個”元素，也只有一個“最后一個”元素；除第一個元素外，每個元素有唯一前驅(qū)；除最后一個元素外，每個元素有唯一后繼。樹是一種層次結(jié)構(gòu)，有且只有一個根結(jié)點，每個結(jié)點可以有多個子女，但只有一個雙親（根無雙親），從這個意義上說存在一（雙親）對多（子女）的關(guān)系。廣義表中的元素既可以是原子，也可以是子表，子表可以為它表共享。從表中套表意義上說，廣義表也是層次結(jié)構(gòu)。從邏輯上講，樹和廣義表均屬非線性結(jié)構(gòu)。但在以下意義上，又蛻變?yōu)榫€性結(jié)構(gòu)。如度為1的樹，以及廣義表中的元素都是原子時。另外，廣義表從元素之間的關(guān)系可看成前驅(qū)和后繼，也符合線性表，但這時元素有原子，也有子表，即元素并不屬于同一數(shù)據(jù)對象。2/1/202316

二叉樹的基本運(yùn)算（1）構(gòu)造一棵二叉樹CreateBTree(BT)（2）清空以BT為根的二叉樹ClearBTree(BT)（3）判斷二叉樹是否為空BTreeEmpty(BT)（4）獲取給定結(jié)點的左孩子和右孩子LeftChild(BT,node)，RightChild(BT,node)（5）獲取給定結(jié)點的雙親Parent(BT,node)（6）遍歷二叉樹Traverse(BT)2/1/202317A)

二叉樹的第i層上至多有2i-1（i1）個結(jié)點。(2)二叉樹的基本性質(zhì)423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點。第四層上(i=4)，有24-1=8個節(jié)點。2/1/202318性質(zhì)1：二叉樹的第i層上至多有2i-1（i1）個結(jié)點。證明：利用歸納法證明。二叉樹的第1層只有一個根結(jié)點，所以，i=1時，2i-1=21-1=20=1成立。假設(shè)對所有的j，1≤j<i成立，即第j層上最多有2j-1個結(jié)點成立。若j=i-1，則第j層上最多有2j-1=2i-2個結(jié)點。由于在二叉樹中，每個結(jié)點的度最大為2，所以可以推導(dǎo)出第i層最多的結(jié)點個數(shù)就是第i-1層最多結(jié)點個數(shù)的2倍，即2i-2*2=2i-1。2/1/202319A)

二叉樹的第i層上至多有2i-1（i1）個結(jié)點。

B)

深度為K的二叉樹中至多含有2K-1個結(jié)點。(2)二叉樹的基本性質(zhì)423167891011121314155此樹的深度h=4，共有24-1=15個節(jié)點。2/1/202320

性質(zhì)2：深度為k的二叉樹中至多含有2k-1個結(jié)點。證明：由性質(zhì)1可以得出，1至K層各層最多的結(jié)點個數(shù)分別為：20,21,22,23,...,2K-1。這是一個以2為比值的等比數(shù)列，前n項之和的計算公式為：2/1/202321其中a1為第一項，an為第n項，q為比值。可以得到，該數(shù)列前K項之和為：2/1/202322A)

二叉樹的第i層上至多有2i-1（i1）個結(jié)點。B)

深度為h的二叉樹中至多含有2h-1個結(jié)點。C)

若在任意一棵二叉樹中，有n0個葉子結(jié)點，有n2個度為2的結(jié)點，則：n0=n2+1(2)二叉樹的基本性質(zhì)423167891011121314155n0=8n2=72/1/202323性質(zhì)3:對于任意一棵二叉樹T，如果度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0=n2+1

證明：假設(shè)度為1的結(jié)點個數(shù)為n1，結(jié)點總數(shù)為n，B為二叉樹中的分支數(shù)。因為在二叉樹中，所有結(jié)點的度均小于或等于2，所以結(jié)點總數(shù)為：

n=n0+n1+n2（1）再查看一下分支數(shù)。在二叉樹中，除根結(jié)點之外，每個結(jié)點都有一個從上向下的分支指向，所以，總的結(jié)點個數(shù)n與分支數(shù)B之間的關(guān)系為：n=B+1。2/1/202324又因為在二叉樹中，度為1的結(jié)點產(chǎn)生1個分支，度為2的結(jié)點產(chǎn)生2個分支，所以分支數(shù)B可以表示為：B=n1+2*n2。將此式代入上式，得：

n=n0+n1+n2（1）

n=n1+2n2+1（2）用（1）式減去（2）式，并經(jīng)過調(diào)整后得到：n0=n2+1。

2/1/202325

8910111213141545672312/1/202326

性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度為[log2n]+1。其中，[log2n]的結(jié)果是不大于log2n的最大整數(shù)。證明：假設(shè)具有n個結(jié)點的完全二叉樹的深度為K，則根據(jù)性質(zhì)2可以得出：

2K-1-1<n≤2K-1

將不等式兩端加1得到：

2K-1≤n<2K

將不等式中的三項同取以2為底的對數(shù)，并經(jīng)過化簡后得到：

K-1≤log2n<K

由此可以得到：log2n=K-1。整理后得到：K=log2n+1。2/1/202327

性質(zhì)5:對于有n個結(jié)點的完全二叉樹中的所有結(jié)點按從上到下，從左到右的順序進(jìn)行編號，則對任意一個結(jié)點i（1≤i≤n），都有：（1）如果i=1，則結(jié)點i是這棵完全二叉樹的根，沒有雙親；否則其雙親結(jié)點的編號為「i/2」。（2）如果2i>n，則結(jié)點i沒有左孩子；否則其左孩子結(jié)點的編號為2i。（3）如果2i+1>n，則結(jié)點i沒有右孩子；否則其右孩子結(jié)點的編號為2i+1。下面我們利用數(shù)學(xué)歸納法證明這個性質(zhì)。我們首先證明（2）和（3）。當(dāng)i=1時，若n≥3，則根的左、右孩子的編號分別是2，3；若n<3，則根沒有右孩子；若n<2，則根將沒有左、右孩子；以上對于（2）和（3）均成立。假設(shè)：對于所有的1≤j≤i結(jié)論成立。即：結(jié)點j的左孩子編號為2j；右孩子編號為2j+1。2/1/2023282i+2

2i2i+12i+22i+3i+12i2i+1i

i

i+12/1/202329由完全二叉樹的結(jié)構(gòu)可以看出：結(jié)點i+1或者與結(jié)點i同層且緊鄰i結(jié)點的右側(cè)，或者i位于某層的最右端，i+1位于下一層的最左端。可以看出，i+1的左、右孩子緊鄰在結(jié)點i的孩子后面，由于結(jié)點i的左、右孩子編號分別為2i和2i+1，所以，結(jié)點i+1的左、右孩子編號分別為2i+2和2i+3，經(jīng)提取公因式可以得到：2(i+1)和2(i+1)+1，即結(jié)點i+1的左孩子編號為2(i+1)；右孩子編號為2(i+1)+1。又因為二叉樹由n個結(jié)點組成，所以，當(dāng)2(i+1)+1>n，且2(i+1)=n時，結(jié)點i+1只有左孩子，而沒有右孩子；當(dāng)2(i+1)>n，結(jié)點i+1既沒有左孩子也沒有右孩子。2/1/202330以上證明得到（2）和（3）成立。下面利用上面的結(jié)論證明（1）。對于任意一個結(jié)點i，若2i≤n，則左孩子的編號為2i，反過來結(jié)點2i的雙親就是i，而2i/2=i；若2i+1≤n，則右孩子的編號為2i+1，反過來結(jié)點2i+1的雙親就是i，而(2i+1)/2=i，由此可以得出（1）成立。2/1/202331（3）滿二叉樹一棵深度為K且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。423167891011121314155特點：每一層上都含有最大結(jié)點數(shù)。2/1/202332423167891011125

非完全二叉樹（4）完全二叉樹423167891011125

完全二叉樹特點：除最后一層外，每一層都取最大結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置。2/1/202333（5）樹與二叉樹的區(qū)別A．樹的結(jié)點個數(shù)至少為1，而二叉樹的結(jié)點個數(shù)可以為0。B．樹中結(jié)點的最大度數(shù)沒有限制，二叉樹結(jié)點最大度數(shù)為2。C．樹的結(jié)點子樹無左、右之分，二叉樹的結(jié)點子樹有明確的左、右之分。

二叉樹樹2/1/2023342、二叉樹的存儲結(jié)構(gòu)

(2)鏈?zhǔn)酱鎯Y(jié)構(gòu)T[16]若父結(jié)點在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。11ABCFED

●●●●●●●●●124

8

910563712131415(1)順序存儲結(jié)構(gòu)(1)順序存儲結(jié)構(gòu)2h-1=24-1=15用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置蘊(yùn)含著結(jié)點之間的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費(fèi)。這種存儲結(jié)構(gòu)適用于完全二叉樹2/1/202335（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)在順序存儲結(jié)構(gòu)中，利用編號表示元素的位置及元素之間孩子或雙親的關(guān)系，因此對于非完全二叉樹，需要將空缺的位置用特定的符號填補(bǔ)，若空缺結(jié)點較多，勢必造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。常見的二叉樹結(jié)點結(jié)構(gòu)如下所示：2/1/202336lchildDatarchildA^DB^C^^E^^F^圖為一般二叉樹的二叉鏈表結(jié)構(gòu)AECBDF每個結(jié)點由數(shù)據(jù)域、左指針域和右指針域組成。2/1/202337這種存儲結(jié)構(gòu)的特點是尋找孩子結(jié)點容易，雙親比較困難。因此，若需要頻繁地尋找雙親，可以給每個結(jié)點添加一個指向雙親結(jié)點的指針域，其結(jié)點結(jié)構(gòu)如下所示。有關(guān)二叉樹在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的操作算法將在隨后介紹。2/1/202338鏈?zhǔn)酱鎯Y(jié)構(gòu)的描述：Typedef

struct

BiTNode{

int

data;

Struct

BiTNode

*lchild,*rchild;}BiTNode,*BiTree;lchildDatarchildlchildDatarchildlchildDatarchild2/1/2023396.3二叉樹的遍歷

二叉樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，在對它進(jìn)行操作時，總是需要逐一對每個數(shù)據(jù)元素實施操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。

所謂遍歷二叉樹就是按某種順序訪問二叉樹中的每個結(jié)點一次且僅一次的過程。這里的訪問可以是輸出、比較、更新、查看元素內(nèi)容等等各種操作。二叉樹的遍歷方式分為兩大類：一類按根、左子樹和右子樹三個部分進(jìn)行訪問；另一類按層次訪問。下面我們將分別進(jìn)行討論。2/1/202340

(1)按先左后右的原則，一般使用三種遍歷：先序遍歷(DLR):

訪問根結(jié)點，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(LDR):

按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。后序遍歷(LRD):

按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。2/1/202341下面我們再給出兩種遍歷二叉樹的方法：（1）對一棵二叉樹中序遍歷時，若我們將二叉樹嚴(yán)格地按左子樹的所有結(jié)點位于根結(jié)點的左側(cè)，右子樹的所有結(jié)點位于根右側(cè)的形式繪制，就可以對每個結(jié)點做一條垂線，映射到下面的水平線上，由此得到的順序就是該二叉樹的中序遍歷序列。2/1/202342DGBAECHF

GHDEFBCA2/1/202343

（2）任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為二叉樹的包線，這條包線對于理解二叉樹的遍歷過程很有用。GHDEFBCA2/1/202344由此可以看出：（1）遍歷操作實際上是將非線性結(jié)構(gòu)線性化的過程，其結(jié)果為線性序列，并根據(jù)采用的遍歷順序分別稱為先序序列、中序序列或后序序列；（2）遍歷操作是一個遞歸的過程，因此，這三種遍歷操作的算法可以用遞歸函數(shù)實現(xiàn)。

ABCDFHEG2/1/202345（2）遍歷算法先序遍歷：DLR中序遍歷：LDR后序遍歷：LRDADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過程ABDCBDACDBCA2/1/202346VoidPreOderTraverse(BiTreeT){if(T!=NULL){

printf(T->data);

PreOrderTraverse(T->lchild);

PreOrderTraverser(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);2/1/202347中序遍歷二叉樹的遞歸算法：

voidinOrderTraverse(BiTreeT){if(T!=NULL){inOrderTraverse(T->lchild);

printf(T->data);

inOrderTraverse(T->rchild);}}后序遍歷二叉樹的遞歸算法：

voidPostOrderTraverse(BiTreeT){if(T!=NULL){PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

printf(T->data);}}2/1/202348

CDBFGEA

#5

若二叉樹的先序遍歷為:ABCDEFG（ABECDFGHIJ），中序遍歷為:CBDAFEG（EBCDAFHIGJ），求二叉樹的后序遍歷序列。

先序遍歷中的第一個元素必為二叉樹的根結(jié)點。中序遍歷中的根結(jié)點恰為左、右子樹的分界點。先序遍歷:ABCDEFG中序遍歷:CBDAFEG2/1/202349

（3）遍歷二叉樹的應(yīng)用

1)建立一棵二叉樹

(在遍歷過程生成結(jié)點，建立二叉樹的存儲結(jié)構(gòu)，用鏈?zhǔn)酱鎯Y(jié)構(gòu)）BiTree

CreatBiTree(){BiTreeT;

scanf(&ch);

if(ch==

)T=NULL;else{T=(BiTNode)malloc(sizeof((BiTNode));T->data=ch;/*生成根結(jié)點*/T->lchild=CreatBiTree();/*構(gòu)造左子樹*/T->rchild=CreatBiTree();/*構(gòu)造右子樹*/}return(T);}ADBCABDCABΦDΦΦCΦΦ按先序遍歷2/1/202350ch=ATTAcreat(TL)ΛT=Λ,Creat(T)

返回creat(TR)Tch=ΦDΛ||=返回creat(TR)D=Tch=ΦΛΛ返回ch=DTTDcreat(TL)=||ΦΦcreat(TR)ch=CTTCcreat(TL)–+ch=BTTBcreat(TL)ΦTch=ΦBΦΛTCΛch=Φ–+返回creat(TR)TCΛch=ΦΛ+返回ATABΦΛABΛD||=ABΛDΛΛABΛDΛΛC–+BΦA(chǔ)ABΛDΛΛCΛΛ2/1/202351

2）統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)方法：對二叉樹進(jìn)行遍歷，判斷被訪問的結(jié)點是否葉子結(jié)點，若是葉子結(jié)點，則將計數(shù)器加1。實現(xiàn)算法：int

countleaf(BiTree){intn1,n2;

if(T==NULL) return(0);

elseif(T->lchild==NULL)&&(T->rchild==NULL)return(1);else{n1=countleaf(T->lchild);n2=countleaf(T->rchild);return(n1+n2);}}2/1/202352(4)按層次遍歷二叉樹實現(xiàn)方法為從上層到下層，每層中從左側(cè)到右側(cè)依次訪問每個結(jié)點。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結(jié)點的遍歷序列。GHDEFBCA按層次遍歷該二叉樹的序列為：

ABCDEFGH2/1/202353二叉樹用順序存儲結(jié)構(gòu)表示時，按層遍歷的算法實現(xiàn)A1B23C

D45EF67G(a)A1B23CD4E67F(b)圖6-202/1/202354voidLevelOreder(QBTreeBT){for(i=1;i<=BT.n;i++)if(BT.item[i]!=’#’)Visite(BT.item[i]);}

2/1/202355訪問過程描述如下：訪問根結(jié)點，并將該結(jié)點記錄下來；若記錄的所有結(jié)點都已處理完畢，則結(jié)束遍歷操作；否則重復(fù)下列操作。取出記錄中第一個還沒有訪問孩子的結(jié)點，若它有左孩子，則訪問左孩子，并將記錄下來；若它有右孩子，則訪問右孩子，并記錄下來。二叉樹用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示時，按層遍歷的算法實現(xiàn)。2/1/202356在這個算法中，應(yīng)使用一個隊列結(jié)構(gòu)完成這項操作。所謂記錄訪問結(jié)點就是入隊操作；而取出記錄的結(jié)點就是出隊操作。這樣一來，我們的算法就可以描述成下列形式：（1）訪問根結(jié)點，并將根結(jié)點入隊；（2）當(dāng)隊列不空時，重復(fù)下列操作：從隊列退出一個結(jié)點；若其有左孩子，則訪問左孩子，并將其左孩子入隊；若其有右孩子，則訪問右孩子，并將其右孩子入隊；2/1/202357

6.4樹和森林

1.樹的存儲結(jié)構(gòu)

(1)雙親表示法樹的雙親表示法主要描述的是結(jié)點的雙親關(guān)系。2/1/202358ABDCEFGHIJ2/1/202359類型定義：#defineMAX_TREE_NODE_SIZE100typedef

struct{

TEntryTypeinfo;

intparent;//雙親位置域}ParentNode;typedef

struct{

ParentNodeitem[MAX_TREE_NODE_SIZE];

intn;//樹中當(dāng)前的結(jié)點數(shù)目}ParentTree;2/1/202360這種存儲方法的特點是尋找結(jié)點的雙親很容易，但尋找結(jié)點的孩子比較困難。算法實現(xiàn)舉例：

int

Parent(ParentTree

T,intnode){if(node<0||node>=T.n)return-2;elsereturnT.item[node].parent;}2/1/202361(2)孩子表示法孩子表示法主要描述的是結(jié)點的孩子關(guān)系。由于每個結(jié)點的孩子個數(shù)不定，所以利用鏈?zhǔn)酱鎯Y(jié)構(gòu)更加適宜。舉例：2/1/202362root0A214^1C^2B35^3E^4D6^5F^6G789^7H^8I^9J^2/1/202363在C語言中，這種存儲形式定義如下：#defineMAX_TREE_NODE_SIZE10typedef

struct

ChildNode{

intchild;//該孩子結(jié)點在一維數(shù)組中的下標(biāo)值

struct

ChileNode*next;//指向下一個孩子結(jié)點}CNode;typedef

struct{

TEntryTypeinfo;//結(jié)點信息

CNode*firstchild;//指向第一個孩子結(jié)點的指針}TNode;2/1/202364

typedef

struct{

TNodeitem[MAX_TREE_NODE_SIZE];

intn,root;

//n為樹中當(dāng)前結(jié)點的數(shù)目，root為根結(jié)點在一維數(shù)組中的位置

}ChildTree;

這種存儲結(jié)構(gòu)的特點是尋找某個結(jié)點的孩子比較容易，但尋找雙親比較麻煩，所以，在必要的時候，可以將雙親表示法和孩子表示法結(jié)合起來，即將一維數(shù)組元素增加一個表示雙親結(jié)點的域parent，用來指示結(jié)點的雙親在一維數(shù)組中的位置。2/1/202365獲取給定結(jié)點第i個孩子的操作算法實現(xiàn)：int

Child(ChildTreeT,intnode,inti){if(node<0||node>=T.n)return-2；

p=T.item[node].firstchild;j=1;while(p&&j!=i){p=p->next;j++;}

if(!p)return-2;

elsereturnp->child;}2/1/202366(3)孩子兄弟表示法孩子兄弟表示法也是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。它通過描述每個結(jié)點的一個孩子和兄弟信息來反映結(jié)點之間的層次關(guān)系，其結(jié)點結(jié)構(gòu)為：

其中，firstchild為指向該結(jié)點第一個孩子的指針，nextsibling為指向該結(jié)點的下一個兄弟，item是數(shù)據(jù)元素內(nèi)容。舉例：2/1/202367^H^I^J^^E^F^G^B^CD^A^T2/1/202368在C語言中，這種存儲形式定義如下：typedef

struct

CSNode{

EntryTypeitem;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree;voidAllChild(CSTreeT,CSTreep)//輸出樹中p指針?biāo)附Y(jié)點的所有孩子信息{q=p->fisrtchild;while(q){

printf(“%c”,q->item);q=q->nextsibling;}}2/1/202369voidLevelOrder(BTree*BT){if(!BT)exit;

InitQueue(Q);p=BT;//初始化

Visite(p);EnQueue(&Q,p);//訪問根結(jié)點，并將根結(jié)點入隊

while(!QueueEmpty(Q)){//當(dāng)隊非空時重復(fù)執(zhí)行下列操作

DeQueue(&Q,&p);//出隊

if(!p->Lchild){Visite(p->Lchild);EnQueue(&Q,p->Lchild);//處理左孩子

if(!p->Rchild){Visite(p->Rchild);EnQueue(&Q,p->Rchild);//處理右孩子

}}2/1/202370

2、將樹和森林轉(zhuǎn)換為二叉樹

由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈表表示，必須找出樹與二叉樹之間的關(guān)系。這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。（1）樹轉(zhuǎn)換為二叉樹方法：·對每個孩子進(jìn)行從左到右的排序；

·在兄弟之間加一條連線；

·對每個結(jié)點，除了左孩子外，去除其與其余孩子之間的聯(lián)系；

·以根結(jié)點為軸心，將整個樹順時針轉(zhuǎn)45度。2/1/202371

I

A

B

C

DEF

G

H(b)

A

B

CDE

G

HFI(a)樹轉(zhuǎn)換為二叉樹ABEFCDGHI(d)ABCDEFGHI(c)2/1/202372

A

B

CDE

G

HFI二叉樹轉(zhuǎn)換為樹ABEFCDGHI(a)ABEFCDGHI(b)c若結(jié)點X是其雙親Y的左孩子，則把X的右孩子，右孩子的右孩子，…，都與Y用連線連起來，最后去掉所有雙親到右孩子的連線.2/1/202373

（2）森林轉(zhuǎn)換為二叉

樹ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：·將各棵樹分別轉(zhuǎn)成二叉樹；·把每棵樹的根結(jié)點用線連起來；·以第一棵樹的根結(jié)點作為二叉樹的根結(jié)點，按順時針方向旋轉(zhuǎn)。2/1/202374

二叉樹轉(zhuǎn)換為森林ADCBEFHIGJEFADCBHIGJADCBEFHIGJEFADCBHIGJ方法：·將二叉樹轉(zhuǎn)成若干棵二叉樹;·將各棵樹二叉樹分別轉(zhuǎn)成樹；2/1/202375

6.6哈夫曼樹及其應(yīng)用

1、哈夫曼樹

樹的路徑長度的概念：

(1)結(jié)點之間的路徑長度：從一個結(jié)點到另一個結(jié)點之間的分支數(shù)目稱為這對結(jié)點之間的路徑長度。（2）樹的路徑長度：是從樹的根到每一結(jié)點的路徑長度之和。2/1/2023761245367PL=0+1+1+2+2+2+2=10樹的路徑長度用PL表示。2/1/2023771245367PL=0+1+1+2+2+2+2=101245C67PL=0+1+1+2+2+3+3=12樹的路徑長度用PL表示。2/1/202378

結(jié)點帶權(quán)的路徑長度：

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

樹中所有葉子結(jié)點帶權(quán)路徑長度之和。

abcd7524WPL=7*2+5*2+2*2+4*2=362/1/202379樹的帶權(quán)路徑長度記作：

其中：Wk為樹中每個葉子結(jié)點的權(quán)；

Lk為每個葉子結(jié)點到根的路徑長度。abcd7524WPL=7*2+5*2+2*2+4*2=36WPL最小的二叉樹就稱作最優(yōu)二叉樹或哈夫曼樹。2/1/202380abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35哈夫曼樹（最優(yōu)樹）帶權(quán)路徑長度最小的二叉樹就是哈夫曼樹。公式：2/1/202381675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)2、哈夫曼樹的構(gòu)造例：給定權(quán)值{7，5，2，4}，構(gòu)造哈夫曼樹。方法：（1）由原始數(shù)據(jù)生成森林；(2)在森林中選取兩棵根結(jié)點權(quán)值最小的和次小的二叉樹作為左右子樹構(gòu)造一棵新的二叉樹，其根結(jié)點的權(quán)值為左右子樹根結(jié)點權(quán)值之和。規(guī)定左子樹根結(jié)點的權(quán)值小于右子樹根結(jié)點的權(quán)值。（3）將新的二叉樹加入到森林F中，去除原兩棵權(quán)值最小的樹；（4）重復(fù)2、3步驟，直至F中只剩一棵樹為止。注意：參看書中P146的例子。2/1/2023823、哈夫曼樹的應(yīng)用（1）判定樹在解決某些判定問題時，利用哈夫曼樹可以得到最佳判定算法。例1將學(xué)生百分成績按分?jǐn)?shù)段分級的程序。若學(xué)生成績分布是均勻的，可用圖（a)二叉樹結(jié)構(gòu)來實現(xiàn)。a<60

a<70

a<80

a<90

不及格中等良好優(yōu)秀及格YNYNYNYN(a)輸入10000個數(shù)據(jù)，則需進(jìn)行31500次比較。2/1/202383分?jǐn)?shù)0—5960—6970—7980—8990—99比例0.050.150.40.30.1070≤a≤80

a<60

及格中等良好80≤a<90

60≤a<70

不及格優(yōu)秀YNYYYNNN(b)不及格Ya<90

a<80

a<70

a<60

優(yōu)秀中等及格良好YNNN(c)YYY學(xué)生成績分布不是均勻的情況：以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼樹，如（b)判斷樹所示。再將每一比較框的兩次比較改為一次，可得到（c)判定樹。輸入10000個數(shù)據(jù)，僅需進(jìn)行22000次比較。2/1/202384146833442200001111T;ACS各字符編碼是T；

ACS

000110110111上述電文編碼：11010111011101000011111000011000方法：（1）用{2，4，2，3，3}作為葉子結(jié)點的權(quán)值生成一棵哈夫曼樹，并將對應(yīng)權(quán)值wi的葉子結(jié)點注明對應(yīng)的字符；（2）約定左分支表示字符“0”，右分支表示字符‘1’（3）從葉子結(jié)點開始，順著雙親反推上去，直到根結(jié)點，路徑上的‘0’或‘1’連接的序列就是結(jié)點對應(yīng)的字符的二進(jìn)制編碼的逆序。（2）哈夫曼編碼-----利用哈夫曼樹構(gòu)造通訊中電文編碼（前綴碼）例2：要傳輸?shù)碾娢氖莧CAS；CAT；SAT；AT}要傳輸?shù)淖址荄={C，A，S，T，；}每個字符出現(xiàn)的頻率是W={2，4，2，3，3}注意：編碼的總長度恰好為哈夫曼樹的帶權(quán)路徑長。2/1/202385作業(yè)#1.有n個葉子結(jié)點的哈夫曼樹，其結(jié)點總數(shù)為2n-12/1/20238635817115592728CDAEB00001111#2.

設(shè)電文中出現(xiàn)的字符為A,B,C,D,E，每個字母在電文中出