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

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

1．

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

2．

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

3．

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

4．

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

5．

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

6．

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

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

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

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

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

樹的有關(guān)概念例：下面的圖是一棵樹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}這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。

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

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

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

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

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

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

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

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

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

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

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

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

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

一些應(yīng)用問題的求解過程可用樹結(jié)構(gòu)的來描述，以幫助程序員寫出求解問題的程序或算法。

例4求集合的冪集

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

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

1）圖示表示

2）二元組表示

3）文氏圖表示

4）凹人表示法（類似書的目錄）

5）廣義表表示

6.1

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

孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(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)，依此類推；

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

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

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

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

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

森林；互不相交的樹集合；

有序樹：子樹有序的樹，如：家族樹；

無序樹：不考慮子樹的順序；6.1

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

（以DOS文元件系統(tǒng)為例解釋樹的基本操作）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二叉樹

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

A

F

G

E

D

C

B6.2二叉樹

A

F

G

E

D

C

B

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

A

G

E

D

B

C

F(b)6.2二叉樹

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

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

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

e

d

c

b

f

a

+

*

/

-

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

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

n2+1

A

F

G

E

D

C

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

A

G

F

E

D

C

B

A

C

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

A

E

D

C

B

G

A

E

D

C

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

A

G

F

E

D

C

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

A

F

E

D

C

B123456性質(zhì)5：在完全二叉樹中編號(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二叉樹三．二叉樹存貯結(jié)構(gòu)

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

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

1234567m-1

ABCDEF

A

F

E

D

C

B1234566.2二叉樹二叉樹的順序結(jié)構(gòu)假想，我們補(bǔ)齊二叉樹所缺少的那些結(jié)點(diǎn)，對(duì)二叉樹結(jié)點(diǎn)編號(hào)。用這種方式對(duì)二叉樹結(jié)點(diǎn)編號(hào)，則在二叉樹中編號(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二叉樹167245389

A

F

G

E

D

C

B123456789m-1

AB

C

DE

F

G二叉樹的順序結(jié)構(gòu)圖示將二叉樹原有的結(jié)點(diǎn)按編號(hào)存儲(chǔ)到內(nèi)存單元“相應(yīng)”的位置上6.2二叉樹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二叉樹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ù)組來實(shí)現(xiàn)，用一維數(shù)組表示的二叉鏈表或三叉鏈表，稱為靜態(tài)鏈表

A

F

E

D

C

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

0123456Lchilddatarchild第六章樹和二叉樹6.3二叉樹的遍歷一.二叉樹的遍歷方法二.遍歷的遞歸算法6.3二叉樹的遍歷遍歷：按某種搜索路徑訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎ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è)直接后繼，遍歷是很容易的事

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

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

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

R：遍歷右子樹

有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD

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

，分別稱為

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

A

F

G

E

D

C

B6.3二叉樹的遍歷先序遍歷（DLR）

若二叉樹非空

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

（3）先序遍歷右子樹；

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

A

F

G

E

D

C

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

（1）中序遍歷左子樹

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

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

A

F

G

E

D

C

B例：中序遍歷右圖所示的二叉樹

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

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

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

（1）后序遍歷左子樹

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

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

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

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

A

F

G

E

D

C

B6.3二叉樹的遍歷

e

d

c

b

f

a

+

*

/

-

-

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

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

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

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

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

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

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

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

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二叉樹的遍歷2中序遍歷遞歸算法

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

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

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

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

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

InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse

你能寫出后序遍歷遞歸算法了吧6.3二叉樹的遍歷3后序遍歷遞歸算法

void

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

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

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

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

PostOrderTraverse(T->lchild,Visit);

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

}//PostOrderTraverse

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

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

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

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

輸入：二叉樹的二叉鏈表

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

D

A

B

∧C

∧∧

E

∧∧

F

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

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

//若二叉樹不為空，在先序遍歷二叉樹的過程中，統(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)){

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

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

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

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

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

輸入：二叉樹的先序序列

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

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

D

A

B

∧C

∧∧

E

∧∧

F

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

A

F

E

D

C

B*******

A

F

E

D

C

B6.4遍歷的應(yīng)用StatusCreateBiTree(BiTree&T){//輸入（在空子樹處添加*的二叉樹的）先序序列（設(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)造左子樹鏈表，并將左子樹根結(jié)點(diǎn)指針//賦給（根）結(jié)點(diǎn)的左孩子域CreateBiTree(T->rchild);//構(gòu)造右子樹鏈表，并將右子樹根結(jié)點(diǎn)指針//賦給（根）結(jié)點(diǎn)的右孩子域}

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

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

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

遍歷是二叉樹最基本最常用的操作。

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

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

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

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

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

加上結(jié)點(diǎn)前趨后繼信息（結(jié)索）的二叉樹稱為線索二叉樹6.5線索二叉樹中序遍歷序列：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é)索）的二叉樹稱為線索二叉樹線索二叉樹孩子指針前趨指針后繼指針6.5線索二叉樹2．線索鏈表

線索二叉樹的存貯方法：

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線索二叉樹

線索鏈表的類型說明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線索二叉樹線索鏈表圖示線索二叉樹

A

G

H

E

D

C

B

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

6.5線索二叉樹為簡(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線索二叉樹如圖標(biāo)出的中序二叉樹結(jié)點(diǎn)的順序，可看出1）中序序列的第一結(jié)點(diǎn)，是二叉樹的最左下結(jié)點(diǎn)；2）若p所指結(jié)點(diǎn)的右孩子域?yàn)榫€索，則p的右孩子結(jié)點(diǎn)即為后繼結(jié)點(diǎn)；3）若p所指結(jié)點(diǎn)的右孩子域?yàn)楹⒆又羔槪瑒tp的后繼結(jié)點(diǎn)為其右子樹的最左下結(jié)點(diǎn)；F11E01G11D11A00B00H11C0001頭結(jié)點(diǎn)①②③

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

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

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

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

樹的遍歷四.森林

6.6樹和森林

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

1雙親表示法雙親表示法：通過保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置，表示樹中結(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樹和森林雙親表示類型定義

#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表示無雙親

6.6樹和森林2、孩子表示法孩子表示法：通過保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置，表示樹中結(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)樹的操作。缺點(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樹和森林方式II：孩子鏈表（可以不看）孩子鏈表：對(duì)樹的每個(gè)結(jié)點(diǎn)用線性鏈表存貯它的孩子結(jié)點(diǎn)樹的孩子鏈表類型定義typedefstructCTNode{//孩子結(jié)點(diǎn)

intchild;

str