第6章樹和二叉樹

DATA1065865ABCDEFG數(shù)據(jù)結構第6章樹和二叉樹主講：李澤平2/1/20231學習提要

第6章樹

1.熟練掌握二叉樹的結構特性，了解相應的證明方法。

2.熟悉二叉樹的各種存儲結構的特點及適用范圍。

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

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

5.熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉換方法。

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

1．數(shù)據(jù)的邏輯結構

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

B鏈式存儲線性表棧隊樹形結構圖形結構數(shù)據(jù)結構的三個主要問題串、數(shù)組和廣義表2/1/20233線性結構

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

1．數(shù)據(jù)的邏輯結構

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

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

A

C

GT2D

HIT3J

M

BEL

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

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

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

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

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

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

終端結點（葉子）：度為0的結點。

非終端結點：度不為0的結點。

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

樹的度：樹中所有結點度的最大值。

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

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

A

C

G

T2D

HI

T3J

M

BEL

KT1F2/1/202311

森林:

是m（m≥0）棵互不相交的樹的集合。在樹結構中，結點之間的關系又可以用家族關系描述，定義如下：

孩子、雙親:

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

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

從根結點到該結點路徑上的所有結點。

兄弟:

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

堂兄弟:

雙親在同一層的結點互為堂兄弟。

A

C

GT2D

HIT3J

M

BEL

KT1F2/1/202312

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

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

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

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

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

（6）遍歷樹Traverse(T)

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

(1)二叉樹的定義二叉樹的五種基本形態(tài)二叉樹一種特殊的樹型結構，特點是樹中每個結點只有兩棵子樹，且子樹有左右之分，次序不能顛倒。空二叉樹

僅有根結點

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

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

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

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

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

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

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

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

3．請分析線性表、樹、廣義表的主要結構特點，以及相互的差異與關聯(lián)。【10】

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

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

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

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

B)

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

性質2：深度為k的二叉樹中至多含有2k-1個結點。證明：由性質1可以得出，1至K層各層最多的結點個數(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）個結點。B)

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

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

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

n=n0+n1+n2（1）再查看一下分支數(shù)。在二叉樹中，除根結點之外，每個結點都有一個從上向下的分支指向，所以，總的結點個數(shù)n與分支數(shù)B之間的關系為：n=B+1。2/1/202324又因為在二叉樹中，度為1的結點產(chǎn)生1個分支，度為2的結點產(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

性質4:具有n個結點的完全二叉樹的深度為[log2n]+1。其中，[log2n]的結果是不大于log2n的最大整數(shù)。證明：假設具有n個結點的完全二叉樹的深度為K，則根據(jù)性質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

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

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

i

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

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

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

二叉樹樹2/1/2023342、二叉樹的存儲結構

(2)鏈式存儲結構T[16]若父結點在數(shù)組中i下標處，其左孩子在2*i處，右孩子在2*i+1處。11ABCFED

●●●●●●●●●124

8

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

struct

BiTNode{

int

data;

Struct

BiTNode

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

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

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

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

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

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

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

GHDEFBCA2/1/202343

（2）任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為二叉樹的包線，這條包線對于理解二叉樹的遍歷過程很有用。GHDEFBCA2/1/202344由此可以看出：（1）遍歷操作實際上是將非線性結構線性化的過程，其結果為線性序列，并根據(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），求二叉樹的后序遍歷序列。

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

（3）遍歷二叉樹的應用

1)建立一棵二叉樹

(在遍歷過程生成結點，建立二叉樹的存儲結構，用鏈式存儲結構）BiTree

CreatBiTree(){BiTreeT;

scanf(&ch);

if(ch==

)T=NULL;else{T=(BiTNode)malloc(sizeof((BiTNode));T->data=ch;/*生成根結點*/T->lchild=CreatBiTree();/*構造左子樹*/T->rchild=CreatBiTree();/*構造右子樹*/}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ΦAABΛDΛΛCΛΛ2/1/202351

2）統(tǒng)計二叉樹中葉子結點的個數(shù)方法：對二叉樹進行遍歷，判斷被訪問的結點是否葉子結點，若是葉子結點，則將計數(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)方法為從上層到下層，每層中從左側到右側依次訪問每個結點。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結點的遍歷序列。GHDEFBCA按層次遍歷該二叉樹的序列為：

ABCDEFGH2/1/202353二叉樹用順序存儲結構表示時，按層遍歷的算法實現(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訪問過程描述如下：訪問根結點，并將該結點記錄下來；若記錄的所有結點都已處理完畢，則結束遍歷操作；否則重復下列操作。取出記錄中第一個還沒有訪問孩子的結點，若它有左孩子，則訪問左孩子，并將記錄下來；若它有右孩子，則訪問右孩子，并記錄下來。二叉樹用鏈式存儲結構表示時，按層遍歷的算法實現(xiàn)。2/1/202356在這個算法中，應使用一個隊列結構完成這項操作。所謂記錄訪問結點就是入隊操作；而取出記錄的結點就是出隊操作。這樣一來，我們的算法就可以描述成下列形式：（1）訪問根結點，并將根結點入隊；（2）當隊列不空時，重復下列操作：從隊列退出一個結點；若其有左孩子，則訪問左孩子，并將其左孩子入隊；若其有右孩子，則訪問右孩子，并將其右孩子入隊；2/1/202357

6.4樹和森林

1.樹的存儲結構

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

struct{

TEntryTypeinfo;

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

struct{

ParentNodeitem[MAX_TREE_NODE_SIZE];

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

int

Parent(ParentTree

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

struct

ChildNode{

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

struct

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

struct{

TEntryTypeinfo;//結點信息

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

typedef

struct{

TNodeitem[MAX_TREE_NODE_SIZE];

intn,root;

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

}ChildTree;

這種存儲結構的特點是尋找某個結點的孩子比較容易，但尋找雙親比較麻煩，所以，在必要的時候，可以將雙親表示法和孩子表示法結合起來，即將一維數(shù)組元素增加一個表示雙親結點的域parent，用來指示結點的雙親在一維數(shù)組中的位置。2/1/202365獲取給定結點第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)孩子兄弟表示法孩子兄弟表示法也是一種鏈式存儲結構。它通過描述每個結點的一個孩子和兄弟信息來反映結點之間的層次關系，其結點結構為：

其中，firstchild為指向該結點第一個孩子的指針，nextsibling為指向該結點的下一個兄弟，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指針所指結點的所有孩子信息{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);//訪問根結點，并將根結點入隊

while(!QueueEmpty(Q)){//當隊非空時重復執(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、將樹和森林轉換為二叉樹

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

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

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

·以根結點為軸心，將整個樹順時針轉45度。2/1/202371

I

A

B

C

DEF

G

H(b)

A

B

CDE

G

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

A

B

CDE

G

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

（2）森林轉換為二叉

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

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

6.6哈夫曼樹及其應用

1、哈夫曼樹

樹的路徑長度的概念：

(1)結點之間的路徑長度：從一個結點到另一個結點之間的分支數(shù)目稱為這對結點之間的路徑長度。（2）樹的路徑長度：是從樹的根到每一結點的路徑長度之和。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

結點帶權的路徑長度：

從該結點到樹根之間的路徑長度與結點上權的乘積。樹的帶權路徑長度：

樹中所有葉子結點帶權路徑長度之和。

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

其中：Wk為樹中每個葉子結點的權；

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

a<70

a<80

a<90

不及格中等良好優(yōu)秀及格YNYNYNYN(a)輸入10000個數(shù)據(jù)，則需進行31500次比較。2/1/202383分數(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學生成績分布不是均勻的情況：以比例數(shù)為權構造一棵哈夫曼樹，如（b)判斷樹所示。再將每一比較框的兩次比較改為一次，可得到（c)判定樹。輸入10000個數(shù)據(jù)，僅需進行22000次比較。2/1/202384146833442200001111T;ACS各字符編碼是T；

ACS

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

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