數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言CHAP61

第六章樹(shù)和二叉樹(shù)第六章樹(shù)和二叉樹(shù)基本內(nèi)容

二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的遍歷和線索化算法；樹(shù)的定義、存儲(chǔ)結(jié)構(gòu)、樹(shù)與二叉樹(shù)的轉(zhuǎn)換、樹(shù)的遍歷；哈夫曼樹(shù)的構(gòu)造；學(xué)習(xí)要點(diǎn)

1．

掌握二叉樹(shù)的結(jié)構(gòu)特性，

2．

熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；

3．

遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。掌握各種遍歷策略的遞歸算法，能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其他操作；

4．

理解二叉樹(shù)線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，掌握二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。

5．

熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和與二叉樹(shù)的轉(zhuǎn)換方法，掌握樹(shù)的遍歷方法；

6．

了解哈夫曼樹(shù)的特性，掌握構(gòu)造哈夫曼樹(shù)和哈夫曼編碼的方法；第六章樹(shù)和二叉樹(shù)第六章樹(shù)和二叉樹(shù)6.1樹(shù)的有關(guān)概念6.2二叉樹(shù)6.3二叉樹(shù)的遍歷6.4遍歷的應(yīng)用6.5線索二叉樹(shù)6.6樹(shù)和森林6.7哈夫曼樹(shù)及應(yīng)用第六章樹(shù)和二叉樹(shù)6.1

樹(shù)的有關(guān)概念1.樹(shù)的概念2.樹(shù)的應(yīng)用3.樹(shù)的表示樹(shù)的有關(guān)術(shù)語(yǔ)5樹(shù)的基本操作6.1

樹(shù)的有關(guān)概念1．樹(shù)的概念樹(shù)結(jié)構(gòu)（除了一個(gè)稱為根的結(jié)點(diǎn)外）每個(gè)元素都有且僅有一個(gè)直接前趨，有且僅有零個(gè)或多個(gè)直接后繼。樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合，在任一棵非空樹(shù)中：

（1）有且僅有一個(gè)稱為根的結(jié)點(diǎn)。

（2）其余結(jié)點(diǎn)可分為個(gè)互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹(shù)，稱為根的子樹(shù)。樹(shù)是遞歸結(jié)構(gòu)，在樹(shù)的定義中又用到了樹(shù)的概念JIACBDHGFE6.1

樹(shù)的有關(guān)概念例：下面的圖是一棵樹(shù)T={A,B,C,D,E,F,G,H,I,J}A是根，其余結(jié)點(diǎn)可以劃分為3個(gè)互不相交的集合：

T1={B,E,F},T2={C,D},T3={D,H,I,J}這些集合中的每一集合都本身又是一棵樹(shù)，它們是A的子樹(shù)。

例如對(duì)于T11，B是根，其余結(jié)點(diǎn)可以劃分為2個(gè)互不相交的集合：T11={E}，T12={F}，T11,T12是B的子樹(shù)。JIACBDHGFE6.1

樹(shù)的有關(guān)概念從邏輯結(jié)構(gòu)看：

1）樹(shù)中只有根結(jié)點(diǎn)沒(méi)有前趨；

2）除根外，其余結(jié)點(diǎn)都有且僅一個(gè)前趨；3）樹(shù)的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后繼；

4）除根外的其他結(jié)點(diǎn)，都存在唯一條從根到該結(jié)點(diǎn)的路徑；5）樹(shù)是一種分枝結(jié)構(gòu)JIACBDHGFE6.1

樹(shù)的有關(guān)概念2．樹(shù)的應(yīng)用

1）樹(shù)可表示具有分枝結(jié)構(gòu)關(guān)系的對(duì)象

例1．家族族譜設(shè)某家庭有10個(gè)成員A、B、C、D、E、F、G、H、I、J，他們之間的關(guān)系可下圖所示的樹(shù)表示：例2．單位行政機(jī)構(gòu)的組織關(guān)系JIACBDHGFE6.1

樹(shù)的有關(guān)概念2）樹(shù)是常用的數(shù)據(jù)組織形式

有些應(yīng)用中數(shù)據(jù)元素之間并不存在間分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹(shù)的形式來(lái)組織。

例3計(jì)算機(jī)的文件系統(tǒng)

不論是DOS文件系統(tǒng)還是window文件系統(tǒng)，所有的文件是用樹(shù)的形式來(lái)組織的。文件夾1文件夾n文件1文件2文件夾11文件夾12文件11文件12C6.1

樹(shù)的有關(guān)概念3）一些應(yīng)用問(wèn)題的求解過(guò)程可用樹(shù)結(jié)構(gòu)的來(lái)描述

一些應(yīng)用問(wèn)題的求解過(guò)程可用樹(shù)結(jié)構(gòu)的來(lái)描述，以幫助程序員寫(xiě)出求解問(wèn)題的程序或算法。

例4求集合的冪集

例如求集合A={1，2，3}的冪集顯然集合A中所有即為該樹(shù)的所有葉子，求集合A所有子集即為求該樹(shù)的所有葉子。{1}{}{1,2}{1}{2}{}{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}{}集合中每個(gè)元素對(duì)于子集來(lái)說(shuō)，要么屬于該子集，要么不屬于該子集例如1不屬于{2，3}，左面的樹(shù)從空集開(kāi)始，構(gòu)造集合的子集考慮元素1考慮元素2考慮元素36.1

樹(shù)的有關(guān)概念3樹(shù)的表示

1）圖示表示

2）二元組表示

3）文氏圖表示

4）凹人表示法（類似書(shū)的目錄）

5）廣義表表示

6.1

樹(shù)的有關(guān)概念樹(shù)的基本術(shù)語(yǔ)樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹(shù)的分支；

孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子；

雙親結(jié)點(diǎn)：B結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是B結(jié)點(diǎn)的雙親；

兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)；

堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)；

結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)，依此類推；

樹(shù)的高度：樹(shù)中最大的結(jié)點(diǎn)層

結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹(shù)的個(gè)數(shù)

樹(shù)的度：樹(shù)中最大的結(jié)點(diǎn)度。

葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為0的結(jié)點(diǎn)；

分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；

森林；互不相交的樹(shù)集合；

有序樹(shù)：子樹(shù)有序的樹(shù)，如：家族樹(shù)；

無(wú)序樹(shù)：不考慮子樹(shù)的順序；6.1

樹(shù)的有關(guān)概念5樹(shù)的基本操作樹(shù)的應(yīng)用很廣，應(yīng)用不同基本操作也不同。下面列舉了樹(shù)的一些基本操作：

（以DOS文元件系統(tǒng)為例解釋樹(shù)的基本操作）1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);8）Value(T,&cur_e);9）Assign(T,cur_e,value);10）Paret(T,cur_e);11）LeftChild(T,cur_e);12）RightSibling(T,cur_e);13）InsertChild(&T,&p,i,c);14）DeleteChild(&T,&p,i);15）TraverseTree(T,Visit());6．2二叉樹(shù)

樹(shù)是一種分枝結(jié)構(gòu)的對(duì)象，在樹(shù)的概念中，對(duì)每一個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)沒(méi)有限制，因此樹(shù)的形態(tài)多種多樣，本章我們主要討論一種最簡(jiǎn)單的樹(shù)——二叉樹(shù)。第六章樹(shù)和二叉樹(shù)6.2二叉樹(shù)一二叉樹(shù)的概念二二叉樹(shù)的性質(zhì)三二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.2二叉樹(shù)一二叉樹(shù)的概念1二叉樹(shù)的定義二叉樹(shù)：或?yàn)榭諛?shù)，或由根及兩顆不相交的左子樹(shù)、右子樹(shù)構(gòu)成，并且左、右子樹(shù)本身也是二叉樹(shù)。說(shuō)明1）二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù)；二叉樹(shù)每個(gè)結(jié)點(diǎn)度小于等于2;2）左、右子樹(shù)不能顛例——有序樹(shù);3）二叉樹(shù)是遞歸結(jié)構(gòu)，在二叉樹(shù)的定義中又用到了二叉樹(shù)的概念;

A

F

G

E

D

C

B6.2二叉樹(shù)

A

F

G

E

D

C

B

(a)、(b)是不同的二叉樹(shù)，(a)的左子樹(shù)有四個(gè)結(jié)點(diǎn)，(b)的左子樹(shù)有兩個(gè)結(jié)點(diǎn)，(a)

A

G

E

D

B

C

F(b)6.2二叉樹(shù)

2．二叉樹(shù)的基本形態(tài)

φ6.2二叉樹(shù)3．應(yīng)用舉例例1可以用二叉樹(shù)表示表達(dá)式

a+b*(c-d)-e/f

e

d

c

b

f

a

+

*

/

-

-6.2二叉樹(shù)例2雙人比賽的所有可能的結(jié)局

甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙開(kāi)始開(kāi)局連贏兩局或五局三勝6.2二叉樹(shù)例3樹(shù)能用二叉樹(shù)表示6.2二叉樹(shù)二二叉樹(shù)性質(zhì)性質(zhì)1在二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)性質(zhì)2深度為k的二叉樹(shù)最多有2k-1個(gè)結(jié)點(diǎn)性質(zhì)3設(shè)二叉樹(shù)葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)n2設(shè)，則n0=

n2+1

A

F

G

E

D

C

B6.2二叉樹(shù)兩種特殊的二叉樹(shù)滿二叉樹(shù)：如果深度為k的二叉樹(shù)，有2k-1個(gè)結(jié)點(diǎn)則稱為滿二叉樹(shù)；

A

G

F

E

D

C

B

A

C

BK=3的滿二叉樹(shù)K=2的滿二叉樹(shù)6.2二叉樹(shù)完全二叉樹(shù)：如果一顆二叉樹(shù)只有最下一層結(jié)點(diǎn)數(shù)可能未達(dá)到最大，并且最下層結(jié)點(diǎn)都集中在該層的最左端，則稱為完全二叉樹(shù)；

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉樹(shù)(c)不是完全二叉樹(shù)

A

G

F

E

D

C

B6.2二叉樹(shù)下面是兩個(gè)關(guān)于完全二叉樹(shù)的性質(zhì)性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為：log2n+1對(duì)完全二叉樹(shù)的結(jié)點(diǎn)編號(hào)：從上到下，每一層從左到右

A

F

E

D

C

B123456性質(zhì)5：在完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)，1）若有左孩子，則左孩編號(hào)為2i；2）若有右孩子，則有孩子結(jié)點(diǎn)編號(hào)為2i+1；3）若有雙親，則雙親結(jié)點(diǎn)編號(hào)為i/2；6.2二叉樹(shù)三．二叉樹(shù)存貯結(jié)構(gòu)

1二叉樹(shù)的順序結(jié)構(gòu)完全二叉樹(shù)的順序結(jié)構(gòu)用一組連續(xù)的內(nèi)存單元，按編號(hào)順序依次存儲(chǔ)完全二叉樹(shù)的元素

順序結(jié)構(gòu)圖示

1234567m-1

ABCDEF

A

F

E

D

C

B1234566.2二叉樹(shù)二叉樹(shù)的順序結(jié)構(gòu)假想，我們補(bǔ)齊二叉樹(shù)所缺少的那些結(jié)點(diǎn)，對(duì)二叉樹(shù)結(jié)點(diǎn)編號(hào)。用這種方式對(duì)二叉樹(shù)結(jié)點(diǎn)編號(hào)，則在二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)，1）若有左孩子，則左孩編號(hào)為2i；2）若有右孩子，則有孩子結(jié)點(diǎn)編號(hào)為2i+1；3）若有雙親，則雙親結(jié)點(diǎn)編號(hào)為i/2；

A

F

G

E

D

C

B167245389

A

F

G

E

D

C

B6.2二叉樹(shù)167245389

A

F

G

E

D

C

B123456789m-1

AB

C

DE

F

G二叉樹(shù)的順序結(jié)構(gòu)圖示將二叉樹(shù)原有的結(jié)點(diǎn)按編號(hào)存儲(chǔ)到內(nèi)存單元“相應(yīng)”的位置上6.2二叉樹(shù)2二叉鏈表二叉鏈表中每個(gè)結(jié)點(diǎn)至少包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域∧

D

A

B

∧C

∧∧

E

∧∧

F

∧

A

F

E

D

C

B3三叉鏈表三叉鏈表中每個(gè)結(jié)點(diǎn)至少包含四個(gè)域：數(shù)據(jù)域、雙親指針域、左指針域、右指針域二叉鏈表圖示6.2二叉樹(shù)4

靜態(tài)鏈表上面?zhèn)兌骀湵砘蛉骀湵硎怯弥羔槍?shí)現(xiàn)，是一種動(dòng)態(tài)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也可用一維數(shù)組來(lái)實(shí)現(xiàn)，用一維數(shù)組表示的二叉鏈表或三叉鏈表，稱為靜態(tài)鏈表

A

F

E

D

C

B孩子結(jié)點(diǎn)在數(shù)組中的位置0表示無(wú)左或右孩子靜態(tài)二叉鏈表A13C05B00E00F00D4

0123456Lchilddatarchild第六章樹(shù)和二叉樹(shù)6.3二叉樹(shù)的遍歷一.二叉樹(shù)的遍歷方法二.遍歷的遞歸算法6.3二叉樹(shù)的遍歷遍歷：按某種搜索路徑訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。訪問(wèn)：含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。

對(duì)于線性結(jié)構(gòu)由于每個(gè)結(jié)點(diǎn)只有一個(gè)直接后繼，遍歷是很容易的事

二叉樹(shù)是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可能有兩個(gè)后繼，如何訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次？

6.3二叉樹(shù)的遍歷二叉樹(shù)的遍歷方法二叉樹(shù)由根、左子樹(shù)、右子樹(shù)三部分組成二叉樹(shù)的遍歷可以分解為：訪問(wèn)根，遍歷左子樹(shù)和遍歷右子樹(shù)令：L：遍歷左子樹(shù)

D：訪問(wèn)根結(jié)點(diǎn)

R：遍歷右子樹(shù)

有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD

約定先左后右,有三種遍歷方法：DLR、LDR、LRD

，分別稱為

先序遍歷、中序遍歷、后序遍歷

A

F

G

E

D

C

B6.3二叉樹(shù)的遍歷先序遍歷（DLR）

若二叉樹(shù)非空

（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；

（3）先序遍歷右子樹(shù)；

先序遍歷序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B例：先序遍歷右圖所示的二叉樹(shù)（1）訪問(wèn)根結(jié)點(diǎn)A（2）先序遍歷左子樹(shù)：即按DLR的順序遍歷左子樹(shù)（3）先序遍歷右子樹(shù)：即按DLR的順序遍歷右子樹(shù)6.3二叉樹(shù)的遍歷中序遍歷（LDR）若二叉樹(shù)非空

（1）中序遍歷左子樹(shù)

（2）訪問(wèn)根結(jié)點(diǎn)（3）中序遍歷右子樹(shù)

中序遍歷序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍歷右圖所示的二叉樹(shù)

（1）中序遍歷左子樹(shù)：即按LDR的順序遍歷左子樹(shù)

（2）訪問(wèn)根結(jié)點(diǎn)A

（3）中序遍歷右子樹(shù)：即按LDR的順序遍歷右子樹(shù)6.3二叉樹(shù)的遍歷后序遍歷（LRD）若二叉樹(shù)非空

（1）后序遍歷左子樹(shù)

（2）后序遍歷右子樹(shù)（3）訪問(wèn)根結(jié)點(diǎn)

后序遍歷序列：D,G,E,B,F,C,A例：后序遍歷右圖所示的二叉樹(shù)

（1）后序遍歷左子樹(shù)：即按LRD的順序遍歷左子樹(shù)

（2）后序遍歷右子樹(shù)：即按LRD的順序遍歷右子樹(shù)（3）訪問(wèn)根結(jié)點(diǎn)A

A

F

G

E

D

C

B6.3二叉樹(shù)的遍歷

e

d

c

b

f

a

+

*

/

-

-

后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-

中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f

先序遍歷序列：-,+,a,*,b,-,c,d,/,e,f例：先中序遍歷序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹(shù)6.3二叉樹(shù)的遍歷這實(shí)際上是先序遍歷的遞歸定義，我們知道遞歸定義包括兩個(gè)部分：1）基本項(xiàng)（也叫終止項(xiàng)）；2）遞歸項(xiàng)若二叉樹(shù)非空（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)（3）先序遍歷右子樹(shù)；先序遍歷遞歸定義遞歸項(xiàng)二.遍歷的遞歸算法

上面介紹了三種遍歷方法，顯然是用遞歸的方式給出的三種遍歷方法，以先序?yàn)槔合刃虮闅v（DLR）的定義：該定義隱含著若二叉樹(shù)為空，結(jié)束6.3二叉樹(shù)的遍歷上面先序遍歷的定義等價(jià)于：若二叉樹(shù)為空，結(jié)束——基本項(xiàng)（也叫終止項(xiàng)）若二叉樹(shù)非空——遞歸項(xiàng)（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)（3）先序遍歷右子樹(shù)；下面給出先序、中序、后序遍歷遞歸算法，為了增加算法的可讀性，這里對(duì)書(shū)上算法作了簡(jiǎn)化，沒(méi)有考慮訪問(wèn)結(jié)點(diǎn)出錯(cuò)的情況（即我們假設(shè)調(diào)用函數(shù)visit()訪問(wèn)結(jié)點(diǎn)總是成功的。6.3二叉樹(shù)的遍歷先序遍歷遞歸算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹(shù)，visit()是訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法先序//遍歷以為根結(jié)點(diǎn)指針的二叉樹(shù)，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit()

if(T){//若二叉樹(shù)為空，結(jié)束返回

//若二叉樹(shù)不為空，訪問(wèn)根結(jié)點(diǎn)；遍歷左子樹(shù)，遍歷右子樹(shù)

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse最簡(jiǎn)單的Visit函數(shù)是：

StatusPrintElement(TElemTypee){//輸出元素e的值

printf(e);

returnOK;}

∧

D

A

B

∧C

∧∧

E

∧∧

F

∧T6.3二叉樹(shù)的遍歷2中序遍歷遞歸算法

voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹(shù)，visit()是訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法中序//遍歷以為根結(jié)點(diǎn)指針的二叉樹(shù)，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit()

if(T){//若二叉樹(shù)為空，結(jié)束返回

//若二叉樹(shù)不為空，遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)

InOrderTraverse(T->lchild,Visit);Visit(T->data)；

InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse

你能寫(xiě)出后序遍歷遞歸算法了吧6.3二叉樹(shù)的遍歷3后序遍歷遞歸算法

void

PostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹(shù)，visit()是訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法中序//遍歷以為根結(jié)點(diǎn)指針的二叉樹(shù)，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit()

if(T){//若二叉樹(shù)為空，結(jié)束返回

//若二叉樹(shù)不為空，遍歷左子樹(shù)，遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)

PostOrderTraverse(T->lchild,Visit);

PostOrderTraverse(T->rchild,Visit);Visit(T->data)；

}//PostOrderTraverse

第六章樹(shù)和二叉樹(shù)6.4遍歷的應(yīng)用

1.求二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)2.建立二叉鏈表

6.4遍歷的應(yīng)用遍歷是二叉樹(shù)的基本操作：二叉樹(shù)許多操作可在遍歷過(guò)程中完成，如二叉樹(shù)線索化，就是在對(duì)二叉樹(shù)進(jìn)行中序遍歷時(shí)加上線索的。本節(jié)再例子舉幾個(gè)二叉樹(shù)遍歷應(yīng)用實(shí)例。6.4遍歷的應(yīng)用例1編寫(xiě)

求二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)的算法

輸入：二叉樹(shù)的二叉鏈表

結(jié)果：二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)基本思想：遍歷操作訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。所以可在二叉樹(shù)遍歷的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)?！?/p>

D

A

B

∧C

∧∧

E

∧∧

F

∧Tvoidleaf(BiTreeT){//采用二叉鏈表存貯二叉樹(shù)，n為全局變量，用于累加二叉樹(shù)的葉子結(jié)點(diǎn)//的個(gè)數(shù)。本算法在先序遍歷二叉樹(shù)的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)//第一次被調(diào)用時(shí)，n=0if(T){//若二叉樹(shù)為空，結(jié)束返回

//若二叉樹(shù)不為空，在先序遍歷二叉樹(shù)的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)if(T->lchild==null&&T->rchild==null)n=n+1;leaf(T->lchild);leaf(T->rchild);}//if}//leafvoidleaf(BiTreeT){//采用二叉鏈表存貯二叉樹(shù)，n為全局變量，用于累加二叉樹(shù)的葉子結(jié)點(diǎn),的個(gè)數(shù)。//本算法在先序遍歷二叉樹(shù)的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)第一次被調(diào)用時(shí)，n=0if(T){//若二叉樹(shù)為空，結(jié)束返回

//若二叉樹(shù)不為空，在先序遍歷二叉樹(shù)的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)if(T->lchild==null&&T->rchild==null)n=n+1;leaf(T->lchild);leaf(T->rchild);}//if}//leaf6.4遍歷的應(yīng)用

viodPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹(shù)，visit()是訪問(wèn)結(jié)點(diǎn)的函數(shù)。本算法先序//遍歷以為根結(jié)點(diǎn)指針的二叉樹(shù)，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit()

if(T){//若二叉樹(shù)為空，返回

//若二叉樹(shù)不為空，訪問(wèn)根結(jié)點(diǎn)；遍歷左子樹(shù)，遍歷右子樹(shù)

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse比較先序遍歷算法和計(jì)算葉子結(jié)點(diǎn)算法，有什么相同和不同？結(jié)構(gòu)類似函數(shù)名不同訪問(wèn)結(jié)點(diǎn)時(shí)調(diào)用visit()訪問(wèn)結(jié)點(diǎn)時(shí)統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)6.4遍歷的應(yīng)用例2為二叉樹(shù)建立二叉鏈表

輸入：二叉樹(shù)的先序序列

結(jié)果：二叉樹(shù)的二叉鏈表

遍歷操作訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。是否可在利用遍歷，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接？基本思想：輸入（在空子樹(shù)處添加*的二叉樹(shù)的）先序序列（設(shè)每個(gè)元素是一個(gè)字符//）按先序編歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接6.4遍歷的應(yīng)用∧

D

A

B

∧C

∧∧

E

∧∧

F

∧T先序序列：ABDFCE（在空子樹(shù)處添加*的二叉樹(shù)的）先序序列：ABD*F**CE***

A

F

E

D

C

B*******

A

F

E

D

C

B6.4遍歷的應(yīng)用StatusCreateBiTree(BiTree&T){//輸入（在空子樹(shù)處添加*的二叉樹(shù)的）先序序列（設(shè)每個(gè)元素是一個(gè)字//符）按先序編歷的順序，建立二叉鏈表，并將該二叉鏈表根結(jié)點(diǎn)指針//賦給T

scanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’則T=NULL返回else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;//建立（根）結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹(shù)鏈表，并將左子樹(shù)根結(jié)點(diǎn)指針//賦給（根）結(jié)點(diǎn)的左孩子域CreateBiTree(T->rchild);//構(gòu)造右子樹(shù)鏈表，并將右子樹(shù)根結(jié)點(diǎn)指針//賦給（根）結(jié)點(diǎn)的右孩子域}

returnOK;}//CreateBiTree小結(jié)

小結(jié)1二叉樹(shù)：或?yàn)榭諛?shù)，或由根及兩顆不相交的左子樹(shù)、右子樹(shù)構(gòu)成，并且左、右子樹(shù)本身也是二叉樹(shù)；2二叉樹(shù)即可以用順序結(jié)構(gòu)存儲(chǔ)，也可用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)；3遍歷：按某種搜索路徑訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。二叉樹(shù)的遍歷可以分解為：訪問(wèn)根，遍歷左子樹(shù)和遍歷右子樹(shù)，本課程介紹了三種遍歷算法：先序遍歷、中序遍歷、后序遍歷；習(xí)題十1P386.12對(duì)P396.15給出的二叉樹(shù)求出以下的遍歷序列：（1）先序序列（2）中序序列（3）后序序列3編寫(xiě)

求二叉樹(shù)的分枝結(jié)點(diǎn)個(gè)數(shù)的算法（用二叉鏈表存貯二叉樹(shù)習(xí)題取自數(shù)據(jù)結(jié)構(gòu)題集C語(yǔ)言版嚴(yán)尉敏等編清華大學(xué)出版社第六章習(xí)題第六章樹(shù)和二叉樹(shù)6.4線索二叉樹(shù)1.線索二叉樹(shù)的概念2線索鏈表3.線索二叉樹(shù)的遍歷6.5線索二叉樹(shù)1線索二叉樹(shù)

遍歷是二叉樹(shù)最基本最常用的操作。

1）對(duì)二叉樹(shù)所有結(jié)點(diǎn)做某種處理可在遍歷過(guò)程中實(shí)現(xiàn)；

2）檢索（查找）二叉樹(shù)某個(gè)結(jié)點(diǎn)，可通過(guò)遍歷實(shí)現(xiàn)；

與線性表相比，對(duì)二叉樹(shù)的遍歷存在如下問(wèn)題：1）遍歷算法要復(fù)雜的多，費(fèi)時(shí)的多；2）為檢索或查找二叉樹(shù)中某結(jié)點(diǎn)在某種遍歷下的后繼，必須從根開(kāi)始遍歷，直到找到該結(jié)點(diǎn)及后繼；

如果能將二叉樹(shù)線性化，就可以減化遍歷算法，提高遍歷速度。如何將二叉樹(shù)線性化？

以中序遍歷為例，我們看到通過(guò)遍歷可以得到二叉樹(shù)結(jié)點(diǎn)的中序序列。若能將中序序列中每個(gè)結(jié)點(diǎn)前趨、后繼信息保存起來(lái)，以后再遍歷二叉樹(shù)時(shí)就可以根據(jù)所保存的結(jié)點(diǎn)前趨、后繼信息對(duì)二叉樹(shù)進(jìn)行遍歷。

加上結(jié)點(diǎn)前趨后繼信息（結(jié)索）的二叉樹(shù)稱為線索二叉樹(shù)6.5線索二叉樹(shù)中序遍歷序列：D,B,H,E,A,F,C,G在中序序列中，D的后繼是B，H的前趨是B，后繼是E…

A

G

H

E

D

C

B

F加上結(jié)點(diǎn)前趨后繼信息（結(jié)索）的二叉樹(shù)稱為線索二叉樹(shù)線索二叉樹(shù)孩子指針前趨指針后繼指針6.5線索二叉樹(shù)2．線索鏈表

線索二叉樹(shù)的存貯方法：

1）

為每個(gè)結(jié)點(diǎn)增加二個(gè)指針域。

缺點(diǎn)：要點(diǎn)用較多的內(nèi)存空間。每個(gè)n個(gè)結(jié)點(diǎn)的二叉鏈表，有n+1個(gè)空指針域，故可利用這些的空指針域存放結(jié)點(diǎn)的前趨和后繼指針，以這種結(jié)點(diǎn)的構(gòu)成二叉鏈表稱為線索鏈表T∧

D

A

B

C

∧

F

∧∧

H∧

E

∧∧

G

∧6.5線索二叉樹(shù)

線索鏈表的類型說(shuō)明typedefenum{link,thread}PointerTag;//link=0,thread=1typedefstructBiThrNode{

TElemTypedata;

StructBiThrNode*lchild,*rchild;//左右指針域

PointerTagLtag,Rtag;//左右標(biāo)志域，標(biāo)志域?yàn)?時(shí)，表示左右指針//域存儲(chǔ)的是左右孩子的指針，標(biāo)志域?yàn)?時(shí)，表示左右指針域存儲(chǔ)的是//前趨后繼結(jié)點(diǎn)的指針}BiThrNode，*BiThrTreeLchildlTagdataRTagrchildF11E01G10D01A00B00H11C006.5線索二叉樹(shù)線索鏈表圖示線索二叉樹(shù)

A

G

H

E

D

C

B

F孩子指針前趨指針后繼指針

6.5線索二叉樹(shù)為簡(jiǎn)化線索鏈表的遍歷算法，仿照線性鏈表，為線索鏈表加上一頭結(jié)點(diǎn)

約定：

頭結(jié)點(diǎn)的lchild域：存放線索鏈表的根結(jié)點(diǎn)指針；

頭結(jié)點(diǎn)的rchild域:中序序列最后一個(gè)結(jié)點(diǎn)的指針；

中序序列第一結(jié)點(diǎn)lchild域指向頭結(jié)點(diǎn);

中序序列最后一個(gè)結(jié)點(diǎn)的rchild域指向頭結(jié)點(diǎn);F11E01G11D11A00B00H11C0001頭結(jié)點(diǎn)6.5線索二叉樹(shù)如圖標(biāo)出的中序二叉樹(shù)結(jié)點(diǎn)的順序，可看出1）中序序列的第一結(jié)點(diǎn)，是二叉樹(shù)的最左下結(jié)點(diǎn)；2）若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索，則p的右孩子結(jié)點(diǎn)即為后繼結(jié)點(diǎn)；3）若p所指結(jié)點(diǎn)的右孩子域?yàn)楹⒆又羔?，則p的后繼結(jié)點(diǎn)為其右子樹(shù)的最左下結(jié)點(diǎn)；F11E01G11D11A00B00H11C0001頭結(jié)點(diǎn)①②③

中序遍歷序列：D,B,H,E,A,F,C,G6.5線索二叉樹(shù)3．線索二叉樹(shù)的遍歷

在二叉樹(shù)上加上結(jié)點(diǎn)前趨、后繼線索后，可利用線索對(duì)二叉樹(shù)進(jìn)行遍歷。

下面是線索鏈表的遍歷算法。

基本步驟：1）p=T->lchild;p指向線索鏈表的根結(jié)點(diǎn)；2）若線索鏈表非空，循環(huán)：（a）循環(huán)，順著p左孩子指針找到最左下結(jié)點(diǎn)；訪問(wèn)之；（b）若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索，p的右孩子結(jié)點(diǎn)即為后繼結(jié)點(diǎn)循環(huán)：p=p->rchild；并訪問(wèn)p所指結(jié)點(diǎn)；（在此循環(huán)中，順著后繼線索訪問(wèn)二叉樹(shù)中的結(jié)點(diǎn)）（c）一旦線索“中斷”，p所指結(jié)點(diǎn)的右孩子域?yàn)橛液⒆又羔?，p=p->rchild，使p指向右孩子結(jié)點(diǎn)；3）返回OK；結(jié)束6.5線索二叉樹(shù)線索鏈表的遍歷算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)){//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，//中序遍歷二叉線索樹(shù)T算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。P=T->lchild;//p指向根結(jié)點(diǎn)While(p!=T){//空樹(shù)或遍歷結(jié)束時(shí)，p==TWhile(p->Ltag==Link)p=p->lchild;//找到最左下結(jié)點(diǎn)；訪問(wèn)之Visit(p->data))while(p->Rtag==Thread&&p->rchild!=T){//若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索//且不是最后一個(gè)結(jié)點(diǎn)p=p->rchild;Visit(p->data);//訪問(wèn)后繼結(jié)點(diǎn)}p=p->rchild;}returnOK;}//InOrderTraverse_Thr為了增加算法的可讀性，這里對(duì)書(shū)上算法作了簡(jiǎn)化，沒(méi)有考慮訪問(wèn)結(jié)點(diǎn)出錯(cuò)的情況（即我們假設(shè)調(diào)用函數(shù)visit()訪問(wèn)結(jié)點(diǎn)總是成功的。第六章樹(shù)和二叉樹(shù)6.6樹(shù)和森林一.樹(shù)的存儲(chǔ)結(jié)構(gòu)二.樹(shù)和二叉樹(shù)的轉(zhuǎn)換三.

樹(shù)的遍歷四.森林

6.6樹(shù)和森林

一．樹(shù)的存貯結(jié)構(gòu)在樹(shù)中，每個(gè)結(jié)點(diǎn)即可能有孩子也可能有雙親，所以既可以通過(guò)保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)位置來(lái)表示結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系，也雙親表示法通過(guò)通過(guò)保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置來(lái)表示結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。

1雙親表示法雙親表示法：通過(guò)保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置，表示樹(shù)中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。用一組連續(xù)的內(nèi)存單元存儲(chǔ)數(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包含兩個(gè)域：一個(gè)數(shù)據(jù)域，一個(gè)“指針域”，用于指示其雙親結(jié)點(diǎn)在數(shù)組中的位置6.6樹(shù)和森林雙親表示類型定義

#defineMAX_TREEE_SIZE100typedefstructPTNode{

TelemTypedata;

intparent;//雙親位置域}PTNode;typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

Intn;//結(jié)點(diǎn)數(shù)}Ptree;IACBDHGFE雙親表示圖示A-1B0C0D0E1F1G2H3I3012345678.dataparent9T.nodesT.n結(jié)點(diǎn)數(shù)雙親結(jié)點(diǎn)在數(shù)組中的位置-1表示無(wú)雙親

6.6樹(shù)和森林2、孩子表示法孩子表示法：通過(guò)保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置，表示樹(shù)中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。

與雙親表示法相反，孩子表示法適合實(shí)現(xiàn)涉及孩子的操作。還可以將雙親表示與孩子表示法結(jié)合：帶雙親的孩子鏈表。

方法1：多重鏈表（類似二叉鏈表）

兩種方式：定長(zhǎng)結(jié)點(diǎn)不定長(zhǎng)結(jié)點(diǎn)定長(zhǎng)結(jié)點(diǎn)

優(yōu)點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)一致，便于實(shí)現(xiàn)樹(shù)的操作。缺點(diǎn)是浪費(fèi)一些內(nèi)存。

不定長(zhǎng)結(jié)點(diǎn)

優(yōu)點(diǎn)：節(jié)省內(nèi)存

缺點(diǎn)：不定長(zhǎng)會(huì)使一些操作實(shí)現(xiàn)復(fù)雜一些6.6樹(shù)和森林方式II：孩子鏈表（可以不看）孩子鏈表：對(duì)樹(shù)的每個(gè)結(jié)點(diǎn)用線性鏈表存貯它的孩子結(jié)點(diǎn)樹(shù)的孩子鏈表類型定義typedefstructCTNode{//孩子結(jié)點(diǎn)

intchild;

str