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

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

（1）有且僅有一個稱為根的結(jié)點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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é)點沒有前趨；其余結(jié)點有零個或多個后繼；除根外，其余結(jié)點都有且僅一個前趨；都存在唯一一條從根到該結(jié)點的路徑。JIACBDHGFEKLM6.1樹的有關(guān)概念樹的概念

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

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

(無前驅(qū))

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

(無后繼)多個葉子結(jié)點

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

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計算機的文件系統(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é)點層：根結(jié)點的層定義為1，其它依此類推；樹的深度：樹中最大的結(jié)點層；結(jié)點的度：結(jié)點子樹的個數(shù)；樹的度：樹中最大的結(jié)點度；葉子結(jié)點：也叫終端結(jié)點，是度為0的結(jié)點；

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

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

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

6.1樹的有關(guān)概念6.2二叉樹6.3二叉樹的遍歷6.4遍歷的應(yīng)用6.5線索二叉樹6.6樹和森林6.7Huffman樹及其應(yīng)用第6章樹和二叉樹樹是一種分枝結(jié)構(gòu)的對象，在樹的概念中，對每一個結(jié)點孩子的個數(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二叉樹的存儲結(jié)構(gòu)6.2二叉樹6.2.1二叉樹的概念特點：二叉樹中每個結(jié)點最多有兩棵子樹；即二叉樹每個結(jié)點度小于等于2;左、右子樹不能顛倒——有序樹;二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念;

A

F

G

E

D

C

B概念：二叉樹或為空樹，或由根及兩顆不相交的左、右子樹構(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二叉樹的存儲結(jié)構(gòu)6.2二叉樹證明：最多結(jié)點數(shù)為各層結(jié)點個數(shù)相加，即

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

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

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

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

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

A

G

F

E

D

C

B(a)K=3的滿二叉樹滿二叉樹：如果深度為k的二叉樹，有2k-1個結(jié)點則稱為滿二叉樹；完全二叉樹：二叉樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(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個結(jié)點的完全二叉樹的深度為log2n+1由此可以推出：2k-1≤n＜2k取對數(shù)得：k-1≤log2n＜k由于k為整數(shù)，故有k-1=log2n

即：k=log2n+1

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

A

E

D

C

B

E

D

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

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

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

n=n0+n1+n2（1）

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

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

b=n-1（2）

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

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

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

2i的

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

i/22i+1

2i

i+1

i6.2.2二叉樹的性質(zhì)編號i=4雙親為i/2=2左子樹為2i=8右子樹為2i+1=9i=1只有根結(jié)點編號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二叉樹的存儲結(jié)構(gòu)6.2二叉樹二叉樹的鏈式存儲表示二叉樹的順序存儲表示6.2.3二叉樹的存儲結(jié)構(gòu)

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

i/22i+1

2i

i+1

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

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

D

A

∧

C

∧∧

E∧∧

F

B

∧root

A

F

E

D

C

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

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

D

A

∧

C

∧∧

E∧∧

F

B

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

Structnode{DataTypedata;

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

parent結(jié)點結(jié)構(gòu):C語言的類型描述如下:二叉樹的鏈式存儲表示6.2.3二叉樹的存儲結(jié)構(gòu)

A

F

E

D

C

BABDFECrootlchdatarch

parent二叉樹的鏈式存儲表示--三叉鏈表6.2.3二叉樹的存儲結(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二叉樹的遍歷

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

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

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

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

T：訪問根結(jié)點

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é)點（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練習6.3.1二叉樹的遍歷方法

若二叉樹非空

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

（3）先序遍歷右子樹；

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

A

F

G

E

D

C

B先序遍歷右圖所示的二叉樹（1）訪問根結(jié)點A（2）先序遍歷左子樹：即按

T

LR的順序遍歷左子樹

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

T

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

d

e

c

b

f

a

+

*

/

-

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

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

（1）后序遍歷左子樹

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

后序遍歷序列：

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

LRT

的順序遍歷左子樹

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

LRT

的順序遍歷右子樹

（3）訪問根結(jié)點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,/,-練習6.3.1二叉樹的遍歷方法按層遍歷

A

F

G

E

D

C

B

層次遍歷序列：

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

A

F

G

E

D

C

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

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

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

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

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

L

R）的定義voidprev(BinTreeT){

if(T)

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

prev(T->rch);}}先序序列為+*a–bc/de稱為前綴表達式∧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稱為中綴表達式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/+稱為后綴表達式a*(b-c)+d/e∧e∧∧

a∧

+

*

//\d/\

-T∧

b∧∧

c∧后序遍歷遞歸算法6.3.2二叉樹的遍歷算法BiTNode*GoFarLeft(BiTreeT,Stack*S){//找到左子樹的最左下的結(jié)點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é)點

while(t){

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

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

棧空表明遍歷結(jié)束

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

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

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

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

6.4.3二叉樹的相似與等價6.4遍歷的應(yīng)用遞歸建立二叉樹我們按先序遞歸遍歷的思想來建立二叉樹。其建立思想如下：（1）建立二叉樹的根結(jié)點；（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ù)。算法思想：采用任何遍歷方法，遍歷時判斷訪問的結(jié)點是不是葉子，若是則葉子數(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é)點開始往下遞推可得到。下面給出后序遍歷求二叉樹深度的遞歸算法：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二叉樹的遍歷與存儲結(jié)構(gòu)的應(yīng)用

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

A

C

B

D

A

D

C

B

A

C

D

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

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

中序：264137581前246中264前3578中3758例左2前46中64右461前3578中3758246構(gòu)造二叉樹6.4.2二叉樹的遍歷與存儲結(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二叉樹的遍歷與存儲結(jié)構(gòu)的應(yīng)用

e

d

c

b

f

a

+

*

/

-

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

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

二叉樹的相似與等價判斷兩株二叉樹是否等價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

二叉樹的相似與等價二叉樹的復制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é)論：“遍歷”是二叉樹各種操作的基礎(chǔ)；可以在遍歷過程中對結(jié)點進行各種操作，對于一棵已知樹可求結(jié)點的雙親；求結(jié)點的孩子結(jié)點；判定結(jié)點所在層次；樹的深度；生成二叉樹……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)，從一個結(jié)點出發(fā)，沿著指針走向只能到達其子孫結(jié)點，卻無法返回其祖先結(jié)點。正像線性鏈表可以從單向鏈表發(fā)展到雙向鏈表一樣，二叉鏈表也可以采用雙向鏈表。遍歷二叉樹就是按一定的規(guī)則將二叉樹中的結(jié)點排列成一個線性序列，即對一個非線性結(jié)構(gòu)進行線性化的過程。有n個結(jié)點的二叉鏈鏈表中必定存在n+1個空鏈域。6.5線索二叉樹知識回顧如何利用二叉鏈表的空指針域？考慮利用這些空鏈域來存放遍歷后結(jié)點的前驅(qū)和后繼信息，這就是線索二叉樹構(gòu)成的思想。采用既可以指示其前驅(qū)又可以指示后繼的雙向鏈接結(jié)構(gòu)的二叉樹被稱為線索二叉樹。

6.5線索二叉樹線索二叉樹的概念利用空鏈域存儲信息鏈式存儲結(jié)構(gòu)——線索鏈表lchltagdatartagrch6.5.1線索二叉樹的表示線索鏈表的結(jié)點結(jié)構(gòu)typedefstructnode{datatypedata;

structnode*lch,*rch;intltag,rtag;}threadbithptr;其中：ltag，rtag為兩個標志域ltag=

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

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

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

rch域指示結(jié)點的后繼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é)點的一個線性序列;用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)是，只能找到結(jié)點的左右孩子信息，不能得到結(jié)點在某種遍歷次序中的前驅(qū)和后繼結(jié)點，這種信息只能在遍歷的過程中才能得到。

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

b

a

e

f

d

c

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

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

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

b

a

e

f

d

c

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

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

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

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

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

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

//

找右子樹的“最左下”結(jié)點return(q);}}qq(b)p6.5.2二叉樹的線索化p的右子樹不空在中序線索樹中找結(jié)點*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é)點q=q->lch;return(q);}}//查找右子樹中最左下的結(jié)點。

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

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

(2)當p->ltag=0時，q為p的左子樹的最右下結(jié)點。pqpq在中序線索樹中找結(jié)點*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線索鏈表中序遍歷的第一個結(jié)點和最后一個結(jié)點都指向根結(jié)點

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é)點p=p->lch;do

{visit(p->data)

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

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

b

a

e

f

d

c

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

while(p->ltag==0）

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

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

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

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

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

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

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

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

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

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

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é)點，指向自身if(!T)Thrt->lchild=Thrt;//二叉樹空，指向自身6.5.3線索二叉樹的遍歷中序線索化二叉樹else{Thrt->lchild=T;pre=Thrt;//頭結(jié)點Thrt指向TInThreading(T);

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

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

Thrt->rchild=pre;}

returnOK;}//InOrderThreading在二叉樹中一般不討論結(jié)點的插入與刪除，原因是其插入與刪除的操作與線性表相同，所不同的是需要詳細說明操作的具體要求。而在線索樹中結(jié)點的插入與刪除則不同，因為要同時考慮修正線索的操作。6.5.3線索二叉樹的遍歷在插入和刪除時，除了修改指針外，還要相應(yīng)地修改線索。線索樹的缺點：6.5.3線索二叉樹的遍歷(a)插入后插入前（S的右子樹為空）SRSR將結(jié)點R插入作為結(jié)點S的右孩子結(jié)點：(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的右標識

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

{w=

Inordernext

(S);

R=w->lch

;

//R的中序后繼是w

}}6.5.3線索二叉樹的遍歷

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

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

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

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

9

A0B1C1D2E2F3G5H5I50123456789dataparent

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

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

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

//根結(jié)點的位置和結(jié)點個數(shù)

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

A

B

C

D∧E

F∧

G∧

H

∧

I∧0123456789

7

9∧

8

2

6∧

45∧

3

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

datafirstchild

childnext

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

childnext

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

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

datafirstchild

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

A0

B1C1D2∧E

2

F3∧

G5∧

H

5∧

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

7

9∧

8

2

6∧

45∧

3

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

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

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

ABCEDFGroot

ABCEDFG

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

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

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

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

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

)；由LBT

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

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

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

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

先根順序遍歷T2;…

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