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

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

（1）有且僅有一個稱為根的結點。

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

6.1樹的有關概念樹的概念

6.1樹的有關概念數據對象D：D是具有相同特性的數據元素的集合。

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

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

數據關系R：ADTTree{樹的概念

6.1樹的有關概念基本操作P：ADTTree{查找類插入類刪除類}數據對象D：

數據關系R：樹的基本操作P

6.1樹的有關概念

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

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

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

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

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

6.1樹的有關概念刪除類：

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

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

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

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

6.1樹的有關概念樹的概念

***************************線性結構非線形結構—樹第一個數據元素

(無前驅)

根結點(無前驅)最后一個數據元素

(無后繼)多個葉子結點

(無后繼)其它數據元素(一個前驅、一個后繼)其它數據元素(一個前驅、多個后繼)單位行政機構的組織關系1）樹可表示具有分枝結構關系的對象

JIACBDHGFEKLM例6.1樹的有關概念樹的應用

2）樹是常用的數據組織形式

有些應用中數據元素之間并不存在分支結構關系，但是為了便于管理和使用數據，將它們用樹的形式來組織。C文件夾1文件夾n文件1文件2文件夾11文件夾12文件11文件12計算機的文件系統

不論是DOS文件系統還是window文件系統，所有的文件是用樹的形式來組織的。例6.1樹的有關概念樹的應用

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

JIACBDHGFEKLM6.1樹的有關概念樹的表示

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

（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樹的有關概念樹的表示

結點層：根結點的層定義為1，其它依此類推；樹的深度：樹中最大的結點層；結點的度：結點子樹的個數；樹的度：樹中最大的結點度；葉子結點：也叫終端結點，是度為0的結點；

樹的度為3樹的深度為4第1層第3層第2層第4層JIACBDHGFEKLM6.1樹的有關概念樹的有關術語

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

樹和森林的關系：（1）一棵樹去掉根，其子樹構成一個森林；（2）一個森林增加一個根結點成為樹。

6.1樹的有關概念6.2二叉樹6.3二叉樹的遍歷6.4遍歷的應用6.5線索二叉樹6.6樹和森林6.7Huffman樹及其應用第6章樹和二叉樹樹是一種分枝結構的對象，在樹的概念中，對每一個結點孩子的個數沒有限制，因此樹的形態多種多樣，本節我們主要討論另一種樹型結構——二叉樹。6.2二叉樹

A

F

G

E

D

C

B

6.2.1二叉樹的概念6.2.2二叉樹的性質6.2.3二叉樹的存儲結構6.2二叉樹6.2.1二叉樹的概念特點：二叉樹中每個結點最多有兩棵子樹；即二叉樹每個結點度小于等于2;左、右子樹不能顛倒——有序樹;二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念;

A

F

G

E

D

C

B概念：二叉樹或為空樹，或由根及兩顆不相交的左、右子樹構成，并且左、右子樹本身也是二叉樹。

A

F

G

E

D

C

B(a)

F

A

G

E

D

B

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

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

6.2.1二叉樹的概念6.2.2二叉樹的性質6.2.3二叉樹的存儲結構6.2二叉樹證明：最多結點數為各層結點個數相加，即

1+2+4+…+2k-1=2k-1性質2

深度為k的二叉樹最多有2k-1個結點。性質1

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

證明：用數學歸納法就可以證明。ABCDEFGIHJ

k層二叉樹6.2.2二叉樹的性質兩種特殊的二叉樹

A

G

F

E

D

C

B(a)K=3的滿二叉樹滿二叉樹：如果深度為k的二叉樹，有2k-1個結點則稱為滿二叉樹；完全二叉樹：二叉樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。

A

E

D

C

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

G

A

E

D

C

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

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

性質3

具有n個結點的完全二叉樹的深度為log2n+1由此可以推出：2k-1≤n＜2k取對數得：k-1≤log2n＜k由于k為整數，故有k-1=log2n

即：k=log2n+1

性質2:深度為k的二叉樹最多有2k-1個結點

A

E

D

C

B

E

D

Dk層的最多結點數k-1層的最多結點數6.2.2二叉樹的性質性質4

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

證明：二叉樹T的結點總數

n=n0+n1+n2（1）

注意：n1生成n1*1個節點，n2生成n2*2個節點，根結點不由任何結點產生由于分支結點是由度為1和度為2的結點生成的即分支結點總數b=n1+2*n2

（3）二叉樹的分支結點總數

b=n-1（2）

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

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

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

2i的

結點為其左孩子結點；2i+2

i/22i+1

2i

i+1

i6.2.2二叉樹的性質編號i=4雙親為i/2=2左子樹為2i=8右子樹為2i+1=9i=1只有根結點編號i=5雙親為i/2=2左子樹為2i=10右子樹為2i+1=11i=8,2i>n無左子樹1512345678910111213146.2.2二叉樹的性質通過性質5把非線性結構輕易轉化成了線性結構。

6.2.1二叉樹的概念6.2.2二叉樹的性質6.2.3二叉樹的存儲結構6.2二叉樹二叉樹的鏈式存儲表示二叉樹的順序存儲表示6.2.3二叉樹的存儲結構

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

i/22i+1

2i

i+1

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

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

D

A

∧

C

∧∧

E∧∧

F

B

∧root

A

F

E

D

C

B二叉樹n個結點的二叉樹中，有多少個空鏈接域？二叉樹的鏈式存儲表示6.2.3二叉樹的存儲結構性質6：n個結點的二叉樹中，共有n+1

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

D

A

∧

C

∧∧

E∧∧

F

B

∧root二叉樹的鏈式存儲表示6.2.3二叉樹的存儲結構三叉鏈表（帶雙親指針的二叉鏈表）:三叉鏈表中每個結點包含四個域：數據域、左指針域、右指針域、雙親指針域typedef

Structnode{DataTypedata;

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

parent結點結構:C語言的類型描述如下:二叉樹的鏈式存儲表示6.2.3二叉樹的存儲結構

A

F

E

D

C

BABDFECrootlchdatarch

parent二叉樹的鏈式存儲表示--三叉鏈表6.2.3二叉樹的存儲結構6.1樹的有關概念6.2二叉樹6.3二叉樹的遍歷6.4遍歷的應用6.5線索二叉樹6.6樹和森林6.7Huffman樹及其應用第6章樹和二叉樹

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

6.3二叉樹的遍歷

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

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

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

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

T：訪問根結點

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）訪問根結點（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）訪問根結點；（2）先序遍歷左子樹；

（3）先序遍歷右子樹；

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

A

F

G

E

D

C

B先序遍歷右圖所示的二叉樹（1）訪問根結點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）訪問根結點

后序遍歷序列：

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

LRT

的順序遍歷左子樹

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

LRT

的順序遍歷右子樹

（3）訪問根結點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）將隊頭元素出隊列，并判斷此元素是否有左右孩子，若有，則將它的左右孩子入列，否則轉（3）；（3）重復步驟（2），直到隊列為空。

A

F

G

E

D

C

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

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

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

（1）訪問根結點；（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){//找到左子樹的最左下的結點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);//找到最左下的結點

while(t){

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

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

棧空表明遍歷結束

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

（1）求結點的雙親、孩子結點、結點的層次；

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

6.4.1遍歷的基本應用6.4.2二叉樹的遍歷與存儲結構的應用

6.4.3二叉樹的相似與等價6.4遍歷的應用遞歸建立二叉樹我們按先序遞歸遍歷的思想來建立二叉樹。其建立思想如下：（1）建立二叉樹的根結點；（2）先序建立二叉樹的左子樹；（3）先序建立二叉樹的右子樹。二叉樹的生成6.4.1遍歷的基本應用二叉樹的生成的遞歸算法bitree*creat(){bitree*t;t=(bitree*)malloc(sizeof(bitree));t->data=x;t->lch=creat();t->rch=creat();returnt;}二叉樹的生成6.4.1遍歷的基本應用求二叉樹的葉子數。算法思想：采用任何遍歷方法，遍歷時判斷訪問的結點是不是葉子，若是則葉子數加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遍歷的基本應用

求二叉樹的深度算法思想：從第一層的根結點開始往下遞推可得到。下面給出后序遍歷求二叉樹深度的遞歸算法：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遍歷的基本應用

6.4.1遍歷的基本應用6.4.2二叉樹的遍歷與存儲結構的應用

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

A

C

B

D

A

D

C

B

A

C

D

B二叉樹的遍歷與存儲結構之間的轉化構造二叉樹

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

中序：264137581前246中264前3578中3758例左2前46中64右461前3578中3758246構造二叉樹6.4.2二叉樹的遍歷與存儲結構的應用根據給定的遍歷次序構造二叉樹，并給出先序遍歷序列。中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-作業構造二叉樹6.4.2二叉樹的遍歷與存儲結構的應用

e

d

c

b

f

a

+

*

/

-

-先序:-,+,a,*,b,-,c,d,/,e,f答案：構造二叉樹6.4.2二叉樹的遍歷與存儲結構的應用6.4遍歷的應用

6.4.1遍歷的基本應用6.4.2二叉樹的遍歷與存儲結構的應用6.4.3二叉樹的相似與等價二叉樹的相似與等價的含義兩株二叉樹具有相同結構指：（1）它們都是空的；（2）它們都是非空的，且左右子樹分別具有相同結構。定義具有相同結構的二叉樹為相似二叉樹。相似且相應結點包含相同信息的二叉樹稱為等價二叉樹?！靶螤睢毕嗤?.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

二叉樹的相似與等價結論：“遍歷”是二叉樹各種操作的基礎；可以在遍歷過程中對結點進行各種操作，對于一棵已知樹可求結點的雙親；求結點的孩子結點；判定結點所在層次；樹的深度；生成二叉樹……6.4.遍歷的應用6.5線索二叉樹

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

6.5.3線索二叉樹的遍歷

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

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

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

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

lch域指示結點的左孩子

lch域指示結點的前驅rtag=

rch域指示結點的右孩子

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

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

b

a

e

f

d

c

gNUlNUL遍歷指向該線性序列中的“前驅”和“后繼”的指針，稱作“線索”。線索鏈表：以上述結點結構構成的二叉鏈表作為二叉樹的存儲結構，叫線索鏈表。線索：指向前驅和后繼的指針。線索二叉樹：采用雙向鏈接結構表示的二叉樹。線索化：對二叉樹以某種次序遍歷使其變為線索二叉樹的過程。6.5.1線索二叉樹的表示線索二叉樹的相關概念6.5線索二叉樹

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

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

b

a

e

f

d

c

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

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)不帶頭結點的線索樹6.5.2二叉樹的線索化關于線索二叉樹的頭結點的設定方法2ABCDEFGIHJHEAD

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

在中序線索樹中找結點*p的中序后繼

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

//

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

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

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

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

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

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)//找中序序列的開始結點p=p->lch;do

{visit(p->data)

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

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

b

a

e

f

d

c

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

while(p->ltag==0）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Thrt->rchild=pre;}

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

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

R->lch=S;

//R的中序前驅是S

S->rtag=0;//修改s的右標識

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

{w=

Inordernext

(S);

R=w->lch

;

//R的中序后繼是w

}}6.5.3線索二叉樹的遍歷

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

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

6.6.1樹的存儲結構6.6.2樹、森林與二叉樹的轉換

6.6.3樹和森林的遍歷6.6樹和森林結點數6.6.1樹的存儲結構采用一組連續空間存儲樹的結點,通過保存每個結點的雙親結點的位置，表示樹中結點之間的結構關系。

9

A0B1C1D2E2F3G5H5I50123456789dataparent

ACHGDFBEI雙親表示法6.6.1樹的存儲結構雙親表示類型定義

#defineMAX100TypedefstructPTnode{//結點結構Elemdata;intparent;//雙親位置域}PTnode雙親表示法

dataparent樹結構:typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;

//根結點的位置和結點個數

}PTree;6.6.1樹的存儲結構雙親表示法樹結構:∧

A

B

C

D∧E

F∧

G∧

H

∧

I∧0123456789

7

9∧

8

2

6∧

45∧

3

∧樹的孩子鏈表圖示結點的孩子結點鏈表對樹的每個結點用線性鏈表存貯它的孩子結點ACHGDFBEI6.6.1樹的存儲結構孩子鏈表表示法

datafirstchild

childnext

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

childnext

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

}CTBox;雙親結點結構:

datafirstchild

找一個結點的孩子十分方便，但要找一個結點的雙親則要遍歷整個結構9∧

A0

B1C1D2∧E

2

F3∧

G5∧

H

5∧

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

7

9∧

8

2

6∧

45∧

3

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

*firstchild,*firstbrother;}CSNode,*CSTree;結點結構:

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

ABCEDFGroot

ABCEDFG

二叉樹：左、右子樹樹：左是孩子，右是兄弟6.6.1樹的存儲結構樹和二叉樹的存儲表示方式是一樣的，只是左右孩子表達的邏輯關系不同：二叉樹：左右孩子；樹的二叉鏈表：第一個孩子結點和右邊第一個兄弟結點。樹的二叉鏈表---孩子兄弟表示法把樹和二叉樹對應起來如何把樹的轉化成二叉樹？6.6樹和森林

6.6.1樹的存儲結構6.6.2樹、森林與二叉樹的轉換

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

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

對應得到ROOT(T1

)；由LBT

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

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

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

訪問根結點；先根順序遍歷T1;

先根順序遍歷T2;…

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