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

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

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹。若D僅含一個數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；（2）若D-{root}≠￠，則存在D-{root}的一個劃分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>}有唯一的一個劃分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)的最初體系，他所著的《計算機程序設(shè)計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作?；静僮鳎海?）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)的最初體系，他所著的《計算機程序設(shè)計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。（10）DeleteChild(&T,p,i)

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

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

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

1

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

思考：深度為k時至少有

個結(jié)點？k5.2二叉樹的定義、性質(zhì)和抽象數(shù)據(jù)類型5.2.2二叉樹的性質(zhì)（3）性質(zhì)3：對任何一棵二叉樹T，如果葉子結(jié)點總數(shù)為n0，度為2的結(jié)點總數(shù)為n2，則有n0=n2+1。證明：假設(shè)二叉樹中結(jié)點總數(shù)為n，度為1的結(jié)點總數(shù)為n1。則：n=n0+n1+n2。假設(shè)二叉樹的分支數(shù)為Y，有n=Y+1。二叉樹的所有分支都是由度為1和度為2的結(jié)點發(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個結(jié)點，則深度為

log2n

+1。符號表示不大于x的最大整數(shù)。證明：假設(shè)具有n個結(jié)點的完全二叉樹的深度為k。k層完全二叉樹的結(jié)點個數(shù)介于k-1層滿二叉樹與k層滿二叉樹結(jié)點個數(shù)之間。根據(jù)性質(zhì)2，k-1層滿二叉樹的結(jié)點總數(shù)為n1=2k-1-1，k層滿二叉樹的結(jié)點總數(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ù)，有k-1≤log2n<k。因為k是整數(shù)，k-1也是整數(shù)，所以k-1=

log2n

，即k=

log2n

+1。命題成立。

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

一棵完全二叉樹有2000個結(jié)點，則其葉結(jié)點的個數(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é)點、再訪問左子樹、最后訪問右子樹，對二叉樹中的每個結(jié)點訪問且僅訪問一次。（11）InOrderTraverse(T)

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

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

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

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

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

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

{

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

++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é)點

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

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

{

if(T!=null){

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

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

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

}

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

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

{

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

inttop=0;BiTreeNodep=T;

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

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

{

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

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

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é)點

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

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

{PostOrderTraverse(T.lchild);

PostOrderTraverse(T.rchild);

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

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

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

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

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é)點，或右孩子結(jié)點已經(jīng)訪問過

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

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

p=null;//為遍歷右子樹做準備

top--;//出棧

}

elsep=p.rchild;

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

個空指針域。AB

D

E

F

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

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

this.lchild=null;//左孩子

this.rchild=null;//右孩子

this.ltag=0;//線索標志域

this.rtag=0;//線索標志域

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

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

{

BiThrNodethrt=newBiThrNode();

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

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

thrt.rtag=1;//修改后繼線索標志

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

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

thrt.lchild=thrt;

else{

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

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

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

//將最后一個結(jié)點線索化

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

pre.rtag=1;//修改最后一個結(jié)點的rtag標志域

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

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

}

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é)點線索化完畢，使p指向的結(jié)點成為前驅(qū)

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

}

returnp;

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

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

{

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

returnp.lchild;

else{

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

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

pre=pre.rchild;

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

}

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

//中序遍歷線索二叉樹

{

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

while(p!=T){

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

p=p.lchild;

Print(p);

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

p=p.rchild;

Print(p);

}

p=p.rchild;

}

}5.4二叉樹的線索化【例5.1】編寫程序，建立如圖5-21所示的二叉樹，并將其中序線索化。任輸入一個結(jié)點，輸出該結(jié)點的中序前驅(qū)和中序后繼。例如，結(jié)點’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ù)的存儲單元存儲樹的每個結(jié)點，并利用一個指示器表示結(jié)點的雙親結(jié)點在樹中的相對位置。通常在Java語言中，利用數(shù)組實現(xiàn)連續(xù)的單元的存儲。樹的雙親表示法如圖5-23所示。5.5.1樹的存儲結(jié)構(gòu)5.5樹、森林與二叉樹classPNode//雙親表示法的結(jié)點定義

{

Stringdata;

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

}

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

{

PNodenode[];

intnum;//結(jié)點的個數(shù)

PTree()

{

node=newPNode[num];

}

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

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

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

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

{introot=x;

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

root=parent[root];

inty=x;

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

{parent[y]=root;

y=parent[y];

}

returnroot;

}5.6并查集3.合并合并算法主要思想：找到x和y所屬子樹的根結(jié)點root_x和root_y，若root_x==root_y，則表明它們屬于同一棵子樹，不需合并；否則，需要比較兩棵子樹的高度，即秩，使合并后的子樹高度盡可能小：給你一個由'1'（陸地）和'0'（水）組成的的二維網(wǎng)格，請你計算網(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ù)量，就是一個利用并查集的合并操作，將所有的元素都合并完，再去還剩下多少個獨立集合的問題。每一個島嶼就是一個獨立的集合。這里有一個注意點就是需要區(qū)分不同的樣本，顯然要進行合并的樣本的值都是字符’1’。5.6并查集發(fā)送電文過程中，要將待傳字符轉(zhuǎn)換成二進制的字符串，怎樣編碼才能使轉(zhuǎn)換后的報文盡快發(fā)送？BAAACCCADB010000001010100011010000011100100原則：頻率高的字符編碼盡可能地短5.7哈夫曼樹哈夫曼（Huffman）樹，也稱最優(yōu)二叉樹。它是一種帶權(quán)路徑長度最短的樹。A：00B：01C：10D：11A：0B：00C：1D：01編碼短注意：在編碼時，必須保證任何一個字符的編碼不能是其他字符編碼的前綴字符串。AAAAAAAABBAAABBA歧義BAAACCCADB00000111001005.7哈夫曼樹A：0B：00C：1D：01DCAB000111A：110B：111C：10D：0

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

10100011111101111105.7哈夫曼樹使用二叉樹對結(jié)點進行編碼是無歧義的，這種編碼就是前綴編碼譯碼時，從根結(jié)點出發(fā)，掃描字符串，遇到0訪問左孩子結(jié)點，遇到1訪問右孩子結(jié)點，直到葉子結(jié)點，葉子結(jié)點的字符即為該編碼對應(yīng)的字符。BAAACCCADB特點：每一個字符的編碼都不是其他字符編碼的前綴，絕不會錯譯!稱為前綴碼5.7哈夫曼樹1010001111110111110ACDB0001115.7哈夫曼樹1.路徑和路徑長度路徑是指在樹中，從一個結(jié)點到另一個結(jié)點所走過的路程。路徑長度是一個結(jié)點到另一個結(jié)點的分支數(shù)目。2.樹的帶權(quán)路徑長度在一些實際應(yīng)用中，根據(jù)結(jié)點的重要程度，將樹中的某一個結(jié)點賦予一個有意義的值，則這個值就是結(jié)點的權(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個權(quán)值{w1,w2,…,wn}，構(gòu)成n棵只有根結(jié)點的二叉樹集合F={T1,T2,…,Tn}，每個結(jié)點的左右子樹均為空。（2）在二叉樹集合F中，找兩個根結(jié)點的權(quán)值最小和次小的樹，作為左、右子樹構(gòu)造一棵新的二叉樹，新二叉樹的根結(jié)點的權(quán)重為左、右子樹根結(jié)點的權(quán)重之和。（3）在二叉樹集合F中，刪除作為左、右子樹的兩個二叉樹，并將新二叉樹加入到集合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é)點為n個，則該哈夫曼樹結(jié)點總數(shù)為2n-1算法實現(xiàn)：定義一個類型為HuffmanCode的變量HT，用來存放每一個葉子結(jié)點的哈夫曼編碼。初始時，將每一個葉子結(jié)點的雙親結(jié)點域、左孩子域和右孩子域初始化為0。如果有n個葉子結(jié)點，則非葉子結(jié)點有n-1個，所以總共結(jié)點數(shù)目是2*n-1個。5.7哈夫曼樹若n=4,w={1,3,6,9}，請構(gòu)造哈夫曼樹和哈夫曼編碼結(jié)點總個數(shù)：m=2*4-1=7weightparentlchrch11000230003600049000567weightparentlchrch1150023500366004970054612610753719046a9c6a1b35.7哈夫曼樹初始狀態(tài)最終狀態(tài)000publicvoidHuffmanCoding(HTNodeHT[],StringHC[],intw[],intn)//構(gòu)造哈夫曼樹HT，哈夫曼樹的編碼存放在HC中，w為n個字符的權(quán)值{if(n<=1)return;intm=2*n-1;for(inti=1;i<=n;i++)//初始化n個葉子結(jié)點

{HT[i]=newHTNode();HT[i].w