數(shù)據(jù)結(jié)構(gòu)與算法-樹

6.1樹的有關(guān)概念6.2二叉樹6.3二叉樹的遍歷6.4遍歷的應(yīng)用6.5線索二叉樹6.6樹和森林6.7Huffman樹及其應(yīng)用第6章樹和二叉樹樹和二叉樹樹的ADT邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)樹樹的應(yīng)用Huffman樹判定過程二叉樹邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)基本性質(zhì)遍歷二叉樹線索二叉樹樹和森林【本章學(xué)習(xí)要點(diǎn)】樹的存儲(chǔ)結(jié)構(gòu)樹的遍歷6.1樹的有關(guān)概念6.2二叉樹6.3二叉樹的遍歷6.4遍歷的應(yīng)用6.5線索二叉樹6.6樹和森林6.7Huffman樹及其應(yīng)用第6章樹和二叉樹本章學(xué)習(xí)重點(diǎn)和難點(diǎn)重點(diǎn)：(1)二叉樹的定義、存儲(chǔ)結(jié)構(gòu)、遍歷及應(yīng)用；(2)線索二叉樹的定義、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的操作；(3)樹和森林與二叉樹之間的相互轉(zhuǎn)化方法；(4)哈夫曼樹的建立方法和哈夫曼編碼。難點(diǎn)：（1）二叉樹的構(gòu)造、應(yīng)用；（2）線索二叉樹的遍歷和相應(yīng)的操作。

樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。樹是n個(gè)結(jié)點(diǎn)的有限集合，在任一棵非空樹中：

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

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

6.1樹的有關(guān)概念樹的概念

6.1樹的有關(guān)概念數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；

(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關(guān)系R：ADTTree{樹的概念

6.1樹的有關(guān)概念基本操作P：ADTTree{查找類插入類刪除類}數(shù)據(jù)對(duì)象D：

數(shù)據(jù)關(guān)系R：樹的基本操作P

6.1樹的有關(guān)概念

Root(T)//求樹的根結(jié)點(diǎn)查找類：Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子

RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹是否為空樹

TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷樹的基本操作P

6.1樹的有關(guān)概念插入類：InitTree(&T)//初始化置空樹CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)

//將以c為根的樹插入為結(jié)點(diǎn)p的第i棵子樹樹的基本操作P

6.1樹的有關(guān)概念刪除類：

ClearTree(&T)//將樹清空DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)

//刪除結(jié)點(diǎn)p的第i棵子樹例如：集合T={A,B,C,D,E,F,G,H,I,J，K，L，M}A是根，其余結(jié)點(diǎn)可以劃分為3個(gè)互不相交的集合：

T1={B,E,F，K，L},T2={C,G},T3={D,H,I,J，M}這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。JIACBDHGFEKLM6.1樹的有關(guān)概念樹的概念

從邏輯結(jié)構(gòu)看：樹是一種分枝結(jié)構(gòu)，樹中只有根結(jié)點(diǎn)沒有前趨；其余結(jié)點(diǎn)有零個(gè)或多個(gè)后繼；除根外，其余結(jié)點(diǎn)都有且僅一個(gè)前趨；都存在唯一一條從根到該結(jié)點(diǎn)的路徑。JIACBDHGFEKLM6.1樹的有關(guān)概念樹的概念

6.1樹的有關(guān)概念樹的概念

***************************線性結(jié)構(gòu)非線形結(jié)構(gòu)—樹第一個(gè)數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點(diǎn)(無前驅(qū))最后一個(gè)數(shù)據(jù)元素

(無后繼)多個(gè)葉子結(jié)點(diǎn)

(無后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)單位行政機(jī)構(gòu)的組織關(guān)系1）樹可表示具有分枝結(jié)構(gòu)關(guān)系的對(duì)象

JIACBDHGFEKLM例6.1樹的有關(guān)概念樹的應(yīng)用

2）樹是常用的數(shù)據(jù)組織形式

有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。C文件夾1文件夾n文件1文件2文件夾11文件夾12文件11文件12計(jì)算機(jī)的文件系統(tǒng)

不論是DOS文件系統(tǒng)還是window文件系統(tǒng)，所有的文件是用樹的形式來組織的。例6.1樹的有關(guān)概念樹的應(yīng)用

（1）樹形表示法ABEKLFCGDHMJI（2）凹入表示法

JIACBDHGFEKLM6.1樹的有關(guān)概念樹的表示

（3）嵌套集合表示法（文氏圖）AEDHJIKLMFGCBJIACBDHGFEKLM6.1樹的有關(guān)概念樹的表示

（4）廣義表表示法(A）第一層(A(B,C,D))第二層(A(B(E,F),C(G),D(H,I,J)))第三層(A(B(E(K,L),F),C(G),D(H(M),I,J)))第四層JIACBDHGFEKLM6.1樹的有關(guān)概念樹的表示

結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1，其它依此類推；樹的深度：樹中最大的結(jié)點(diǎn)層；結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個(gè)數(shù)；樹的度：樹中最大的結(jié)點(diǎn)度；葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為0的結(jié)點(diǎn)；

樹的度為3樹的深度為4第1層第3層第2層第4層JIACBDHGFEKLM6.1樹的有關(guān)概念樹的有關(guān)術(shù)語

分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；有序樹：子樹有序的樹，如：家族樹；無序樹：不考慮子樹的順序；森林：互不相交的樹集合；6.1樹的有關(guān)概念樹的有關(guān)術(shù)語

樹和森林的關(guān)系：（1）一棵樹去掉根，其子樹構(gòu)成一個(gè)森林；（2）一個(gè)森林增加一個(gè)根結(jié)點(diǎn)成為樹。

6.1樹的有關(guān)概念6.2二叉樹6.3二叉樹的遍歷6.4遍歷的應(yīng)用6.5線索二叉樹6.6樹和森林6.7Huffman樹及其應(yīng)用第6章樹和二叉樹樹是一種分枝結(jié)構(gòu)的對(duì)象，在樹的概念中，對(duì)每一個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)沒有限制，因此樹的形態(tài)多種多樣，本節(jié)我們主要討論另一種樹型結(jié)構(gòu)——二叉樹。6.2二叉樹

A

F

G

E

D

C

B

6.2.1二叉樹的概念6.2.2二叉樹的性質(zhì)6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)6.2二叉樹6.2.1二叉樹的概念特點(diǎn)：二叉樹中每個(gè)結(jié)點(diǎn)最多有兩棵子樹；即二叉樹每個(gè)結(jié)點(diǎn)度小于等于2;左、右子樹不能顛倒——有序樹;二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念;

A

F

G

E

D

C

B概念：二叉樹或?yàn)榭諛洌蛴筛皟深w不相交的左、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。

A

F

G

E

D

C

B(a)

F

A

G

E

D

B

C(b)二叉樹是有左右之分的6.2.1二叉樹的概念二叉樹的基本形態(tài)

φ(a)空樹(b)僅有根(c)右子樹空(d)左子樹空(e)左、右子樹均在6.2.1二叉樹的概念

6.2.1二叉樹的概念6.2.2二叉樹的性質(zhì)6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)6.2二叉樹證明：最多結(jié)點(diǎn)數(shù)為各層結(jié)點(diǎn)個(gè)數(shù)相加，即

1+2+4+…+2k-1=2k-1性質(zhì)2

深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)1

在二叉樹的第i(i≥1)層上至多有2i-1個(gè)結(jié)點(diǎn)。

證明：用數(shù)學(xué)歸納法就可以證明。ABCDEFGIHJ

k層二叉樹6.2.2二叉樹的性質(zhì)兩種特殊的二叉樹

A

G

F

E

D

C

B(a)K=3的滿二叉樹滿二叉樹：如果深度為k的二叉樹，有2k-1個(gè)結(jié)點(diǎn)則稱為滿二叉樹；完全二叉樹：二叉樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。

A

E

D

C

B(b)(b)完全二叉樹

G

A

E

D

C

B(c)(c)不是完全二叉樹結(jié)論：滿二叉樹一定是完全二叉樹，反之不一定6.2.2二叉樹的性質(zhì)證明：設(shè)所求完全二叉樹的深度為k由性質(zhì)2和完全二叉樹的定義知：

2k-1-1＜n≤2k-1

性質(zhì)3

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1由此可以推出：2k-1≤n＜2k取對(duì)數(shù)得：k-1≤log2n＜k由于k為整數(shù)，故有k-1=log2n

即：k=log2n+1

性質(zhì)2:深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)

A

E

D

C

B

E

D

Dk層的最多結(jié)點(diǎn)數(shù)k-1層的最多結(jié)點(diǎn)數(shù)6.2.2二叉樹的性質(zhì)性質(zhì)4

對(duì)任意二叉樹T，如果度數(shù)為0結(jié)點(diǎn)數(shù)為n0,度數(shù)為1結(jié)點(diǎn)數(shù)為n1,度數(shù)為2結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

證明：二叉樹T的結(jié)點(diǎn)總數(shù)

n=n0+n1+n2（1）

注意：n1生成n1*1個(gè)節(jié)點(diǎn)，n2生成n2*2個(gè)節(jié)點(diǎn)，根結(jié)點(diǎn)不由任何結(jié)點(diǎn)產(chǎn)生由于分支結(jié)點(diǎn)是由度為1和度為2的結(jié)點(diǎn)生成的即分支結(jié)點(diǎn)總數(shù)b=n1+2*n2

（3）二叉樹的分支結(jié)點(diǎn)總數(shù)

b=n-1（2）

由(1)(2)(3)得求得：n0=n2+1ABCDEFGIHJ6.2.2二叉樹的性質(zhì)性質(zhì)5:若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為i的結(jié)點(diǎn):

(1)若i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親，否則，編號(hào)為

i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；(3)若2i+1>n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。(2)若2i>n，則該結(jié)點(diǎn)無左孩子，否則，編號(hào)為

2i的

結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；2i+2

i/22i+1

2i

i+1

i6.2.2二叉樹的性質(zhì)編號(hào)i=4雙親為i/2=2左子樹為2i=8右子樹為2i+1=9i=1只有根結(jié)點(diǎn)編號(hào)i=5雙親為i/2=2左子樹為2i=10右子樹為2i+1=11i=8,2i>n無左子樹1512345678910111213146.2.2二叉樹的性質(zhì)通過性質(zhì)5把非線性結(jié)構(gòu)輕易轉(zhuǎn)化成了線性結(jié)構(gòu)。

6.2.1二叉樹的概念6.2.2二叉樹的性質(zhì)6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹的順序存儲(chǔ)表示6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)

(1)完全（或滿）二叉樹ABCDEFGIHJ采用一維數(shù)組，按層序順序依次存儲(chǔ)二叉樹的每一個(gè)結(jié)點(diǎn)。如下圖所示：二叉樹的順序存儲(chǔ)表示利用性質(zhì)5實(shí)現(xiàn)線性結(jié)構(gòu)和非線性結(jié)構(gòu)的靈活轉(zhuǎn)換。2i+2

i/22i+1

2i

i+1

iABCDEFG12345678910HIJ6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)(2)一般二叉樹ABC0E0G1234567891000J通過虛設(shè)部分結(jié)點(diǎn)，使其變成相應(yīng)的完全二叉樹。ABCEGJABC0E0G00J二叉樹的順序存儲(chǔ)表示6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)(3)特殊的二叉樹說明：順序存儲(chǔ)方式對(duì)于畸形二叉樹，浪費(fèi)較大空間二叉樹的順序存儲(chǔ)表示6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)ABCJ二叉鏈表存儲(chǔ)：二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域typedefStructnode{DataTypedata;

Structnode*lch,*rch;}BinTNode;lchrchdataC語言的類型描述如下:二叉樹的鏈?zhǔn)酱鎯?chǔ)表示6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)二叉鏈表圖示∧

D

A

∧

C

∧∧

E∧∧

F

B

∧root

A

F

E

D

C

B二叉樹n個(gè)結(jié)點(diǎn)的二叉樹中，有多少個(gè)空鏈接域？二叉樹的鏈?zhǔn)酱鎯?chǔ)表示6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)性質(zhì)6：n個(gè)結(jié)點(diǎn)的二叉樹中，共有n+1

個(gè)空指針域。證：n個(gè)結(jié)點(diǎn)總的指針域數(shù)2n除了根結(jié)點(diǎn)外，其余n-1個(gè)結(jié)點(diǎn)都是由指針域指出的結(jié)點(diǎn)；所以，剩余的結(jié)點(diǎn)數(shù)即空指針域個(gè)數(shù)為：2n-（n-1）=n+1二叉鏈表的缺點(diǎn)是很難找到結(jié)點(diǎn)的雙親二叉鏈表圖示∧

D

A

∧

C

∧∧

E∧∧

F

B

∧root二叉樹的鏈?zhǔn)酱鎯?chǔ)表示6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)三叉鏈表（帶雙親指針的二叉鏈表）:三叉鏈表中每個(gè)結(jié)點(diǎn)包含四個(gè)域：數(shù)據(jù)域、左指針域、右指針域、雙親指針域typedef

Structnode{DataTypedata;

Structnode*lch,*rch,*parent;};lchdatarch

parent結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:二叉樹的鏈?zhǔn)酱鎯?chǔ)表示6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)

A

F

E

D

C

BABDFECrootlchdatarch

parent二叉樹的鏈?zhǔn)酱鎯?chǔ)表示--三叉鏈表6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)6.1樹的有關(guān)概念6.2二叉樹6.3二叉樹的遍歷6.4遍歷的應(yīng)用6.5線索二叉樹6.6樹和森林6.7Huffman樹及其應(yīng)用第6章樹和二叉樹

6.3.1二叉樹的遍歷方法6.3.2二叉樹的遍歷算法

6.3二叉樹的遍歷

遍歷：按某種搜索路徑訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次。訪問：訪問是指對(duì)結(jié)點(diǎn)進(jìn)行各種操作的簡(jiǎn)稱，包括輸出、查找、修改等等操作。遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其它的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。

6.3.1二叉樹的遍歷方法“遍歷”是任何類型均有的操作：線性結(jié)構(gòu)的遍歷：只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)；非線性結(jié)構(gòu)的遍歷：二叉樹是非線性結(jié)構(gòu)，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。

如何訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次？？6.3.1二叉樹的遍歷方法

對(duì)“二叉樹”而言，可以有三條搜索路徑：先上后下的按層次遍歷；先左（子樹）后右（子樹）的遍歷；先右（子樹）后左（子樹）的遍歷。6.3.1二叉樹的遍歷方法二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：L：遍歷左子樹

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

R：遍歷右子樹有六種遍歷方法：

T

LR，LT

R，LRT，

T

RL，RT

L，RLT約定先左后右,有三種遍歷方法：

T

LR、LT

R、LRT，分別稱為

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

A

F

G

E

D

C

B6.3.1二叉樹的遍歷方法若二叉樹非空

（1）中序遍歷左子樹

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

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

中序遍歷（LTR

）

A

F

G

E

D

C

B,F例D,G,B,A,E,C圖示6.3.1二叉樹的遍歷方法

d

e

c

b

f

a

+

*

/

-

-中序遍歷下圖所示的二叉樹

中序a,+,b,*,c,-,d,-,e,/,f練習(xí)6.3.1二叉樹的遍歷方法

若二叉樹非空

（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）先序遍歷左子樹：即按

T

LR的順序遍歷左子樹

（3）先序遍歷右子樹：即按

T

LR的順序遍歷右子樹圖示先序遍歷（TLR）例6.3.1二叉樹的遍歷方法

d

e

c

b

f

a

+

*

/

-

-先序遍歷下圖所示的二叉樹

先序-,+,a,*,b,-,c,d,/,e,f練習(xí)6.3.1二叉樹的遍歷方法若二叉樹非空

（1）后序遍歷左子樹

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

后序遍歷序列：

D,G,E,B,F,C,A后序遍歷右圖所示的二叉樹（1）后序遍歷左子樹：即按

LRT

的順序遍歷左子樹

（2）后序遍歷右子樹：即按

LRT

的順序遍歷右子樹

（3）訪問根結(jié)點(diǎn)A圖示后序遍歷（LT

R

）

A

F

G

E

D

C

B例6.3.1二叉樹的遍歷方法

d

e

c

b

f

a

+

*

/

-

-后序遍歷下圖所示的二叉樹

后序a,b,c,d,-,*,+,e,f,/,-練習(xí)6.3.1二叉樹的遍歷方法按層遍歷

A

F

G

E

D

C

B

層次遍歷序列：

A,B,C,D,E,F,G6.3.1二叉樹的遍歷方法按層遍歷按層遍歷引入了隊(duì)列作為輔助工具。算法思想為：（1）將二叉樹根入隊(duì)列；（2）將隊(duì)頭元素出隊(duì)列，并判斷此元素是否有左右孩子，若有，則將它的左右孩子入列，否則轉(zhuǎn)（3）；（3）重復(fù)步驟（2），直到隊(duì)列為空。

A

F

G

E

D

C

B課后思考：按層遍歷算法6.3.1二叉樹的遍歷方法6.3二叉樹的遍歷

6.3.1二叉樹的遍歷方法6.3.2二叉樹的遍歷算法

若二叉樹非空（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹（3）先序遍歷右子樹；上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束——基本項(xiàng)（也叫終止項(xiàng)）若二叉樹非空——遞歸項(xiàng)

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

（3）先序遍歷右子樹；6.3.2二叉樹的遍歷算法先序遍歷（T

L

R）的定義voidprev(BinTreeT){

if(T)

{visit(T->data)；prev(T->lch);

prev(T->rch);}}先序序列為+*a–bc/de稱為前綴表達(dá)式∧e∧∧

a∧

+

*

//\d/\

-T∧

b∧∧

c∧a*(b-c)+d/e先序遍歷遞歸算法6.3.2二叉樹的遍歷算法

voidMid(BinTreeT){

if(T){Mid(T->lch);visit(T->data)；

Mid(T->rch);}}中序序列為

a*b–c+d/e稱為中綴表達(dá)式a*(b-c)+d/e∧e∧∧

a∧

+

*

//\d/\

-T∧

b∧∧

c∧中序遍歷遞歸算法6.3.2二叉樹的遍歷算法

voidPost(BinTreeT){

if(T){Post(T->lch);

Post(T->rch);visti(T->data)；

}}后序序列為abc–*de/+稱為后綴表達(dá)式a*(b-c)+d/e∧e∧∧

a∧

+

*

//\d/\

-T∧

b∧∧

c∧后序遍歷遞歸算法6.3.2二叉樹的遍歷算法BiTNode*GoFarLeft(BiTreeT,Stack*S){//找到左子樹的最左下的結(jié)點(diǎn)if(!T)returnNULL;while(T->lch){

Push(S,T);T=T->lch;

}returnT;}

d

b

e

a

*

-

/

c

+中序遍歷的非遞歸算法中序序列為：a*b–c+d/e6.3.2二叉樹的遍歷算法中序遍歷的非遞歸算法voidInorder_I(BiTreeT){

Stack*S;

t=GoFarLeft(T,S);//找到最左下的結(jié)點(diǎn)

while(t){

visit(t->data);if(t->rch)t=GoFarLeft(t->rch,S);elseif(!StackEmpty(S))//棧不空時(shí)退棧

t=Pop(S);elset=NULL;//

?？毡砻鞅闅v結(jié)束

}//while}//Inorder_I6.3.2二叉樹的遍歷算法6.4遍歷的應(yīng)用遍歷是二叉樹各種操作的基礎(chǔ)，可以在遍歷過程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作：

（1）求結(jié)點(diǎn)的雙親、孩子結(jié)點(diǎn)、結(jié)點(diǎn)的層次；

（2）求孩子結(jié)點(diǎn)；（3）求結(jié)點(diǎn)的層次；（4）遍歷過程中生成結(jié)點(diǎn)，建立二叉樹；遍歷二叉樹的過程實(shí)質(zhì):是把二叉樹的結(jié)點(diǎn)進(jìn)行線性排列的過程。

6.4.1遍歷的基本應(yīng)用6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用

6.4.3二叉樹的相似與等價(jià)6.4遍歷的應(yīng)用遞歸建立二叉樹我們按先序遞歸遍歷的思想來建立二叉樹。其建立思想如下：（1）建立二叉樹的根結(jié)點(diǎn)；（2）先序建立二叉樹的左子樹；（3）先序建立二叉樹的右子樹。二叉樹的生成6.4.1遍歷的基本應(yīng)用二叉樹的生成的遞歸算法bitree*creat(){bitree*t;t=(bitree*)malloc(sizeof(bitree));t->data=x;t->lch=creat();t->rch=creat();returnt;}二叉樹的生成6.4.1遍歷的基本應(yīng)用求二叉樹的葉子數(shù)。算法思想：采用任何遍歷方法，遍歷時(shí)判斷訪問的結(jié)點(diǎn)是不是葉子，若是則葉子數(shù)加1。intcountleaf(bitreet,intnum){if(t!=NULL){if((t->lch==NULL)&&(t->rch)==NULL))num++;

num=countleaf(t->lch,num);num=countleaf(t->rch,num);}returnnum;}6.4.1遍歷的基本應(yīng)用

求二叉樹的深度算法思想：從第一層的根結(jié)點(diǎn)開始往下遞推可得到。下面給出后序遍歷求二叉樹深度的遞歸算法：Inttreedepth(bitree*t){inth,lh,rh;if(t==NULL)h=0;else{lh=treedepth(t->lch);rh=treedepth(t->rch);if(lh>=rh)h=lh+1;elseh=rh+1;

}returnh;}6.4.1遍歷的基本應(yīng)用

6.4.1遍歷的基本應(yīng)用6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用

6.4.3二叉樹的相似與等價(jià)6.4.遍歷的應(yīng)用問題：給定一個(gè)遍歷序列，能否唯一確定一棵二叉樹？例如：先序序列為ABCD,其二叉樹的結(jié)構(gòu)是什么？答案是不唯一6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用

A

C

B

D

A

D

C

B

A

C

D

B二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)之間的轉(zhuǎn)化構(gòu)造二叉樹

給定某兩種遍歷序列能否唯一確定一棵二叉樹？給定中序和后序給定中序和前序給定先序和后序不能唯一確定一棵二叉樹唯一確定一棵二叉樹唯一確定一棵二叉樹關(guān)鍵（1）確定二叉樹的根結(jié)點(diǎn)；（2）結(jié)點(diǎn)的左右次序。6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用給定二叉樹先序和中序遍歷序列，如何構(gòu)造二叉樹？先序：12463578

中序：264137581前246中264前3578中3758例左2前46中64右461前3578中3758246構(gòu)造二叉樹6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用根據(jù)給定的遍歷次序構(gòu)造二叉樹，并給出先序遍歷序列。中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-作業(yè)構(gòu)造二叉樹6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用

e

d

c

b

f

a

+

*

/

-

-先序:-,+,a,*,b,-,c,d,/,e,f答案：構(gòu)造二叉樹6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用6.4遍歷的應(yīng)用

6.4.1遍歷的基本應(yīng)用6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用6.4.3二叉樹的相似與等價(jià)二叉樹的相似與等價(jià)的含義兩株二叉樹具有相同結(jié)構(gòu)指：（1）它們都是空的；（2）它們都是非空的，且左右子樹分別具有相同結(jié)構(gòu)。定義具有相同結(jié)構(gòu)的二叉樹為相似二叉樹。相似且相應(yīng)結(jié)點(diǎn)包含相同信息的二叉樹稱為等價(jià)二叉樹?！靶螤睢毕嗤?.4.3

二叉樹的相似與等價(jià)判斷兩株二叉樹是否等價(jià)intEQUAL(t1

,t2)BTREEt1,t2;{intx;x=0;if(ISEMPTY(t1)&&ISEMPTY(t2))//二叉樹空x=1;elseif(!ISEMPTY(t1)&&!ISEMPTY(t2))//二叉樹不空if(DATA(t1)==DATA(t2))if(EQUAL(LCHILD(t1),LCHILD(t2)))x=EQUAL(RCHILD(t1),RCHILD(t2))return(x);}/*EQUAL*/6.4.3

二叉樹的相似與等價(jià)二叉樹的復(fù)制BTREECOPY(BTREEoldtree){BTREEtemp;if(oldtree!=NULL){temp=newNode;

temp->lch=COPY(oldtree->lch);temp->rch=COPY(oldtree->rch);temp->data=oldtree->data;return(temp);}return(NULL);}6.4.3

二叉樹的相似與等價(jià)結(jié)論：“遍歷”是二叉樹各種操作的基礎(chǔ)；可以在遍歷過程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作，對(duì)于一棵已知樹可求結(jié)點(diǎn)的雙親；求結(jié)點(diǎn)的孩子結(jié)點(diǎn)；判定結(jié)點(diǎn)所在層次；樹的深度；生成二叉樹……6.4.遍歷的應(yīng)用6.5線索二叉樹

6.5.1線索二叉樹的表示6.5.2二叉樹的線索化

6.5.3線索二叉樹的遍歷

6.5.1線索二叉樹的表示6.5.2二叉樹的線索化

6.5.3線索二叉樹的遍歷6.5線索二叉樹二叉鏈表是一種單向鏈接結(jié)構(gòu)，從一個(gè)結(jié)點(diǎn)出發(fā)，沿著指針走向只能到達(dá)其子孫結(jié)點(diǎn)，卻無法返回其祖先結(jié)點(diǎn)。正像線性鏈表可以從單向鏈表發(fā)展到雙向鏈表一樣，二叉鏈表也可以采用雙向鏈表。遍歷二叉樹就是按一定的規(guī)則將二叉樹中的結(jié)點(diǎn)排列成一個(gè)線性序列，即對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化的過程。有n個(gè)結(jié)點(diǎn)的二叉鏈鏈表中必定存在n+1個(gè)空鏈域。6.5線索二叉樹知識(shí)回顧如何利用二叉鏈表的空指針域？考慮利用這些空鏈域來存放遍歷后結(jié)點(diǎn)的前驅(qū)和后繼信息，這就是線索二叉樹構(gòu)成的思想。采用既可以指示其前驅(qū)又可以指示后繼的雙向鏈接結(jié)構(gòu)的二叉樹被稱為線索二叉樹。

6.5線索二叉樹線索二叉樹的概念利用空鏈域存儲(chǔ)信息鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——線索鏈表lchltagdatartagrch6.5.1線索二叉樹的表示線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)typedefstructnode{datatypedata;

structnode*lch,*rch;intltag,rtag;}threadbithptr;其中：ltag，rtag為兩個(gè)標(biāo)志域ltag=

lch域指示結(jié)點(diǎn)的左孩子

lch域指示結(jié)點(diǎn)的前驅(qū)rtag=

rch域指示結(jié)點(diǎn)的右孩子

rch域指示結(jié)點(diǎn)的后繼6.5.1線索二叉樹的表示線索二叉樹

e

d

c

b

f

a

+

*

/

-

-先序遍歷序列:-,+,a,*,b,-,c,d,/,e,f后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f遍歷二叉樹的結(jié)果是求得結(jié)點(diǎn)的一個(gè)線性序列;用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)是，只能找到結(jié)點(diǎn)的左右孩子信息，不能得到結(jié)點(diǎn)在某種遍歷次序中的前驅(qū)和后繼結(jié)點(diǎn)，這種信息只能在遍歷的過程中才能得到。

6.5線索二叉樹線索二叉樹用線索保存遍歷的信息充分利用剩余的n+1個(gè)空指針域0g00e01d10f01a11b11c16.5.2二叉樹的線索化二叉樹存儲(chǔ)結(jié)構(gòu)--線索鏈表線索鏈表中序a,e,b,f,c,t,d

b

a

e

f

d

c

gNUlNUL遍歷指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”。線索鏈表：以上述結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫線索鏈表。線索：指向前驅(qū)和后繼的指針。線索二叉樹：采用雙向鏈接結(jié)構(gòu)表示的二叉樹。線索化：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程。6.5.1線索二叉樹的表示線索二叉樹的相關(guān)概念6.5線索二叉樹

6.5.1線索二叉樹的表示6.5.2二叉樹的線索化

6.5.3線索二叉樹的遍歷關(guān)于線索二叉鏈表的頭結(jié)點(diǎn)的設(shè)定方法16.5.2二叉樹的線索化說明：由此方法設(shè)定的頭結(jié)點(diǎn)類似為二叉樹建立了一個(gè)雙向線索鏈表，既可從第一個(gè)結(jié)點(diǎn)起順后繼進(jìn)行遍歷，也可從最后一個(gè)結(jié)點(diǎn)起順前驅(qū)進(jìn)行遍歷。令二叉樹中序序列中的第一個(gè)結(jié)點(diǎn)的lchild和最后一個(gè)結(jié)點(diǎn)的rchild均指向頭結(jié)點(diǎn)。常在二叉樹線索鏈表上添加一個(gè)頭結(jié)點(diǎn)，令其lchild指向二叉樹的根結(jié)點(diǎn)，其rchild域指向中序遍歷時(shí)訪問的最后一個(gè)結(jié)點(diǎn)。010g0head0e01d10f01a11b11c16.5.2二叉樹的線索化關(guān)于線索二叉鏈表的頭結(jié)點(diǎn)的設(shè)定方法1線索鏈表head->lch指向根結(jié)點(diǎn)head->rch指向中序最后一個(gè)結(jié)點(diǎn)

b

a

e

f

d

c

g中序遍歷的第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)都指向頭結(jié)點(diǎn)中序a,e,b,f,c,t,d構(gòu)成雙向循環(huán)線索鏈表類似線性鏈表，為每個(gè)線索樹增加一個(gè)頭結(jié)點(diǎn),并設(shè):

head->lch=T(二叉樹的根);head->rch=head;head->ltag=0;head->rtag=0;當(dāng)線索樹為空時(shí)：

head->lch=head;head->rch=head;head->ltag=1;head->rtag=0;ABCDEFGIHJT(a)不帶頭結(jié)點(diǎn)的線索樹6.5.2二叉樹的線索化關(guān)于線索二叉樹的頭結(jié)點(diǎn)的設(shè)定方法2ABCDEFGIHJHEAD

(b)帶頭結(jié)點(diǎn)的線索樹在中序線索樹中查找中序后繼的方法（1）當(dāng)結(jié)點(diǎn)沒有右子樹時(shí)，即：當(dāng)p->rtag=1時(shí)，p->rch既為所求后繼結(jié)點(diǎn)（線索）。（2）當(dāng)結(jié)點(diǎn)有右子樹時(shí)，即：當(dāng)p->rtag=0時(shí)，p的后繼結(jié)點(diǎn)為p的右子樹的最左下結(jié)點(diǎn)。查找---在線索樹中找節(jié)點(diǎn)---中序后繼6.5.2二叉樹的線索化如何在中序線索樹找指定結(jié)點(diǎn)的后繼？在中序線索樹中找結(jié)點(diǎn)*p的中序后繼p的右子樹為空6.5.2二叉樹的線索化pq(a)threadbithptr*Inordernext(bithptr*p){threadbithptr*q;if(p->rtag==1)return(p->rch);else}

在中序線索樹中找結(jié)點(diǎn)*p的中序后繼

threadbithptr*Inordernext(bithptr*p){else//*p右子樹非空{(diào)q=p->rch;//從*p的右子樹開始找while(q->ltag==0)q=q->lch;

//

找右子樹的“最左下”結(jié)點(diǎn)return(q);}}qq(b)p6.5.2二叉樹的線索化p的右子樹不空在中序線索樹中找結(jié)點(diǎn)*p的中序后繼

threadbithptr*Inordernext(bithptr*p){threadbithptr*q;if(p->rtag==1)//*P的右子樹為空return(p->rch);else//*P右子樹非空{(diào)q=p->rch;while(q->ltag==0)//找右子樹的“最左下”結(jié)點(diǎn)q=q->lch;return(q);}}//查找右子樹中最左下的結(jié)點(diǎn)。

pq(a)qq(b)p6.5.2二叉樹的線索化在線索二叉樹中查找中序前驅(qū)的方法（1）當(dāng)結(jié)點(diǎn)沒有左子樹時(shí)，即：當(dāng)p->ltag=1時(shí)，p->lch既為所求前驅(qū)結(jié)點(diǎn)（線索）。（2）當(dāng)結(jié)點(diǎn)有左子樹時(shí)，即：當(dāng)p->ltag=0時(shí)，p的前驅(qū)結(jié)點(diǎn)為p的左子樹的最右下結(jié)點(diǎn)。如何在中序線索樹找指定結(jié)點(diǎn)的前趨？查找--在線索二叉樹樹中找結(jié)點(diǎn)--中序前驅(qū)6.5.2二叉樹的線索化threadbithptrINPRE(threadbithptrp)threadbithptrp;{threadbithptrq;

q=p->lch;}分析：(1)當(dāng)p->ltag=1時(shí)，p->lch既為所求（線索）。

(2)當(dāng)p->ltag=0時(shí)，q為p的左子樹的最右下結(jié)點(diǎn)。pqpq在中序線索樹中找結(jié)點(diǎn)*p的中序前趨p的左孩子為空p的左孩子不空if(p->ltag==0)while(q->rtag==0)q=q->rch;

6.5.2二叉樹的線索化6.5線索二叉樹

6.5.1線索二叉樹的表示6.5.2二叉樹的線索化6.5.3線索二叉樹的遍歷010g0thrt0e01d10f01a11b11c1線索鏈表中序遍歷的第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)都指向根結(jié)點(diǎn)

b

a

e

f

d

c

g中序a,e,b,f,c,t,d6.5.3線索二叉樹的遍歷TraverseInthread(threadbithptr*p){if(p!=Null){

while(p->ltag==0)//找中序序列的開始結(jié)點(diǎn)p=p->lch;do

{visit(p->data)

p=Inordernext(p);//找*p的中序后繼結(jié)點(diǎn)

}while(p!=Null);}}6.5.3線索二叉樹的遍歷遍歷中序線索二叉樹的遞歸算法010g0thrt0e01d10f01a11b11c1線索鏈表中序遍歷的第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)都指向根結(jié)點(diǎn)

b

a

e

f

d

c

g中序a,e,b,f,c,t,d6.5.3線索二叉樹的遍歷pTraverseInthread(biThrTreeThrt，Status(*visit)){//中序遍歷線索二叉樹T的非遞歸算法T指向線索二叉樹的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的lch指向根結(jié)點(diǎn)，中序的最后一個(gè)結(jié)點(diǎn)指向根結(jié)點(diǎn)。每次判定結(jié)點(diǎn)的ltag和rtagp=Thrt->lch;//p指向二叉樹真正的根結(jié)點(diǎn)while(p!=Thrt){

while(p->ltag==0）

p=p->lch;//找中序序列的開始結(jié)點(diǎn)if(!visit(p->data))//圖中的a被訪問

while(p->rtag==1)&&p->rch!=Thrt{

//循環(huán)結(jié)束條件，此時(shí)p指向結(jié)點(diǎn)e//p->rch!=T表明p不是是中序遍歷的最后一個(gè)結(jié)點(diǎn)p=p->rch;//p指向圖中的e結(jié)點(diǎn)

visit(p->data)}//圖中e被訪問p=p->rch;//右線索指向后繼結(jié)點(diǎn)，此時(shí)p指向圖中的f結(jié)點(diǎn)//重復(fù)以上過程，直到有線索指向根為止

}return(ok);}}6.5.3線索二叉樹的遍歷遍歷中序線索二叉樹的非遞歸算法6.5.3線索二叉樹的遍歷中序線索化二叉樹線索化的實(shí)質(zhì):是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼信息只有在遍歷時(shí)才能得到，因此線索化的過程即為在遍歷過程中修改空指針的過程。

6.5.3線索二叉樹的遍歷中序線索化二叉樹如何建立線索鏈表？圖示

在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,

pre指向剛訪問過的結(jié)點(diǎn)。P指向當(dāng)前訪問結(jié)點(diǎn)。即pre是p的前驅(qū)類似線性表的兩個(gè)相鄰的結(jié)點(diǎn)，修改相應(yīng)的pre域和next域6.5.3線索二叉樹的遍歷中序線索化二叉樹voidInThreading(BiThrTreep)

{InThreading(p->lchild);//左子樹線索化Threadp//線索化根結(jié)點(diǎn)InThreading(p->rchild);//右子樹線索化}//InThreading具體見下頁：6.5.3線索二叉樹的遍歷中序線索化二叉樹voidInThreading(BiThrTreep)

{if(p){//對(duì)以p為根的非空二叉樹進(jìn)行線索化

InThreading(p->lchild);//左子樹線索化

if(!p->lchild)//建前驅(qū)線索

{p->LTag=Thread;p->lchild=pre;}if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=p;}pre=p;//保持pre指向p的前驅(qū)

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

}//if}//InThreading6.5.3線索二叉樹的遍歷構(gòu)建中序線索化二叉樹StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//構(gòu)建中序線索鏈表

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt->LTag=0;Thrt->RTag=1;Thrt->rchild=Thrt;//添加頭結(jié)點(diǎn)，指向自身if(!T)Thrt->lchild=Thrt;//二叉樹空，指向自身6.5.3線索二叉樹的遍歷中序線索化二叉樹else{Thrt->lchild=T;pre=Thrt;//頭結(jié)點(diǎn)Thrt指向TInThreading(T);

pre->rchild=Thrt;//處理最后一個(gè)結(jié)點(diǎn)

pre->RTag=1;//pre->rch與Thrt->rch互鏈接

Thrt->rchild=pre;}

returnOK;}//InOrderThreading在二叉樹中一般不討論結(jié)點(diǎn)的插入與刪除，原因是其插入與刪除的操作與線性表相同，所不同的是需要詳細(xì)說明操作的具體要求。而在線索樹中結(jié)點(diǎn)的插入與刪除則不同，因?yàn)橐瑫r(shí)考慮修正線索的操作。6.5.3線索二叉樹的遍歷在插入和刪除時(shí)，除了修改指針外，還要相應(yīng)地修改線索。線索樹的缺點(diǎn)：6.5.3線索二叉樹的遍歷(a)插入后插入前（S的右子樹為空）SRSR將結(jié)點(diǎn)R插入作為結(jié)點(diǎn)S的右孩子結(jié)點(diǎn)：(1)若S的右子樹為空，則直接插入;如圖所示例SRW(b)SR插入前（右子樹非空）插入后6.5.3線索二叉樹的遍歷例(2)若S的右子樹非空，則R插入后原來S的右子樹作為R的右子樹。VoidRINSERT(threadbithptrS,R){if(S->rtag=1)//右子樹空{(diào)R->rtag=1;R->ltag=1;R->rch=S->rch;

//R的中序后繼是原來S的后繼

R->lch=S;

//R的中序前驅(qū)是S

S->rtag=0;//修改s的右標(biāo)識(shí)

S->rch=R;//S的右孩子是R}else//右子樹非空

{w=

Inordernext

(S);

R=w->lch

;

//R的中序后繼是w

}}6.5.3線索二叉樹的遍歷

線索二叉樹的右插入算法:將結(jié)點(diǎn)R插入作為結(jié)點(diǎn)S的右孩子例SRWSR6.5.3線索二叉樹的遍歷思考題：線索二叉樹的左插入算法:將結(jié)點(diǎn)R插入作為結(jié)點(diǎn)S的左孩子按給定先綴的表達(dá)式建立相應(yīng)的二叉樹6.5.3遍歷二叉樹和線索二叉樹應(yīng)用舉例

已知表達(dá)式的先綴表示式-×+abc/de表達(dá)式=（第一操作數(shù)）（運(yùn)算符）（第二操作數(shù)）abcde-×+/先綴表達(dá)式能否唯一確定二叉樹按給定的表達(dá)式建立相應(yīng)的二叉樹6.5.3遍歷二叉樹和線索二叉樹應(yīng)用舉例abcde-×+/對(duì)于二元運(yùn)算符：左右子樹不空；操作數(shù)為葉子結(jié)點(diǎn)；運(yùn)算符為分支結(jié)點(diǎn)；按給定后綴的表達(dá)式建立相應(yīng)的二叉樹6.5.3遍歷二叉樹和線索二叉樹應(yīng)用舉例方法：從左到右掃描后綴表達(dá)式，遇到操作符用對(duì)前面的操作數(shù)建立二叉樹，以此類推。例如：后綴表達(dá)式ab+c*de/-abcde-×+/按給定的原表達(dá)式建立相應(yīng)的二叉樹6.5.3遍歷二叉樹和線索二叉樹應(yīng)用舉例abcde-×+/原表達(dá)式（a+b)*c-(d/e)思想：結(jié)合原表達(dá)式轉(zhuǎn)化成后綴表達(dá)式（利用棧）和后綴轉(zhuǎn)化成二叉樹兩種方法實(shí)現(xiàn)。6.5.3遍歷二叉樹和線索二叉樹a+b(a+b)×c–d/ea+b×c分析表達(dá)式和二叉樹的關(guān)系:ab+abc×+abc×+(a+b)×cabcde-×+/樹的操作是可以通過對(duì)二叉樹的操作來實(shí)現(xiàn)6.6樹和森林

6.6.1樹的存儲(chǔ)結(jié)構(gòu)6.6.2樹、森林與二叉樹的轉(zhuǎn)換

6.6.3樹和森林的遍歷6.6樹和森林結(jié)點(diǎn)數(shù)6.6.1樹的存儲(chǔ)結(jié)構(gòu)采用一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn),通過保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置，表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。

9

A0B1C1D2E2F3G5H5I50123456789dataparent

ACHGDFBEI雙親表示法6.6.1樹的存儲(chǔ)結(jié)構(gòu)雙親表示類型定義

#defineMAX100TypedefstructPTnode{//結(jié)點(diǎn)結(jié)構(gòu)Elemdata;intparent;//雙親位置域}PTnode雙親表示法

dataparent樹結(jié)構(gòu):typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;

//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;6.6.1樹的存儲(chǔ)結(jié)構(gòu)雙親表示法樹結(jié)構(gòu):∧

A

B

C

D∧E

F∧

G∧

H

∧

I∧0123456789

7

9∧

8

2

6∧

45∧

3

∧樹的孩子鏈表圖示結(jié)點(diǎn)的孩子結(jié)點(diǎn)鏈表對(duì)樹的每個(gè)結(jié)點(diǎn)用線性鏈表存貯它的孩子結(jié)點(diǎn)ACHGDFBEI6.6.1樹的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法

datafirstchild

childnext

孩子鏈表表示法示意圖r=0n=96.6.1樹的存儲(chǔ)結(jié)構(gòu)對(duì)樹的每個(gè)結(jié)點(diǎn)用線性鏈表存貯它的孩子結(jié)點(diǎn)孩子鏈表表示法typedefstructCTNode{intchild;structCTNode*next;}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnext

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu):

datafirstchild

找一個(gè)結(jié)點(diǎn)的孩子十分方便，但要找一個(gè)結(jié)點(diǎn)的雙親則要遍歷整個(gè)結(jié)構(gòu)9∧

A0

B1C1D2∧E

2

F3∧

G5∧

H

5∧

I5∧0123456789帶雙親孩子鏈表示意圖結(jié)點(diǎn)的孩子結(jié)點(diǎn)鏈表結(jié)合雙親表示法和孩子表示法

7

9∧

8

2

6∧

45∧

3

∧ACHGDFBEI6.6.1樹的存儲(chǔ)結(jié)構(gòu)雙親孩子表示法dataparentlinkr=0n=96.6.1樹的存儲(chǔ)結(jié)構(gòu)樹的二叉鏈表---孩子兄弟表示法typedefstructCSNode{Elemdata;structCSNode

*firstchild,*firstbrother;}CSNode,*CSTree;結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatafirstbrother用二叉鏈表作為樹的存貯結(jié)構(gòu)。鏈表的兩個(gè)指針域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和右邊下一個(gè)兄弟結(jié)點(diǎn)。AIHGFECDB樹的孩子兄弟表示法圖示B的第一個(gè)孩子結(jié)點(diǎn)B的右兄弟結(jié)點(diǎn)∧∧∧∧∧∧∧∧∧∧ACHGDFBEI6.6.1樹的存儲(chǔ)結(jié)構(gòu)用二叉鏈表作為樹的存貯結(jié)構(gòu)。鏈表的兩個(gè)指針域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和右邊第一個(gè)兄弟結(jié)點(diǎn)。樹的二叉鏈表---孩子兄弟表示法與二叉樹的存儲(chǔ)表示一樣，但含義不同6.6.1樹的存儲(chǔ)結(jié)構(gòu)樹的二叉鏈表---孩子兄弟表示法ABCDEFG

ABCEDFGroot

ABCEDFG

二叉樹：左、右子樹樹：左是孩子，右是兄弟6.6.1樹的存儲(chǔ)結(jié)構(gòu)樹和二叉樹的存儲(chǔ)表示方式是一樣的，只是左右孩子表達(dá)的邏輯關(guān)系不同：二叉樹：左右孩子；樹的二叉鏈表：第一個(gè)孩子結(jié)點(diǎn)和右邊第一個(gè)兄弟結(jié)點(diǎn)。樹的二叉鏈表---孩子兄弟表示法把樹和二叉樹對(duì)應(yīng)起來如何把樹的轉(zhuǎn)化成二叉樹？6.6樹和森林

6.6.1樹的存儲(chǔ)結(jié)構(gòu)6.6.2樹、森林與二叉樹的轉(zhuǎn)換

6.6.3樹和森林的遍歷樹轉(zhuǎn)換為二叉樹的方法樹轉(zhuǎn)換為二叉樹的方法（1）在所有兄弟結(jié)點(diǎn)之間加一條連線；（2）對(duì)每個(gè)結(jié)點(diǎn)，除了保留與其長(zhǎng)子的連線外，去掉該結(jié)點(diǎn)與其它孩子的連線；6.6.2樹、森林與二叉樹的轉(zhuǎn)換圖示每棵樹對(duì)應(yīng)的二叉樹將樹轉(zhuǎn)換為二叉樹FHGEACBDIKJLABCDFHGEIJLK例6.6.2樹、森林與二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換為二叉樹的方法森林轉(zhuǎn)換為二叉樹的方法（1）將森林中的每一樹轉(zhuǎn)換二叉樹；（2）將各二叉樹的根結(jié)點(diǎn)視為兄弟連在一起。6.6.2樹、森林與二叉樹的轉(zhuǎn)換圖示包含3棵樹的森林每棵樹對(duì)應(yīng)的二叉樹森林對(duì)應(yīng)的二叉樹森林轉(zhuǎn)換為二叉樹FHGEACBDIKJLABCDFHGEIJLKABDFHGECIJLK例6.6.2樹、森林與二叉樹的轉(zhuǎn)換森林轉(zhuǎn)換為二叉樹的方法由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F=Φ，則B=Φ；否則，由ROOT(T1)對(duì)應(yīng)得到Node(root)；由(t11,t12,…,t1m)對(duì)應(yīng)得到LBT；由(T2,T3,…,Tn)對(duì)應(yīng)得到RBT。6.6.2樹、森林與二叉樹的轉(zhuǎn)換設(shè)森林

F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹B=(Node(root),LBT,RBT);森林和二叉樹的對(duì)應(yīng)關(guān)系由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若B=Φ，則F=Φ；否則，由Node(root)

對(duì)應(yīng)得到ROOT(T1

)；由LBT

對(duì)應(yīng)得到(t11,t12,…，t1m)；由RBT

對(duì)應(yīng)得到(T2,T3,…,Tn)。森林和二叉樹的對(duì)應(yīng)關(guān)系6.6.2樹、森林與二叉樹的轉(zhuǎn)換樹或森林與二叉樹之間有一個(gè)自然的一一對(duì)應(yīng)的關(guān)系。任何一個(gè)森林或樹可以唯一地對(duì)應(yīng)到一棵二叉樹；任何一棵二叉樹可以唯一地對(duì)應(yīng)到一個(gè)森林或一棵樹任何一棵與樹對(duì)應(yīng)的二叉樹,其右子樹必為空6.6.2樹、森林與二叉樹的轉(zhuǎn)換（1）如果結(jié)點(diǎn)X是其雙親Y的左孩子，則把x的右孩子，右孩子的右孩子，…，都與Y用連線連起來；（2）去掉所有雙親到右孩子的連線二叉樹到樹、森林的轉(zhuǎn)換6.6.2樹、森林與二叉樹的轉(zhuǎn)換圖示6.6樹和森林

6.6.1樹的存儲(chǔ)結(jié)構(gòu)6.6.2樹、森林與二叉樹的轉(zhuǎn)換6.6.3樹和森林的遍歷與二叉樹的遍歷類似，樹的遍歷也是從根結(jié)點(diǎn)出發(fā)，對(duì)樹中各個(gè)結(jié)點(diǎn)訪問一次且僅進(jìn)行一次。由于一個(gè)結(jié)點(diǎn)可以有兩棵以上的子樹，因此一般不討論中根遍歷。對(duì)樹進(jìn)行遍歷可有兩條搜索路徑：（1）從左到右（2）按層次從上到下。樹的按層次遍歷類似于二叉樹的按層次遍歷；6.6.3樹和森林的遍歷先根順序

訪問根結(jié)點(diǎn)；先根順序遍歷T1;

先根順序遍歷T2;…

先根順序遍歷Tk;T1T2TknT…先根圖示6.6.3樹和森林的遍歷樹的先根遍歷6.6.3樹和森林的遍歷樹的先根遍歷樹的先根遍歷遞歸該算法如下：voidpreordertre(CSnode*root)/*root一般樹的根結(jié)點(diǎn)*/{if(root!=NULL){visit(root->data);/*訪問根結(jié)點(diǎn)*/ preordertre(root->firstchild);preordertre(root->nextsilbing);