《數(shù)據(jù)結構》課件第6章

第6章樹和二叉樹6.1樹的基本概念6.2樹的存儲結構和基本操作6.3二叉樹的定義和基本性質(zhì)6.4二叉樹的存儲結構和基本操作6.5二叉樹的遍歷6.6樹和森林與二叉樹之間的關系6.7哈夫曼樹及其應用本章小結習題六實訓6-1樹的存儲結構實訓6-2二叉樹的遍歷及應用實訓6-3哈夫曼編碼

【教學目標】通過對本章的學習，理解樹和二叉樹的基本概念及遞歸定義，掌握樹的存儲結構和基本操作，掌握二叉樹的基本性質(zhì)，重點掌握二叉樹的各種存儲結構以及鏈式存儲結構上各種基本操作的實現(xiàn)，重點掌握二叉樹的遍歷方法，熟練掌握樹、森林和二叉樹之間的轉(zhuǎn)換方法，熟悉哈夫曼樹的建立過程和哈夫曼編碼。6.1樹的基本概念6.1.1樹的定義樹是n(n≥0)個結點的有限集合T。當n=0時，稱為空樹；當n>0時，該集合滿足如下條件：

(1)其中必有一個稱為根(Root)的特定結點，它沒有直接前驅(qū)，但有零個或多個直接后繼。

(2)其余n-1個結點可以劃分成m(m≥0)個互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根Root的子樹(Subtree)。每棵子樹的根結點有且僅有一個直接前驅(qū)，但有零個或多個直接后繼。在現(xiàn)實生活中有很多樹形結構的例子。例如本書的目錄就是樹形結構。本書共分9章，每一章又分為若干節(jié)，每一節(jié)又分為若干小節(jié)，這樣就構成了一個典型的樹的實例。又如家族的血緣關系，A有三個孩子B1、B2、B3；B1有三個孩子C1、C2、C3；B2有兩個孩子C4、C5；C1有兩個孩子D1、D2，構成了一個四世同堂的大家族，A就是這棵家族大樹的根。在樹的定義中要特別注意非空樹的兩個特點：

(1)樹中至少有一個結點——根。

(2)樹中各子樹是互不相交的集合。結合圖6.1不難了解上面提到的這些特點，同時，大家還要看到樹定義的遞歸性。圖6.1樹形表示法6.1.2樹的邏輯表示

1.樹的邏輯結構描述樹的邏輯結構可用如下形式描述：

Tree?=?(D，R)其中，D為具有相同性質(zhì)的數(shù)據(jù)元素的集合，R為D上元素之間的關系的集合，如圖6.1中有子樹的那棵樹:D={A,B,C,D,E,F,G,H,I,J,K,L,M}R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>,<E,K>,<E,L>,<H,M>}

2.樹的邏輯表示樹的邏輯表示方式有很多種，常見的有以下幾種：

(1)樹形表示法。它像日常生活中的樹木一樣，整個圖是一棵倒立的樹，從根結點出發(fā)向下擴展，根結點在最上層，葉子結點在最下面，如圖6.1所示。

(2)凹入表示法。圖形的一端，所有的結點對齊，根結點用最長的矩形表示，同一層的結點用相同長度的矩形表示，層次越高，矩形長度越短，如圖6.2(a)所示。

(3)嵌套表示法。類似數(shù)學中所說的文氏圖表示法，如圖6.2(b)所示。圖6.2樹的邏輯表示(a)凹入表示法；(b)嵌套表示法

(4)廣義表表示法。用廣義表的形式表示時根結點排在最前面，用一對圓括號把它的子樹結點括起來，子樹結點之間用逗號隔開。圖6.1用廣義表表示如下：(A(B(E(K，L)，F(xiàn))，C(G)，D(H(M)，I，J))6.1.3樹的基本術語結點(node)——包含一個數(shù)據(jù)元素及若干指向其它結點的分支信息。結點的度(degree)——一個結點的子樹個數(shù)稱為此結點的度。圖6.1中，結點A的度為3，B的度為2，L的度為0。葉結點(leaf)——度為0的結點，即無后繼的結點，也稱為終端結點。圖6.1中，結點K、L、F、G、M、I、J都是葉結點。分支結點——度不為0的結點，也稱為非終端結點。圖6.1中，結點A、B、C、D、E、H都是分支結點。孩子結點(child)——一個結點的直接后繼稱為該結點的孩子結點。圖6.1中，結點B、C是A的孩子。雙親結點(parents)——一個結點的直接前驅(qū)稱為該結點的雙親結點。圖6.1中，結點A是B、C的雙親。兄弟結點(sibling)——同一雙親結點的孩子結點之間互稱兄弟結點。圖6.1中，結點H、I、J互為兄弟結點。祖先結點——一個結點的祖先結點是指從根結點到該結點的路徑上的所有結點。圖6.1中，結點K的祖先是A、B、E。子孫結點——一個結點的直接后繼和間接后繼稱為該結點的子孫結點。圖6.1中，結點D的子孫是H、I、J、M。樹的度——樹中所有結點的度的最大值。圖6.1中，樹的度為3。結點的層次——從根結點開始定義，根結點的層次為1，根的直接后繼的層次為2，依此類推。圖6.1中，結點B、C、D在第2層，K、L、M在第4層。樹的高度(深度)(depth)——樹中所有結點的層次的最大值。圖6.1中，樹的高度為4。有序樹——在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。森林(forest)——m(m≥0)棵互不相交的樹的集合。將一棵非空樹的根結點刪去，樹就變成一個森林；反之，給森林增加一個統(tǒng)一的根結點，森林就變成一棵樹。6.1.4樹的基本概念分析以圖6.1中的樹為例，設結點總數(shù)為n，樹的度為m，其中度為0,1,2,…,m的結點個數(shù)分別表示為n0,n1,n2,…,nm，顯然

N?=?n0?+?n1+n2+…+nm

(6-1)設樹的分支總數(shù)為B，從上往下看就會發(fā)現(xiàn)，根據(jù)結點度的定義，度為0的結點下面沒有分支，度為m的結點下面有m個分支，所以，

B=0×n0+1×n1+2×n2+…+m×nm(6-2)如果從樹的最底層往上看就會發(fā)現(xiàn)，由于分支表示結點的父子關系，因此除了根結點之外，每一個結點只有一個分支進入，即每個結點有且僅有一個雙親結點，故

n?=?B?+?1(6-3)即結點度數(shù)之和?=?分支總數(shù)?=?結點總數(shù)-1

例6.1

已知一棵樹的度為4，其中度為1、2、3、4的結點的個數(shù)分別為6、5、4、3，求該樹中葉子結點的個數(shù)。解：樹的度為4，即樹中結點度的最大值為4。將已知條件分別代入式(6-1)、式(6-2)：n=n0+n1+n2+n3+n4=n0+6+5+4+3=n0+18B=1×6+2×5+3×4+4×3=40將n和B代入式(6-3)有n0+18=40+1，所以n0=23。答：樹中葉子結點的個數(shù)為23。6.2樹的存儲結構和基本操作6.2.1樹的存儲結構常用的樹的存儲結構有四種：雙親表示法；孩子表示法；帶雙親的孩子鏈表；孩子兄弟表示法(二叉鏈表表示法)。

1.雙親表示法雙親表示法利用樹中每個結點的雙親唯一性，在存儲結點信息的同時，為每個結點附設一個指向其雙親的指針parent，唯一地表示任何一棵樹。存儲結構的實現(xiàn)：用一組連續(xù)的存儲空間，即一維數(shù)組存儲樹中的各個結點，數(shù)組中的一個元素表示樹中的一個結點，數(shù)組元素為結構體類型。每個結點含數(shù)據(jù)域和雙親域兩個域，數(shù)據(jù)域中存放結點本身信息；雙親域指示本結點的雙親結點在數(shù)組中的位置。樹的雙親表示法如圖6.3所示。圖6.3樹的雙親表示法(a)樹；(b)樹的雙親表示法雙親表示法的C語言描述如下：/*0號單元不用或存放結點個數(shù)，假設數(shù)據(jù)項為字符型*/typedefstructnode{chardata;intparent;}PNODE;PNODEt[M];/*用結點數(shù)組表示樹*/用雙親表示法來表示樹結點之間的關系，很容易找到每一個結點(根結點除外)的雙親，但是誰是該結點的孩子，如何才能找到該結點的孩子，用這種表示法卻較難實現(xiàn)，也就是說雙親表示法找雙親容易，找孩子難。

2.孩子表示法樹中的每個結點都有零個或多個孩子結點，通常采用以下幾種方法來管理這些孩子結點。

1)多重鏈表每個結點有多個指針域，分別指向其子樹的根的表叫做多重鏈表。由于每個結點的孩子數(shù)(即結點的度)不盡相同，因此多重鏈表中設置孩子結點指針域個數(shù)的方法有兩種：

(1)結點同構。結點的指針個數(shù)相等，且為樹的度D。

(2)結點異構。結點指針個數(shù)不等，為該結點的度d。通常都采用結點同構的多重鏈表。圖6.3(a)所示樹的多重鏈表如圖6.4所示。圖6.4結點同構時樹的孩子表示法

2)孩子鏈表每個結點的孩子結點用單鏈表存儲，再用含n個元素的結構體數(shù)組指向每個孩子鏈表。孩子表示法的存儲結構包括兩個部分：一部分是表頭數(shù)組，表頭數(shù)組中的元素是結構體數(shù)據(jù)，由一個數(shù)據(jù)項(結點數(shù)據(jù)，假設是字符型)和一個指針項(指向結點的第一個孩子)構成；另一部分是孩子單鏈表，每個鏈表結點由一個整型數(shù)據(jù)(用來存放表頭數(shù)組元素的下標)和一個指針項(指向下一個孩子)構成。孩子結點的存儲結構如下：

typedefstructtnode{

intchild; /*該孩子結點在表頭數(shù)組中的下標*/

structtnode*next;/*指向下一個孩子結點*/

}TNODE;表頭結點的存儲結構如下：#defineM100 /*定義表頭數(shù)組最大存儲容量*/typedefstructtablenode{chardata; /*數(shù)據(jù)域*/TNODE*fchild; /*指向第一個孩子結點*/}TD;TDt[M+1]; /*t[0]單元不用*/圖6.3(a)所示樹的孩子鏈表表示法如圖6.5所示。圖6.5樹的孩子鏈表表示法

3.帶雙親的孩子鏈表用孩子表示法來表示結點之間的關系可以很容易找到結點的孩子，但是找它的雙親結點就比較困難。有沒有一種表示法可以把前面兩種表示法的優(yōu)點都繼承下來呢？為了讓結點既容易找到它的雙親結點又容易找到孩子結點，可用帶雙親的孩子鏈表來表示結點之間的存儲關系。這種存儲結構和孩子表示法有一點相似，只是在孩子表示法的表頭數(shù)組中增加了一列來作為雙親域，用來存放該結點的雙親在表頭數(shù)組中的位置。圖6.3(a)所示樹的帶雙親的孩子鏈表表示法如圖6.6所示。圖6.6樹的帶雙親的孩子鏈表存儲結構

4.孩子兄弟表示法(二叉鏈表表示法)圖6.7樹的孩子兄弟表示法的存儲結構孩子兄弟表示法也稱為二叉樹表示法或二叉鏈表表示法，即用二叉鏈表作樹的存儲結構。鏈表中的結點由左指針域、右指針域和數(shù)據(jù)域三個部分組成，左指針指向該結點的第一個孩子結點，右指針指向該結點的下一個兄弟結點。圖6.3(a)所示樹的孩子兄弟表示法如圖6.7所示。圖6.7樹的孩子兄弟表示法的存儲結構孩子兄弟表示法的C語言描述如下：typedefstructtnode{chardata;structtnode*lchild;structtnode*rsibling;}TNODE;用孩子兄弟表示法表示結點之間的關系，容易實現(xiàn)樹的各種操作。例如在圖6.7中查找結點B的第三個孩子結點F。設有一指針p指向結點B，則B的第三個孩子結點F可通過下列三個操作來查找：

p?=?p->lchild;p?=?p->rsibling;p?=?p->rsibling;如果在每個結點中增設一個雙親域，則很容易查找一個結點的雙親結點和樹的根結點。孩子兄弟表示法的特點是操作容易，但破壞了樹的層次結構關系。6.2.2樹的基本操作樹中常用的基本操作如下：

(1)?InitTree(Tree)?——將Tree初始化為一棵空樹。

(2)?DestoryTree(Tree)?——銷毀樹Tree。

(3)?CreateTree(Tree)——創(chuàng)建樹Tree。

(4)?ClearTree(Tree)——清空樹。

(5)?TreeEmpty(Tree)——若Tree為空，則返回TRUE，否則返回FALSE。

(6)?Root(Tree)——返回樹Tree的根。

(7)?TreeDepth(Tree)——返回樹的深度。

(8)?Parent(Tree，x)——樹Tree存在，x是Tree中的某個結點。若x為非根結點，則返回它的雙親，否則返回“空”。

(9)?FirstChild(Tree，x)——樹Tree存在，x是Tree中的某個結點。若x為非葉子結點，則返回它的第一個孩子結點，否則返回“空”。

(10)?NextSibling(Tree，x)——樹Tree存在，x是Tree中的某個結點。若x不是其雙親的最后一個孩子結點，則返回x的下一個兄弟結點，否則返回“空”。

(11)?InsertChild(Tree，p，Child)——樹Tree存在，p指向Tree中的某個結點，非空樹Child與Tree不相交。將Child插入Tree中，作為p所指向結點的子樹。

(12)?DeleteChild(Tree，p，i)——樹Tree存在，p指向Tree中的某個結點，1≤i≤d，d為p所指向結點的度。刪除Tree中p所指向結點的第i棵子樹。

(13)?TraverseTree(Tree，Visit())——樹Tree存在，Visit()是對結點進行訪問的函數(shù)。按照某種次序?qū)銽ree的每個結點調(diào)用Visit()函數(shù)訪問一次且最多一次。若Visit()失敗，則操作失敗。6.3二叉樹的定義和基本性質(zhì)6.3.1二叉樹的定義

1.定義二叉樹是n(n≥0)個結點的有限集，它或為空樹(n?=?0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成。

2.二叉樹的特點

(1)每個結點至多有二棵子樹(即不存在度大于2的結點)

(2)二叉樹的子樹有左、右之分，且其次序不能任意顛倒。

(3)二叉樹可以為空。

3.二叉樹的基本形態(tài)二叉樹的基本形態(tài)有五種，如圖6.8所示。圖6.8二叉樹的五種基本形態(tài)(a)空二叉樹；(b)只有根結點的二叉樹；(c)右子樹為空；(d)左子樹為空；(e)左、右子樹均非空

4.幾種特殊形式的二叉樹

1)滿二叉樹

(1)定義一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹，如圖6.9(a)所示。

(2)特點一層上的結點數(shù)都是最大結點數(shù)。滿二叉樹的順序表示，即從二叉樹的根開始，層間從上到下，層內(nèi)從左到右，逐層進行編號(1，2，…，n)。例如圖6.9(a)所示的滿二叉樹的順序表示為(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)。

2)完全二叉樹

(1)定義深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號1至n的結點一一對應時，稱為完全二叉樹，如圖6.9(b)所示。圖6.9滿二叉樹與完全二叉樹(a)滿二叉樹；(b)完全二叉樹

(2)特點①葉子結點只可能在層次最大的兩層上出現(xiàn)。②對任一結點，若其右分支下子孫的最大層次為L，則其左分支下子孫的最大層次必為L或L?+?1。滿二叉樹和完全二叉樹是二叉樹的特殊情形。滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。6.3.2二叉樹的基本性質(zhì)在這里介紹一下二叉樹的幾個重要的性質(zhì)，并對部分性質(zhì)進行證明。

性質(zhì)1

在二叉樹的第i層上至多有2i-1個節(jié)點(i≥1)。

證明用數(shù)學歸納法證明。

歸納基礎：當i?=?1時，整個二叉樹只有一個根結點，此時2i-1?=?20?=?1，結論成立。歸納假設：假設i?=?k時結論成立，即第k層上結點總數(shù)最多為2k-1個。現(xiàn)證明當i=k+1時，結論成立。因為二叉樹中每個結點的度最大為2，則第k+1層的結點總數(shù)最多為第k層上結點最大數(shù)的2倍，即2×2k-1=2(k+1)-１=2k，故結論成立。

性質(zhì)2

深度為k的二叉樹至多有2k-1個結點(k≥1)。

證明由性質(zhì)1，可得深度為k的二叉樹最大結點數(shù)是命題得證。

性質(zhì)3

對任何一棵二叉樹BT，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2，則n0?=?n2?+?1。

證明設n1為二叉樹BT中度為1的結點數(shù)，n為二叉樹T中的結點總數(shù)。因為二叉樹中所有結點的度均小于或等于2，所以該二叉樹中結點總數(shù)為

n?=?n0?+?n1?+?n2

(6-4)設二叉樹中分支數(shù)目為B，因為除根結點外，每個結點均對應一個進入它的分支，所以

n?=?B?+?1(6-5)又因為分支由度為1和度為2的結點射出，所以

B?=?n1?+?2?×?n2(6-6)將式(6-4)、式(6-6)分別代入式(6-5)，得到n0?+?n1?+?n2?=?n1?+?2?×?n2?+?1所以，n0?=?n2?+?1，命題得證。

性質(zhì)4

具有n個結點的完全二叉樹的深度為

log2n

+1。

log2n

表示取log2n的整數(shù)部分作為它的值。

證明假設n個結點的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結點總數(shù)為n1?=?2k-1-1k層滿二叉樹的結點總數(shù)為n2?=?2k-1顯然有n1<n≤n2，進一步可以推出n1+1≤n<n2+1。將n1=2k-1-1和n2=2k-1代入上式，可得2k-1≤n<2k，即k-1≤log2n<k。因為k是整數(shù)，所以k-1?=

log2n

，k?=?

log2n

+1，故結論成立。

性質(zhì)5

如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i(1≤i≤n)，有：

(1)如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是

i/2

。

(2)如果2i?>?n，則結點i無左孩子；如果2i≤n，則其左孩子是2i。

(3)如果2i+1>n，則結點i無右孩子；如果2i+1≤n，則其右孩子是2i+1。

例6.2

已知完全二叉樹結點總數(shù)為500，求葉子結點的數(shù)目。

分析：設完全二叉樹中度為1的結點的數(shù)目為n1，如果完全二叉樹的高度為k，由于k-1層滿二叉樹的結點總數(shù)為2k-1-1，且為奇數(shù)，因此在第k層添加1個結點時，n1?=?1，添加2個結點時，n1=0，…，所以，完全二叉樹中度為1的結點的數(shù)目n1只有兩種情形：解：據(jù)性質(zhì)4可知n=n0+n1+n2=n0+n1+n0-1=2n0+n1-1由于n為偶數(shù)，故n1=1，得n=2n0，n0=n/2=500/2=250答：葉子結點總數(shù)為250。6.4二叉樹的存儲結構和基本操作6.4.1順序存儲結構二叉樹的結構是非線性的，每一結點最多可有兩個后繼。二叉樹的存儲結構有兩種：順序存儲結構和鏈式存儲結構。

1.順序存儲順序存儲就是用一組連續(xù)的存儲單元來存儲二叉樹上的數(shù)據(jù)元素，如果用C語言來實現(xiàn)，一般情況下就是定義一個一維數(shù)組來存儲二叉樹上的數(shù)據(jù)元素，因此必須把二叉樹的所有結點結構轉(zhuǎn)換成一種線性序列結構，使得結點在線性序列中通過它們的相對位置能反映出結點之間的邏輯關系。二叉樹順序存儲結構用C語言描述如下：#defineMAXSIZE100

/*二叉樹的最大結點數(shù)或者說是數(shù)組的最大容量*/charSqBiTree[MAXSIZE+1];

/*0號單元不用*/

2.順序存儲的實現(xiàn)為了實現(xiàn)二叉樹的順序存儲，就要將二叉樹中各結點進行編號，要求該編號與等高的完全二叉樹中對應位置上的結點編號相同，并以結點編號為下標，把各結點對應地存放到一維數(shù)組中去。根據(jù)二叉樹的性質(zhì)5，可得根結點的編號為1，結點i的左孩子的編號為2i，右孩子的編號為2i?+?1。完全二叉樹的順序存儲結構如圖6.10所示。圖6.10完全二叉樹的順序存儲結構

3.順序存儲的特點二叉樹順序存儲結構有以下特點：

(1)結點之間的關系可通過數(shù)組的下標計算出來。

(2)僅適用于存儲滿二叉樹和完全二叉樹，對于一般二叉樹，特別是對于那些單分支結點較多的二叉樹來說是很不合適的，會造成存儲空間的大量浪費，如圖6.11所示。不難發(fā)現(xiàn)，采用順序存儲結構，實際上是對非線性的數(shù)據(jù)結構線性化，用線性結構來表示二叉樹結點之間的邏輯關系。圖6.11一般二叉樹的順序存儲結構6.4.2鏈式存儲結構

1.二叉鏈表設計要求不同，問題的解決方式不同，要用到的鏈式存儲結構也不同。一般情況下對二叉樹的鏈式存儲采用二叉鏈表表示。對于任意的二叉樹來說，每個結點只有兩個孩子，一個雙親結點?？梢栽O計每個結點至少包括三個域：數(shù)據(jù)域、左孩子域和右孩子域。其中，LChild域指向該結點的左孩子，data域記錄該結點的信息，RChild域指向該結點的右孩子。用C語言可以這樣聲明二叉樹的二叉鏈表結點的結構：typedefstructNode{

DataTypedata;

structNode*LChild;

structNode*RChild;}BiTNode,*BiTree;在二叉鏈表中，每個非空的指針域?qū)鏄渲械囊粋€分支。由于n個結點構成的二叉樹中只有n-1個分支，因此相對應的二叉鏈表中只有n-1個指針域被使用，而指針總數(shù)是2n個，即還有n?+?1個空指針域。從圖6.12二叉樹的二叉鏈表表示中可以看出，該二叉樹有7個結點，每一個結點中有左右兩個指針，在該樹的二叉鏈表表示中總共有14個指針，其中6個指針在使用，還有8個指針是空的。圖6.12二叉樹的二叉鏈表表示(a)二叉樹T；(b)二叉樹T的二叉鏈表

2.三叉鏈表在二叉鏈表中查找某一結點的孩子結點是很方便的，而要查找其雙親結點則十分困難。為了便于找到雙親結點，可以增加一個Parent域，Parent域指向該結點的雙親結點。結點結構如下：三叉鏈表的存儲結構用C語言描述如下：typedefstructnode{

DataTypedata;

structnode*LChild,*RChild,*Parent;}JD;用三叉鏈表來存儲的二叉樹，既容易找到結點的左右孩子結點，又容易找到其雙親結點，如圖6.13所示。圖6.13圖6.12(a)所示二叉樹的三叉鏈表表示6.4.3基本操作與前面所討論的樹的基本操作類似，二叉樹的基本操作如下：

(1)?InitBTree(bt)——將bt初始化為空二叉樹。

(2)?CreateBTree(bt)——創(chuàng)建一棵非空二叉樹bt。

(3)?DestoryBTree(bt)——銷毀二叉樹bt。

(4)?EmptyBTree(bt)——若bt為空，則返回TRUE，否則返回FALSE。

(5)?Root(bt)——求二叉樹bt的根結點。若bt為空二叉樹，則函數(shù)返回“空”。

(6)?Parent(bt，x)——求雙親函數(shù)。求二叉樹bt中結點x的雙親結點。若結點x是二叉樹的根結點或二叉樹bt中無結點x，則返回“空”。

(7)?LeftChild(bt，x)——求左孩子。若結點x為葉子結點或x不在bt中，則返回“空”。

(8)?RightChild(bt，x)——求右孩子。若結點x為葉子結點或x不在bt中，則返回“空”。

(9)?Traverse(bt)——遍歷操作。按某個次序依次訪問二叉樹中每個結點一次且僅一次。

(10)?ClearBTree(bt)——清除操作。將二叉樹bt置為空樹。6.5二叉樹的遍歷6.5.1遍歷概述二叉樹的遍歷方法主要有以下四種：先序遍歷、中序遍歷、后序遍歷和層次遍歷。根據(jù)二叉樹的遞歸定義，二叉樹由根結點、左子樹、右子樹三部分組成，因此只要依次遍歷這三部分，就遍歷了整棵二叉樹。圖6.14表示二叉樹結點的基本結構。從圖中可以看出，如果用L、D、R分別表示遍歷左子樹、訪問根結點、遍歷右子樹，那么對二叉樹的遍歷順序就可以有六種方式：

(1)訪問根，遍歷左子樹，遍歷右子樹(記做DLR)。

(2)訪問根，遍歷右子樹，遍歷左子樹(記做DRL)。

(3)遍歷左子樹，訪問根，遍歷右子樹(記做LDR)。圖6.14二叉樹結點的基本結構

(4)遍歷左子樹，遍歷右子樹，訪問根(記做LRD)。

(5)遍歷右子樹，訪問根，遍歷左子樹(記做RDL)。

(6)遍歷右子樹，遍歷左子樹，訪問根(記做RLD)。在以上六種遍歷方式中，規(guī)定按先左后右的順序，則只保留DLR、LDR、LRD三種遍歷方式。又根據(jù)對根訪問的順序的不同分別稱DLR為先序(根)遍歷，LDR為中序(根)遍歷、LRD為后序(根)遍歷。注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進行遍歷。如果從二叉樹的根結點開始，按照二叉樹層次從小到大依次遍歷二叉樹的每一層，而在遍歷每層時，按從左到右的順序依次訪問各結點，這種遍歷方式稱為層次遍歷。對于如圖6.15所示的二叉樹，其先序、中序、后序、層次遍歷的序列如下：先序遍歷：A、B、D、F、G、C、E、H。中序遍歷：B、F、D、G、A、C、E、H。后序遍歷：F、G、D、B、H、E、C、A。層次遍歷：A、B、C、D、E、F、G、H。圖6.15二叉樹可以看出，二叉樹的根結點總是在先序遍歷序列的第一位，在后序遍歷序列的最后一位，所以通過先序或后序遍歷序列可以準確判定二叉樹的根，但卻無法判定其他結點在左子樹還是右子樹上。而在中序遍歷序列中，如果知道了根的位置，則根前面的是左子樹上的結點，根后面的是右子樹上的結點，可是單獨通過中序遍歷序列是無法判定根結點的。所以，可以通過先序+中序或是后序+中序來唯一地確定一棵二叉樹。這就是所謂“先(后)序定根，中序定左右”。例6.3已知結點的先序序列和中序序列分別如下：先序序列：ABCDEFG。中序序列：CBEDAFG.。根據(jù)給定的先序序列和中序序列求出整棵二叉樹。首先由先序序列知二叉樹的根結點為A，則其左子樹的中序序列是(CBED)，右子樹的中序序列為(FG)，反過來得知其左子樹的先序序列必為(BCDE)，右子樹的先序序列為(FG)，依此類推，可由左子樹的先序序列和中序序列構造出A的左子樹，由右子樹的先序序列和中序序列構造出A的右子樹，如圖6.16所示。圖6.16先序和中序序列構造一棵二叉樹的過程6.5.2遍歷算法

1.先序遍歷先序遍歷二叉樹的基本思想：訪問根結點，先序遍歷左子樹，先序遍歷右子樹。算法描述如下：

voidPreOrder(BiTreeroot)

/*先序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結點的指針*/

{

if(root!=NULL)

{

Visit(root->data); /*訪問根結點*/PreOrder(root->LChild); /*先序遍歷左子樹*/PreOrder(root->RChild); /*先序遍歷右子樹*/}}

2.中序遍歷中序遍歷二叉樹的基本思想：中序遍歷左子樹，訪問根結點，中序遍歷右子樹。算法描述如下：voidInOrder(BiTreeroot)/*中序遍歷二叉樹,root為指向二叉樹(或某一子樹)根結點的指針*/{

if(root!=NULL){InOrder(root->LChild); /*中序遍歷左子樹*/Visit(root->data); /*訪問根結點*/InOrder(root->RChild); /*中序遍歷右子樹*/}}

2.后序遍歷后序遍歷二叉樹的基本思想：后序遍歷左子樹，后序遍歷右子樹，最后訪問根結點。算法描述如下：voidPostOrder(BiTreeroot)/*后序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結點的指針*/{if(root!=NULL){PostOrder(root->LChild); /*后序遍歷左子樹*/PostOrder(root->RChild); /*后序遍歷右子樹*

Visit(root->data); /*訪問根結點*/}}6.5.3遍歷算法的應用

1.輸出二叉樹中的結點遍歷算法將遍歷二叉樹中的每一個結點，若對輸出二叉樹中的結點并無次序要求，則可用三種遍歷中的任何一種算法完成。下面寫出用先序遍歷輸出結點的實現(xiàn)算法。voidPreOrder(BiTreeroot)/*先序遍歷輸出二叉樹結點,root為指向二叉樹根結點的指針*/{if(root!=NULL){printf(root->data); /*輸出根結點*/PreOrder(root->LChild); /*先序遍歷左子樹*/PreOrder(root->RChild); /*先序遍歷右子樹*/}}

2.輸出二叉樹中的葉子結點輸出二叉樹中的葉子結點是一個有條件的輸出問題，即在遍歷過程中走到每一個結點時需進行測試，看是否有滿足葉子結點的條件。voidPreOrder(BiTreeroot)/*先序遍歷輸出二叉樹中的葉子結點,root為指向二叉樹根結點的指針*/{

if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL) printf(root->data);

/*輸出葉子結點*/PreOrder(root->LChild);

/*先序遍歷左子樹*/PreOrder(root->RChild);

/*先序遍歷右子樹*/}}

3.統(tǒng)計葉子結點數(shù)目

1)非遞歸算法只要把上面算法中對葉子結點的輸出改為對全局變量LeafCount累加即可實現(xiàn)計數(shù)。

/*LeafCount是保存葉子結點數(shù)目的全局變量,調(diào)用之前初始化值為0*/

…

LeafCount=0; /*全局變量，在前面定義*/

voidleaf(BiTreeroot)

{if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL)LeafCount++;leaf(root->LChild);leaf(root->RChild);}}

2)遞歸算法采用遞歸算法時，如果是空樹，則返回0；如果只有一個結點，則返回1；其它情況返回左右子樹的葉子結點數(shù)之和。intleaf(BiTreeroot){intLeafCount;

/*局部變量，存放返回值*/if(root==NULL)

LeafCount=0;elseif((root->LChild==NULL)&&(root->RChild==NULL))LeafCount=1;elseLeafCount=leaf(root->LChild)+leaf(root->RChild);/*葉子數(shù)為左右子樹的葉子數(shù)目之和*/returnLeafCount;}6.6樹和森林與二叉樹之間的關系6.6.1樹轉(zhuǎn)換成二叉樹如果樹的存儲結構采用孩子兄弟表示法，即用二叉鏈表作樹的存儲結構，則樹就可以被視為轉(zhuǎn)換成了一棵二叉樹。結點的左指針指向其第一個孩子，右指針指向其下一個兄弟。將樹轉(zhuǎn)換成二叉樹的步驟為：

(1)加線就是在兄弟之間加一連線。

(2)抹線就是對樹中的每個結點，只保留其與第一個孩子結點之間的連線，抹去其與其它孩子結點之間的連線。

(3)旋轉(zhuǎn)是以樹的根結點為軸心，將整樹順時針旋轉(zhuǎn)45°。

例6.4

將圖6.17(a)所示的樹轉(zhuǎn)換為二叉樹。

解：操作過程如圖6.17(b)、(c)、(d)所示。圖6.17樹轉(zhuǎn)換成二叉樹過程(a)樹；(b)加線；(c)抹線；(d)旋轉(zhuǎn)6.6.2森林轉(zhuǎn)換成二叉樹森林是若干棵樹的集合。樹可以轉(zhuǎn)換為二叉樹，森林同樣也可以轉(zhuǎn)換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈表表示。其基本思想就是將森林中所有樹的根結點視為兄弟。所以雖然樹和森林都可以轉(zhuǎn)換為二叉樹，但二者卻有所不同：樹轉(zhuǎn)換成的二叉樹,其根結點必然無右孩子，而森林轉(zhuǎn)換后的二叉樹，其根結點可以有右孩子。森林轉(zhuǎn)換為二叉樹的方法如下：

(1)將森林中的每棵樹轉(zhuǎn)換成相應的二叉樹。

(2)第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。例6.5

將圖6.18(a)所示的樹轉(zhuǎn)換為二叉樹。圖6.18森林轉(zhuǎn)換成二叉樹(a)森林；(b)森林中每棵樹對應的二叉樹；(c)森林對應的二叉樹解：轉(zhuǎn)換成二叉樹的過程見圖6.18(b)、(c)。例6.6

如果森林共有n個結點，其中第一棵樹有n1個結點，問由該森林轉(zhuǎn)換成的二叉樹的根結點的左右子樹上各有多少個結點。

解：在森林對應的二叉樹中，第一棵樹轉(zhuǎn)換成了根和左子樹，而其它樹轉(zhuǎn)換成的二叉樹都在根結點的右子樹上。所以，左子樹上的結點數(shù)為n1-1，右子樹上的結點數(shù)為n-n1。6.6.3二叉樹還原成森林樹和森林都可以轉(zhuǎn)換為二叉樹，如果是樹轉(zhuǎn)換成的二叉樹,其根結點必然無右孩子，而如果是森林轉(zhuǎn)換成的二叉樹，其根結點有右孩子。將一棵二叉樹還原為樹或森林，具體方法如下：

(1)連線。若某結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子……都與該結點的雙親結點用線連起來。

(2)抹線。刪掉原二叉樹中所有雙親結點與右孩子結點的連線。

(3)整理。整理由(1)、(2)兩步所得到的樹或森林，使之結構層次分明。二叉樹還原成森林的過程如圖6.19所示。圖6.19二叉樹到森林的轉(zhuǎn)換示例(a)連線；(b)抹線；(c)整理6.6.4樹與森林的遍歷1.樹的遍歷樹的遍歷方法主要有以下兩種：1)先根遍歷若樹非空，則先根遍歷方法的步驟是：(1)訪問根結點。(2)從左到右，依次先根遍歷根結點的每一棵子樹。例如，圖6.17(a)中樹的先根遍歷序列為ABECFHGD。

2)后根遍歷若樹非空，則后根遍歷方法的步驟是：

(1)從左到右，依次后根遍歷根結點的每一棵子樹。

(2)訪問根結點。例如，圖6.17(a)中樹的后根遍歷序列為EBHFGCDA。可以證明，樹的先根和后根遍歷序列分別對應著由樹轉(zhuǎn)換成的二叉樹的先序和中序遍歷序列。

2.森林的遍歷森林的遍歷方法主要有以下三種：

1)先序遍歷若森林非空，則先序遍歷方法為：

(1)訪問森林中第一棵樹的根結點。

(2)先序遍歷第一棵樹的根結點的子樹森林。

(3)先序遍歷除去第一棵樹之后剩余的樹構成的森林。例如，圖6.17(a)中森林的先序遍歷序列為ABCDEFGHIJ。

2)中序遍歷若森林非空，則中序遍歷方法為：

(1)中序遍歷森林中第一棵樹的根結點的子樹森林。

(2)訪問第一棵樹的根結點。

(3)中序遍歷除去第一棵樹之后剩余的樹構成的森林。例如，圖6.17(a)中森林的中序遍歷序列為BCDAFEHJIG。

3)后序遍歷若森林非空，則后序遍歷方法為：

(1)后序遍歷森林中第一棵樹的根結點的子樹森林。

(2)后序遍歷除去第一棵樹之后剩余的樹構成的森林。

(3)訪問第一棵樹的根結點。例如，圖6.17(a)中森林的后序遍歷序列為BCDFHJIGEA。6.7哈夫曼樹及其應用6.7.1基本概念

1.路徑和路徑長度路徑：從樹中一個結點到另一個結點之間的分支序列構成這兩個結點間的路徑。路徑長度：路徑上的分支數(shù)。樹的路徑長度：從樹根到每一個結點的路徑長度之和。在結點數(shù)目相同的二叉樹中，完全二叉樹的路徑長度最短。

2.結點的權和帶權路徑長度結點的權：在一些應用中，賦予樹中結點的一個有某種意義的實數(shù)。例如用權來表示結點的重要性或使用頻率等。結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點權值的乘積。

3.樹的帶權路徑長度樹的帶權路徑長度(WeightedPathLengthofTree，WPL)：樹中所有葉子結點的帶權路徑長度之和，即其中，n為葉子結點的個數(shù)，wi為第i個葉子結點的權值，li為第i個葉子結點的路徑長度。

例6.7

有4個結點A、B、C、D，權值分別為7、5、2、4，構造出不同形態(tài)的有4個葉子結點的二叉樹(如圖6.20所示)，分別求這些二叉樹的帶權路徑長度。

解：三棵二叉樹的帶權路徑長度分別為WPL(a)=7×2+5×2+2×2+4×2=36WPL(b)=4×2+7×3+5×3+2×1=46WPL(c)=7×1+5×2+2×3+4×3=35圖6.20具有不同帶權路徑長度的二叉樹(a)帶權路徑長度為36；(b)帶權路徑長度為46；(c)帶權路徑長度為356.7.2哈夫曼樹(最優(yōu)二叉樹)從圖6.20中四個相同的葉子結點構成的三棵不同的二叉樹的帶權路徑長度可以知道，圖6.20(c)的值最小，它所對應的二叉樹具有最短帶權路徑長度，稱為最優(yōu)二叉樹，即哈夫曼樹。哈夫曼(Huffman)樹定義：設有n個權值{w1,w2,…,wn}，構造一棵有n個葉子結點的二叉樹，每個葉子的權值為wi，則WPL最小的二叉樹叫哈夫曼樹。

1.構造哈夫曼樹步驟

(1)用給定的n個權值{w1,w2,…,wn}對應的n個結點構成n棵二叉樹的森林F={T1,T2,…,Tn}，其中每一棵二叉樹Ti(1≤i≤n)都只有一個權值為wi的根結點，其左、右子樹為空。

(2)在森林F中選擇兩棵根結點權值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標記新二叉樹的根結點權值為其左右子樹的根結點權值之和。

(3)在森林F中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。

(4)重復(2)、(3)兩步，直到森林F中只含一棵樹為止，這棵樹即哈夫曼樹。

例6.8

已知A、B、C、D四個結點，它們的權值分別為3、6、8、12，求由這四個結點構造的哈夫曼樹及其WPL。

解：由這四個結點構造哈夫曼樹的過程如圖6.21所示。WPL=12×1+8×2+3×3+6×3=55在圖6.21中有四個葉子結點，構造出來的哈夫曼樹由7個結點構成，即一棵有n個葉子結點的哈夫曼樹由2n-1個結點構成。圖6.21哈夫曼樹的構造示意圖6.7.3哈夫曼編碼假設一個指令系統(tǒng)包括I1、I2、…、I7等7條指令，其對應的使用頻率如表6-1所示。如何為其構造適當?shù)木幋a系統(tǒng)呢。表6-1指令使用頻率

分析：首先考慮使用定長編碼系統(tǒng)，最短需3位編碼，如表6-2所示。表6-2定長編碼按照以上編碼方式，對于編碼序列001011010100，可準確解釋為指令序列I2I4I3I5，且不會產(chǎn)生歧義。定長編碼簡單準確，但沒有考慮指令的使用頻率，將常用指令與罕用指令的長度設計成一樣，就如同將五筆字型輸入法中的一級、二級簡碼全部改成四位編碼，使用起來顯然效率低下且極不方便。如何根據(jù)使用頻率設計變長編碼系統(tǒng)呢？不妨先嘗試設計成如表6-3所示最簡單的方式。表6-3變長編碼對于編碼序列001011010100，卻有I1I1I6I3I3I5、I1I1I3I7I3I5等多種解釋。造成歧義的原因在于某些編碼是另一些編碼的前綴，如I2是I3～I7的前綴，I4是I7的前綴。一個合格的變長編碼系統(tǒng)中，任一編碼都不能是其他編碼的前綴。符合這一條件的編碼系統(tǒng)稱為前綴編碼系統(tǒng)。哈夫曼編碼是一種很重要的數(shù)據(jù)通信二進制編碼，是一種前綴編碼系統(tǒng)?，F(xiàn)在具體來分析一下哈夫曼編碼數(shù)據(jù)通信的應用。首先要了解哈夫曼編碼思想：就是根據(jù)通信數(shù)據(jù)中字符出現(xiàn)的頻率進行編碼，使電文編碼總長最短。哈夫曼編碼先根據(jù)字符出現(xiàn)頻率來構造哈夫曼樹，然后將樹中結點左分支標為“0”，右分支標為“1”；每個字符的哈夫曼編碼即為從根到每個葉子結點經(jīng)過的路徑而得到的0、1序列。以I1～I7的頻率為權，構造的哈夫曼樹如圖6.22所示。圖6.22哈夫曼樹從圖6.22中可以看出，如果編碼A是編碼B的前綴，則A在哈夫曼樹中一定是B的祖先結點。由于哈夫曼編碼對應均為葉子結點，因此任一指令的編碼都不可能是其它編碼的前綴，即哈夫曼編碼系統(tǒng)是前綴編碼系統(tǒng)。對應的哈夫曼編碼如表6-4所示。表6-4哈夫曼編碼可以算出該哈夫曼編碼的平均碼長為：其中Pi為指令使用頻率，Ii為指令編碼長度。可見，哈夫曼編碼中雖然大部分編碼的長度大于定長編碼的長度3，卻使得程序的總位數(shù)變小了。6.7.4哈夫曼算法由于哈夫曼樹中沒有度為1的結點，因此一棵有n個葉子的哈夫曼樹共有2n-1個結點，那么，可以用一個大小為2n-1的一維數(shù)組存放哈夫曼樹的各個結點。每個結點包含權值、雙親結點的信息和孩子結點的信息，并采用順序存儲結構。二叉樹中結點類型定義如下：typedefstruct{intweight;intparent,lchild,rchild;}HTNODE,*HUFFMANTREE; /*動態(tài)分配數(shù)組存儲哈夫曼樹*/typedefchar**HUFFMANCODE;/*動態(tài)分配數(shù)組存儲哈夫曼編碼表*/例6.8中的哈夫曼樹及哈夫曼編碼如圖6.23所示。圖6.23(a)為初始狀態(tài)。森林中有4棵單結點的樹。雙親為0表示是樹的根結點。

1.構造哈夫曼樹的算法構造一棵有n個葉子的哈夫曼樹的算法如下：

(1)從已有根結點(雙親為0)中選擇權值最小和次小的結點M1、M2。

(2)在已有全部結點的最后添加新結點N，其權值為M1、M2權值之和，左右孩子分別是M1、M2，雙親為0。

(3)修改M1、M2的雙親域為N。

(4)重復(1)，共進行n-1次。圖6.23(b)為最終狀態(tài)。此時森林中只有一棵樹(1個根結點)，即為構造好的哈夫曼樹。

2.形成哈夫曼編碼的算法求某個葉子結點M對應的哈夫曼編碼，要從葉子結點到根逆向求取，結果先存放在輔助工作空間S內(nèi)，最后再復制到哈夫曼編碼表中。

(1)在S中從右向左逐位存放編碼，首先在最后一位存放編碼結束符。

(2)從葉子M開始，逆向求取編碼。設C?=?M。

(3)設P是C的雙親結點。

(4)從右向左向S中編碼：若C是P的左孩子，加入'0'，是右孩子，加入'1'。

(5)?C?=?P；

(6)重復(3)～(5)，直到P為空。所求得的哈夫曼編碼如圖6.23(c)所示。圖6.23哈夫曼編碼(a)初始狀態(tài)；(b)最終狀態(tài)；(c)哈夫曼編碼本章小結本章首先介紹了樹和二叉樹的基本概念、存儲結構及性質(zhì)。樹是一種一對多的非線性結構，可以采用雙親表示法、孩子表示法、帶雙親的孩子鏈表、孩子兄弟表示法進行存儲。二叉樹是度數(shù)不大于2且左右子樹不能互換的特殊的樹，采用順序存儲和鏈式存儲兩種存儲方式。遍歷是二叉樹最基本也最重要的操作，常用的二叉樹遍歷算法有先序、中序、后序和層次遍歷。二叉樹和樹之間可以進行轉(zhuǎn)換。哈夫曼樹是帶權路徑長度最小的樹。二叉樹的性質(zhì)及其應用、用遞歸方式構建和遍歷二叉樹的算法、哈夫曼樹的構建和應用是本章的重點。習題六

一、判斷題

1.二叉樹是樹的特殊情形。()

2.二叉樹的先序遍歷序列中，任意結點均處在其孩子結點之前。()

3.二叉鏈表是一種邏輯結構。()

4.由二叉樹的先序序列和后序序列可以唯一確定一棵二叉樹。()

5.?n個結點的完全二叉樹不唯一。()

6.樹的后序遍歷序列與其對應的二叉樹的后序遍歷序列相同。()

7.完全二叉樹的某結點若無左孩子，則它必是葉子結點。()

二、選擇題

1.將一棵樹t轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹h，則t的后序遍歷是h的()

A.先序遍歷 B.中序遍歷

C.后序遍歷 D.層次遍歷

2.對二叉樹從1開始進行連續(xù)編號，要求每個結點的編號大于其左右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用()次序的遍歷實現(xiàn)編號。

A.先序 B.中序

C.后序 D.從根開始的層次遍歷

3.已知一棵完全二叉樹中共有768個結點，則該樹中共有(

)個葉子結點。

A.?383 B.?384

C.?385 D.?386

4.先序遍歷和中序遍歷相同的二叉樹為()。

A只有根結點的二叉樹

B.根結點無左孩子的二叉樹

C一般二叉樹

D.只有根結點的二叉樹和所有結點只有右子樹的二叉樹

三、簡答題

1.一棵樹的邊集為{(a,b)，(b,e)，(a,c)，(c,g)，(a,d)，(d,i)，(c,f)，(c,h)，(d,j)，(i,k)},請畫出此棵樹的形態(tài)，并回答下列問題：

(1)樹的根是哪個結點？哪些是葉子結點？哪些是分支結點？

(2)各結點的度分別是多少？樹的度是多少？

(3)各結點的層次分別是多少？樹的深度是多少？以d為根的子樹深度是多少？

(4)結點i的雙親是哪個結點？祖先是哪個結點？孩子是哪些結點？兄弟是哪些結點？

2.樹和二叉樹有哪些區(qū)別？

3.已知二叉樹的后序和中序序列如下，構造出該二叉樹，寫出它的前序遍歷序列。后序序列：ABCDEFG中序序列：ACBGDFE

4.假設用于通信的電文由字符集{a,b,c,d,e,f,g}中的字母構成，它們在電文中出現(xiàn)的頻度分別為{0.31,0.16,0.10,0.08,0.11,0.20,0.04}

(1)為這7個字母設計哈夫曼編碼。

(2)對這7個字母進行等長編碼，至少需要幾位二進制數(shù)？哈夫曼編碼與等長編碼相比，能使電文總長壓縮多少？

四、算法題

1.設計算法求二叉樹的高度。

2.按要求寫出算法，功能為判斷一棵二叉樹(采用二叉鏈表存儲結構)是否為完全二叉樹。實訓6-1樹的存儲結構【實訓目的】

1.加深對樹的基本概念、樹的存儲結構的理解。

2.掌握樹的各種存儲結構的實現(xiàn)。【實訓內(nèi)容】如圖6.24所示的樹，分別使用雙親表示法和孩子鏈表進行存儲?！緦嵱栆蟆?/p>

1.設計一個程序?qū)崿F(xiàn)上述過程。

2.比較每種存儲結構的利弊?！舅惴ǚ治觥?/p>

1.雙親表示法采用數(shù)組進行存儲。

2.孩子鏈表采用表頭結點數(shù)組存儲結點，采用單鏈表表示結點之間的父子關系，鏈表頭指針存放在父結點中。圖6.24樹【算法分析】

1.雙親表示法采用數(shù)組進行存儲。

2.孩子鏈表采用表頭結點數(shù)組存儲結點，采用單鏈表表示結點之間的父子關系，鏈表頭指針存放在父結點中?！境绦蚯鍐巍?include<stdio.h>#defineM20typedefstruct{chardata;intparent;typedefstruct{chardata;intparent;}NODE;

/*定義雙親表示法結點結構*/NODEpt[M+1];

/*用結點數(shù)組表示樹,pt[0]單元不用*/typedefstructtnode{intchild;

/*該孩子結點在表頭數(shù)組中的下標*/structtnode*next;/*指向下一個孩子結點*/}TNODE;

/*定義孩子表示法中孩子結點結構*/typedefstructtablenode{chardata; /*數(shù)據(jù)域*/TNODE*fchild; /*指向第一個孩子結點*/}TD;

/*定義孩子表示法中表頭結點結構*/TDct[M+1];

/*用表頭結點數(shù)組表示樹，ct[0]單元不用*/voidparent_tree(chartreeData[M],intm){inti,j;charc;pt[0].data='';pt[0].parent=-1;for(i=1;i<=m;i++){pt[i].data=treeData[i];printf(“輸入%c的父結點,根的父結點請輸入空格\n",pt[i].data);

c=getchar();getchar();for(j=0;j<i;j++)if(pt[j].data==c)pt[i].parent=j;}printf("樹的雙親表示法：\n");printf("下標dataparent\n");for(i=0;i<=m;i++)printf("%d\t%c\t%d\n",i,pt[i].data,pt[i].parent);}voidchild_tree(chartreeData[M],intm){inti,j;charc;TNODE*lc,*p;intflag;ct[0].data='';ct[0].fchild=NULL;for(i=1;i<=m;i++){ /*表頭結點初始化*/ct[i].fchild=NULL;ct[i].data=treeData[i];}for(i=1;i<=m;i++){ /*建立孩子鏈表*/flag=1;while(flag){printf(“依次輸入%c的子結點,沒有子結點請輸入空格\n",ct[i].data);c=getchar();getchar();if(c!=''){lc=(TNODE*)malloc(sizeof(TNODE));

/*建立子結點*/lc->next=NULL;

for(j=1;j<=m;j++) /*查找子結點編號*/if(ct[j].data==c){lc->child=j;break;}if(ct[i].fchild==NULL)

/*子結點加入孩子鏈表*/ct[i].fchild=lc;else{

p=ct[i].fchild;while(p->next!=NULL)p=p->next;p->next=lc;}}elseflag=0;}}printf("樹的孩子表示法：\n");printf("下標datafchild\n");for(i=0;i<=m;i++){p=ct[i].fchild;printf("%d\t%c\t",i,ct[i].data);while(p!=NULL){printf("--->[%d]",p->child);p=p->next;}printf("\n");}}main(){chartreeData[M]={'','A','B','C','D','E','F','G','H','I'};intm=9;parent_tree(treeData,m);child_tree(treeData,m);}實訓6-2二叉樹的遍歷及應用【實訓目的】

1.加深對二叉樹的基本概念的理解。

2.掌握二叉樹遍歷操作及其應用。【實訓內(nèi)容】創(chuàng)建一棵二叉樹，并進行先序遍歷、中序遍歷、后序遍歷、層次遍歷，打印二叉樹的葉子結點，并統(tǒng)計葉子結點個數(shù)和總結點個數(shù)?！緦嵱栆蟆?/p>

1.設計一個程序?qū)崿F(xiàn)上述過程。

2.采用二叉鏈表存儲結構?！舅惴ǚ治觥?/p>

1.可采用輸入二叉樹的先序遍歷序列的方式來建立二叉樹。

2.采用遞歸方式進行二叉樹的遍歷。

3.判斷葉子結點的條件是其左右孩子均為空。

4.層次遍歷中，如果A在B之前被訪問，則A的孩子必在B的孩子之前被訪問。利用這一特性，借助一個先入先出的循環(huán)隊列，先將根結點入隊，只要隊伍不為空，則反復執(zhí)行如下操作：

(1)將隊首元素輸出并出隊。

(2)將出隊元素的左右孩子入隊?！境绦蚯鍐巍?include<stdlib.h>#include<stdio.h>#definequeuesize100typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}btnode; /*定義二叉鏈表結點結構*/typedefbtnode*btree; /*定義二叉鏈表指針類型*/typedefstruct{intfront,rear;btreedata[queuesize]; /*循環(huán)隊列元素類型為二叉鏈表結點指針*/intcount;}cirqueue; /*循環(huán)隊列結構定義*/createbtree(btree*t){ /*輸入二叉樹的先序遍歷序列，創(chuàng)建二叉鏈表*/charch;if((ch=getchar())=='')

/*如果讀入空格字符，則創(chuàng)建空樹*/*t=NULL;else{

*t=(btnode*)malloc(sizeof(btnode));

/*申請根結點*t空間*/(*t)->data=ch; /*將結點數(shù)據(jù)ch放入根結點的數(shù)據(jù)域*/createbtree(&(*t)->lchild);

/*建立左子樹*/createbtree(&(*t)->rchild);

/*建立右