數(shù)據(jù)結(jié)構(gòu)(C／C++描述)第6章 樹與二叉樹

第6章樹和二叉樹6.1樹的定義及其存儲(chǔ)結(jié)構(gòu)6.2

二叉樹6.3

遍歷二叉樹和線索化二叉樹6.4

樹、森林和二叉樹的關(guān)系6.5哈夫曼樹及其應(yīng)用

6.1樹的定義及其存儲(chǔ)結(jié)構(gòu)數(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：6.1.1樹的定義及基本術(shù)語(yǔ)ABCDEFGHIJMKLA()T1T3T2樹根例如:B(E,F(K,L)),

C(G),

D(H,I,J(M))(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無(wú)序樹：子樹之間不存在確定的次序關(guān)系?；拘g(shù)語(yǔ)結(jié)點(diǎn):結(jié)點(diǎn)的度:樹的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支分支的個(gè)數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM(從根到結(jié)點(diǎn)的)路徑：孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)結(jié)點(diǎn)的層次:樹的深度：

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1,第l層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次任何一棵非空樹是一個(gè)二元組Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點(diǎn)，F(xiàn)被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBEFKLCGDHIJMF對(duì)比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無(wú)前驅(qū))

根結(jié)點(diǎn)(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素(無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)6.1.2樹的存儲(chǔ)結(jié)構(gòu)一、雙親數(shù)組表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法ABCDEFGr=0n=70

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、雙親表示法:

typedefstructPTNode

{TElemTypedata;

int

parent;//雙親位置域}PTNode;

dataparent#defineMaxTreeSize100結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類型描述:typedefstruct{

PTNode

nodes[MaxTreeSize];

int

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

}

PTree;樹結(jié)構(gòu):r=0n=7dataparentfirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645123二、孩子鏈表表示法:-1000224typedefstructCTNode

{

int

child;//數(shù)組下標(biāo)

structCTNode

*nextchild;}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextchildC語(yǔ)言的類型描述:

typedefstruct{TElemTypedata;//結(jié)點(diǎn)的值ChildPtrfirstchild;//孩子鏈的頭指針

}

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

datafirstchildtypedefstruct{

CTBox

nodes[MaxTreeSize];//雙親結(jié)點(diǎn)結(jié)構(gòu)數(shù)組

int

n,r;

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

CTree;樹結(jié)構(gòu):ABCDEFGrootABCEDFGABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法root森林的二叉鏈表表示typedefstruct

CSNode{

TElemType

data;

struct

CSNode

*firstchild,*nextsibling;}

CSNode,*CSTree;C語(yǔ)言的類型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddata

nextsibling6.2

二叉樹6.2.1

二叉樹的定義

二叉樹或?yàn)榭諛?；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹EF二叉樹的5種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹6.2.2

二叉樹的性質(zhì)

性質(zhì)1：

在二叉樹的第i層上至多有2i-1

個(gè)結(jié)點(diǎn)。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時(shí)，只有一個(gè)根結(jié)點(diǎn)，

2i-1

=20

=1；假設(shè)對(duì)所有的j，1≤j

i，命題成立;二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-2

2=2i-1

。性質(zhì)2：

深度為k的二叉樹上至多含2k-1

個(gè)結(jié)點(diǎn)（k≥1）證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為

20+21+

+2k-1=2k-1

性質(zhì)3：

對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2

個(gè)度為

2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1證明：設(shè)二叉樹上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1

+2n2而b=n-1=n0+n1+n2-1由此，n0=n2

+1兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij完全二叉樹：如果一顆二叉樹只有最下一層結(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

B

性質(zhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1證明：設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1≤n<

2k即k-1

≤log2

n<k

因?yàn)閗只能是整數(shù)，因此，k=log2n

+1性質(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)是二叉樹的根，無(wú)雙親,否則，編號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn);

(2)若2i>n，則該結(jié)點(diǎn)i無(wú)左孩子，

否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1>n，則該結(jié)點(diǎn)i無(wú)右孩子結(jié)點(diǎn)，

否則，編號(hào)為2i+1

的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹的順序存儲(chǔ)表示#define

MaxTreeSize100

//二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[MaxTreeSize

+1];

//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;一、二叉樹的順序存儲(chǔ)表示順序存儲(chǔ)結(jié)構(gòu):按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問：順序存儲(chǔ)后能否復(fù)原成唯一對(duì)應(yīng)的二叉樹形狀？答：若是完全/滿二叉樹則可以做到唯一復(fù)原。而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)5）例如，對(duì)應(yīng)[2]的兩個(gè)孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。T[0]一般不用討論：不是完全二叉樹怎么辦？答：一律轉(zhuǎn)為完全二叉樹！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便

例如:

ABDCEF

1234567891011121314ABCDEF2511437相應(yīng)完全二叉樹

n=15二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表ADEBCFrootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表typedefstruct

BiTNode

{

//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;

structBiTNode*lchild,*rchild;

//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類型描述如下:rootADEBCF2．三叉鏈表parent

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):

typedefstruct

TriTNode//結(jié)點(diǎn)結(jié)構(gòu)

{TElemTypedata;

struct

TriTNode

*lchild,*rchild;

//左右孩子指針

structTriTNode

*parent;//雙親指針

}

TriTNode,*TriTree;parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類型描述如下:6.3遍歷二叉樹和線索化二叉樹一、遍歷的概念二、先左后右的遍歷算法三、算法的遞歸描述四、中序遍歷算法的非遞歸描述五、遍歷算法的應(yīng)用舉例6.3.1二叉樹的遍歷

順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。一、遍歷的概念“訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。

“遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，

每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑進(jìn)行遍歷的問題。對(duì)“二叉樹”而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。遍歷二叉樹（TraversingBinaryTree）遍歷定義——指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游）。遍歷用途——它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。

遍歷方法——牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看都是“先左后右”。二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法根左子樹右子樹根根根根根

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法（DLR）

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。中（根）序遍歷算法（LDR）

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。后（根）序遍歷算法（LRD）ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A三、算法的遞歸描述void

PreOrderTraverse(BiTreeT){//

先序遍歷二叉樹

if(T){

VisitElement(T->data);//訪問結(jié)點(diǎn)

PreOrderTraverse

(T->lchild);//遍歷左子樹

PreOrderTraverse

(T->rchild);//遍歷右子樹

}}void

InOrderTraverse(BiTreeT){//

中序遍歷二叉樹

if(T){

①InOrderTraverse(T->lchild);//遍歷左子樹

②VisitElement

(T->data);//訪問結(jié)點(diǎn)

③InOrderTraverse

(T->rchild);//遍歷右子樹

}}void

PostOrderTraverse

(BiTreeT){//

后序遍歷二叉樹

if(T){

①PostOrderTraverse(T->lchild);//遍歷左子樹

②PostOrderTraverse(T->rchild);//遍歷右子樹

③VisitElement(T->data);//訪問根結(jié)點(diǎn)

}}對(duì)遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將visit語(yǔ)句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說(shuō)這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過3次。AFEDCBG第1次經(jīng)過時(shí)訪問＝先序遍歷第2次經(jīng)過時(shí)訪問＝中序遍歷第3次經(jīng)過時(shí)訪問＝后序遍歷2.二叉樹遍歷的時(shí)間效率和空間效率時(shí)間效率:O(n)

//每個(gè)結(jié)點(diǎn)只訪問一次空間效率:O(n)

//棧占用的最大輔助空間（精確值：樹深為k的遞歸遍歷需要k+1個(gè)輔助單元?。?duì)遍歷的分析：從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過3次。AFEDCBG第1次經(jīng)過時(shí)訪問＝先序遍歷第2次經(jīng)過時(shí)訪問＝中序遍歷第3次經(jīng)過時(shí)訪問＝后序遍歷中序序列：DBFEGACint

InOrderTraverse(BiTreeT){BiTNode*p;InitStack(S);p=T;

while(p||!StackEmpty(S)){if

(p) {

Push(S,p);p=p->lchild;} //根結(jié)點(diǎn)進(jìn)棧，遍歷左子樹else

{Pop(S,p);//根結(jié)點(diǎn)退棧，訪問根結(jié)點(diǎn)，遍歷右子樹VisitElement(p->data);p=p->rchild;}//else}//whilereturn

OK;}

//InOrderTraverse四、中序遍歷算法的非遞歸描述五、遍歷算法的應(yīng)用舉例1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)2、建立二叉樹的存儲(chǔ)結(jié)構(gòu)1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想:

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)”

的操作改為:若是葉子，則計(jì)數(shù)器增1。voidCountLeaf(BiTreeT,int&count){//先序遍歷二叉樹，計(jì)算葉子結(jié)點(diǎn)個(gè)數(shù)if(T){if((!T->lchild)&&(!T->rchild))

count++;//對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf2、建立二叉樹的存儲(chǔ)結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法

以字符串的形式“根左子樹

右子樹”定義一棵二叉樹例如:以空白字符“”表示ABCDAB

C

D

空樹只含一個(gè)根結(jié)點(diǎn)的二叉樹A以字符串“A”表示以下列字符串表示intCreateBiTree(BiTree&T)

{//按先序序列構(gòu)造二叉鏈表表示的二叉樹Tscanf(&ch);if(ch=='')T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹

CreateBiTree(T->rchild);//構(gòu)造右子樹}

returnOK;//遞歸出口}//CreateBiTreeAB

C

D

ABCD上頁(yè)算法執(zhí)行過程舉例如下:ATBCD^^^^^①scanf(&ch);②if(ch=='')T=NULL;

else

{③

if(!(T=newBiTNode))

exit(OVERFLOW);④

T->data=ch;⑤

CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnok//遞歸出口

僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹

如果同時(shí)已知二叉樹的中序序列“cbdaegf”,則會(huì)如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.3.2

線索化二叉樹一、何謂線索二叉樹？遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA

指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”與其相對(duì)應(yīng)的二叉樹，稱作“線索二叉樹”包含“線索”的存儲(chǔ)結(jié)構(gòu)，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^對(duì)線索鏈表中結(jié)點(diǎn)的約定：

在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域的值為“指針Link=0”；否則Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“線索Thread=1”。若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為“指針Link=0”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“線索Thread=1”。

如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表”typedefstruct

BiThrNode{

TElemTypedata;

struct

BiThrNode

*lchild,*rchild;

//左右指針

PointerThr

LTag,RTag;

//左右標(biāo)志}

BiThrNode,*BiThrTree;線索鏈表的類型描述：

typedef

enum

{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索規(guī)定：1）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。為了避免混淆，增加兩個(gè)標(biāo)志域，如下圖所示：lchildLTagdataRTagrchild約定:當(dāng)Tag域?yàn)?時(shí),表示正常情況;當(dāng)Tag域?yàn)?時(shí),表示線索情況.有關(guān)線索二叉樹的幾個(gè)術(shù)語(yǔ)：

線索鏈表：

用前頁(yè)結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表

線索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針

線索二叉樹：加上線索的二叉樹（圖形式樣）

線索化：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程注：在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的，當(dāng)標(biāo)志為0時(shí)，則需要通過一定運(yùn)算才能找到它的后繼。ABCGEIDHFroot懸空？懸空？解：該二叉樹中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：例2：畫出以下二叉樹對(duì)應(yīng)的中序線索二叉樹。為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)對(duì)應(yīng)的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,G0--root0二、線索鏈表的遍歷算法由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。對(duì)中序線索化鏈表的遍歷算法

※中序遍歷的第一個(gè)結(jié)點(diǎn)？

※在中序線索化鏈表中結(jié)點(diǎn)的后繼？

左子樹上處于“最左下”（沒有左子樹）的結(jié)點(diǎn)若無(wú)右子樹，則為后繼線索所指結(jié)點(diǎn)否則為對(duì)其右子樹進(jìn)行中序遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)void

InOrderTraverse_Thr(BiThrTreeT){//線索二叉樹的中序遍歷算法p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T)

{

//空樹或遍歷結(jié)束時(shí)，p==Twhile(p->LTag==Link)p=p->lchild;//查找第一個(gè)結(jié)點(diǎn)－最左下

if(!visit(p->data))returnERROR;//若起點(diǎn)值為空則出錯(cuò)告警while(p->RTag==Thread&&p->rchild!=T)

{//若有后繼標(biāo)志，則直接提取p->rchild中線索并訪問p=p->rchild;Visit(p->data);//訪問后繼結(jié)點(diǎn)

}p=p->rchild;//當(dāng)前結(jié)點(diǎn)右域不空或已經(jīng)找好了后繼，則一律//從結(jié)點(diǎn)的右子樹開始重復(fù){}的全部過程。

}}在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前驅(qū)。三、如何建立線索鏈表？對(duì)應(yīng)的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,G0--root0void

InThreading(BiThrTreep)

{

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

InThreading(p->lchild);

//左子樹線索化

if(!p->lchild)//建前驅(qū)線索{p->LTag=1;p->lchild=pre;}

if(!pre->rchild)//建后繼線索{pre->RTag=1;pre->rchild=p;}

pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);

//右子樹線索化

}//if}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//構(gòu)建中序線索鏈表if(!(Thrt=newBiThrNode))exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加頭結(jié)點(diǎn)returnOK;}//InOrderThreading……if(!T)

Thrt->lchild=Thrt;//若二叉樹空，左指針回指else{Thrt->lchild=T;

pre=Thrt;//設(shè)置前趨指針初值

InThreading(T);//調(diào)用算法6.7

pre->rchild=Thrt;

//處理最后一個(gè)結(jié)點(diǎn)

pre->RTag=Thread;Thrt->rchild=pre;

}

6.4樹、森林和二叉樹的關(guān)系6.4.1樹、森林和二叉樹的轉(zhuǎn)換設(shè)森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹

B=(LBT,Node(root),RBT);由森林轉(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。T1T11,T12,…,T1mT2,…,TnLBTRBTroot轉(zhuǎn)換步驟：step1:將樹中同一結(jié)點(diǎn)的兄弟相連;step2:保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子順時(shí)針旋轉(zhuǎn)45度角。加線抹線旋轉(zhuǎn)討論1：樹如何轉(zhuǎn)為二叉樹？方法：加線—抹線—旋轉(zhuǎn)

abeidfhgc樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連長(zhǎng)兄為父孩子靠左根結(jié)點(diǎn)肯定沒有右孩子！討論2：二叉樹怎樣還原為樹？abeidfhgc要點(diǎn)：把所有右孩子變?yōu)樾值埽∪缓竽鏁r(shí)針旋轉(zhuǎn)45度。

abeidfhgc法1：①各森林先各自轉(zhuǎn)為二叉樹；②依次連到前一個(gè)二叉樹的右子樹上。討論3：森林如何轉(zhuǎn)為二叉樹？法2：

森林直接變兄弟，再轉(zhuǎn)為二叉樹即F={T1,T2,…,Tm}B={root,LB,RB}ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林轉(zhuǎn)二叉樹舉例：（法2）兄弟相連長(zhǎng)兄為父孩子靠左頭根為根

A討論4：二叉樹如何還原為森林？要點(diǎn)：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?/p>

ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B={root,LB,RB}F={T1,T2,…,Tm}

由此，樹和森林的各種操作均可與二叉樹的各種操作相對(duì)應(yīng)。

應(yīng)當(dāng)注意的是，和樹對(duì)應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟6.4.2樹和森林的遍歷一、樹的遍歷二、森林的遍歷三、樹的遍歷的應(yīng)用樹的遍歷可有3條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。

層次遍歷時(shí)頂點(diǎn)的訪問次序：ABCDEFGHIJK

先根遍歷時(shí)頂點(diǎn)的訪問次序：ABEF

C

DGHIJK后根遍歷時(shí)頂點(diǎn)的訪問次序：EFB

C

IJKHG

DAABCD

EFGHIJK

BCDEFGHIJK1。森林中第一棵樹的根結(jié)點(diǎn)；2。森林中第一棵樹的子樹森林；3。森林中其它樹構(gòu)成的森林?？梢苑纸獬?部分：森林

若森林不空，則訪問森林中第一棵樹的根結(jié)點(diǎn);先序遍歷森林中第一棵樹的子樹森林;先序遍歷森林中（除第一棵樹之外）其余樹構(gòu)成的森林。先序遍歷:森林的遍歷即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行先根遍歷。

BCDEFGHIJK森林