樹和森林的表示方法和遍歷樹和森林的遍歷樹的表示方法小結(jié)和作業(yè)森林和二叉樹的對應(yīng)關(guān)系一、雙親表示法二、孩子鏈表表示法三、帶雙親的孩子鏈表表示法樹的存儲結(jié)構(gòu)四、樹的孩子兄弟表示法雙親表示法用一組連續(xù)空間存儲樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在鏈表中的位置。雙親表示法ABCDEFGroot=0n=70

A1

B2

C

3

D4

E5

F6

Gdata-1000225parent雙親表示法

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

typedef

struct

PTNode{

TElemTypedata;

intparent;//雙親位置域

}PTNode;雙親表示法typedef

struct{

PTNode

nodes[MAX_TREE_SIZE];

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

}PTree;樹結(jié)構(gòu):孩子鏈表表示法1）結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹的度k,這樣n個(gè)結(jié)點(diǎn)度為k的樹必有n(k-1)+1個(gè)空鏈域.1.多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹的根datachild1child2……….childD孩子鏈表表示法2）結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度ddatachild1child2……….childD2.孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲，再用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表孩子鏈表表示法ABCDEFGroot=0n=7data0

A1

B2

C3

D4

E5

F6

G

123firstchild456孩子鏈表表示法typedef

struct

CTNode

{

intchild;

struct

CTNode

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

childnextchildC語言的類型描述:孩子鏈表表示法

typedef

struct{

TElemTypedata;

ChildPtr

firstchild;//孩子鏈的頭指針

}

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

datafirstchild孩子鏈表表示法typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

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

}

CTree;樹結(jié)構(gòu):帶雙親的孩子鏈表表示法1.雙親表示法，PARENT（T，x）可以在常量時(shí)間內(nèi)完成，但是求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)。2.孩子鏈表表示法，適于那些涉及孩子的操作，卻不適于PARENT（T，x）操作。3.將雙親表示法和孩子鏈表表示法合在一起，可以發(fā)揮以上兩種存儲結(jié)構(gòu)的優(yōu)勢，稱為帶雙親的孩子鏈表表示法帶雙親的孩子鏈表表示法ABCDEFGroot=0n=7Parent0

A1

B2C3

D4

E5

F6

G

123-1000225456datafirstchild樹的孩子兄弟存儲表示法ABCDEFGABCDEFG樹的孩子兄弟存儲表示法又稱為二叉樹表示法，以二叉鏈表作為樹的存儲結(jié)構(gòu)。結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsibling指向第一個(gè)孩子結(jié)點(diǎn)指向下一個(gè)兄弟結(jié)點(diǎn)樹的孩子兄弟存儲表示法typedef

struct

CSNode{

TElemTypedata;

struct

CSNode

*firstchild,*nextsibling;}

CSNode,*CSTree;C語言的類型描述:樹的孩子兄弟存儲表示法ABCDEFGBCEFGADrootABCDEFG森林和二叉樹的對應(yīng)關(guān)系樹與二叉樹的對應(yīng)關(guān)系：給定一棵樹，通過樹的二叉鏈表表示法可以找到唯一的一棵二叉樹與之對應(yīng)。樹的二叉鏈表的右子樹一定是空的。森林與二叉樹的對應(yīng)關(guān)系：將森林中的第二棵樹看成第一棵樹的兄弟即可。森林和二叉樹的對應(yīng)關(guān)系T1T11,T12,…,T1mT2,…,TnLBTRBTroot森林和二叉樹的對應(yīng)關(guā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。森林和二叉樹的對應(yīng)關(guān)系A(chǔ)BCDEFGHIJABCDEFGHIJ森林轉(zhuǎn)換成二叉樹:先將森林中的所有樹轉(zhuǎn)換成二叉樹GIJHBCD森林和二叉樹的對應(yīng)關(guān)系A(chǔ)BCDEFGHIJ以第一棵二叉樹的根為樹根，將森林中所有的二叉樹轉(zhuǎn)換成一棵二叉樹AEF森林和二叉樹的對應(yīng)關(guān)系由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:由LBT對應(yīng)得到(t11,t12,…，t1m);若B=Φ,則F=Φ;否則，由Node(root)

對應(yīng)得到ROOT(T1);由RBT對應(yīng)得到(T2,T3,…,Tn)。森林和二叉樹的對應(yīng)關(guān)系二叉樹轉(zhuǎn)換成森林1）抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹2）還原：將孤立的二叉樹還原成樹森林和二叉樹的對應(yīng)關(guān)系GIJHBCDAEFABCDEFGHIJ1.斷開二叉樹中右分支中搜索到的所有右孩子間的連線森林和二叉樹的對應(yīng)關(guān)系A(chǔ)BCDEFGHIJ2.將得到的二叉樹全部還原成樹ABCDEFGHIJ森林和二叉樹的對應(yīng)關(guān)系由樹、森林和二叉樹的相互轉(zhuǎn)換可知，樹和森林的各種操作均可與二叉樹的各種操作相對應(yīng)。不過，和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋鹤笞訕涫呛⒆?，右子樹是兄弟。樹和森林的遍歷一、樹的遍歷二、森林的遍歷三、樹的遍歷的應(yīng)用樹的遍歷-先根(次序)遍歷先根(次序)遍歷:若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。ABCDEFGHIJKABCDEFGHIJKABEFCDGHIJK先根(次序)遍歷序列為：樹的遍歷-后根(次序)遍歷后根(次序)遍歷:若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。ABCDEFGHIJKABCDEFGHIJKAEFBCIJKHGD后根(次序)遍歷序列為：樹的遍歷-按層次遍歷按層次遍歷:若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。ABCDEFGHIJKABCDEFGHIJKABCDEFG按層次遍歷序列為：HIJK樹的遍歷樹的二叉樹表示:BCDEFGABCEDGFA樹先根遍歷ABEFCDG因此，樹的先根遍歷結(jié)果與其對應(yīng)二叉樹表示的先序遍歷結(jié)果相同樹的遍歷樹的二叉樹表示:BCDEFGABCEDGFA樹后根遍歷EFBCGDA因此，樹的后根遍歷結(jié)果與其對應(yīng)二叉樹表示的中序遍歷結(jié)果相同森林的遍歷CBEFDGHIJKBCDEFGHIJK1.森林中第一棵樹的根點(diǎn)；2.森林中第一棵樹的子森林；3.森林中其它樹構(gòu)成的森林。森林可以分解成三部分：森林的遍歷-先序遍歷若森林不空，則1）訪問森林中第一棵樹的根結(jié)點(diǎn);即：依次從左至右對森林中的每一棵樹進(jìn)行先根遍歷。2）先序遍歷森林中第一棵樹的子樹森林;3）先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。ABDCEGFHIJKABCDEFGHIJK先根遍歷序列為：ABCDEFGHIKJ森林的遍歷-先序遍歷ABDCEGFHIJK森林對應(yīng)的二叉樹：ABDCEGFHIJK森林的遍歷-中序遍歷森林不空，則中序遍歷森林中第一棵樹的子樹森林;即：依次從左至右對森林中的每一棵樹進(jìn)行后根遍歷。訪問森林中第一棵樹的根結(jié)點(diǎn);中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。中序遍歷序列為：ABCEDGFKIJH森林的遍歷-中序遍歷ABDCEGFHIJKABCDEFGHIJKABDCEGFHIJKABDCEGFHIJK樹的遍歷與二叉樹遍歷的對應(yīng)關(guān)系先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷樹的遍歷的應(yīng)用設(shè)樹的存儲結(jié)構(gòu)為孩子兄弟鏈表typedef

struct

CSNode{

TElemTypedata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree;一、求樹的深度二、輸出樹中所有從根到葉子的路徑三、建立樹的存儲結(jié)構(gòu)樹的遍歷的應(yīng)用BCDEFGA一、求樹的深度的算法：1、如果T為空，則樹的深度為02、求出T每棵子樹的深度3、從所有子樹的深度中取最大，然后加1，即為樹的深度樹的遍歷的應(yīng)用int

Depth(TreeT){//只考慮邏輯結(jié)構(gòu)if(!T)return(0);

for(p=T1,T2,…Tn){//每棵子樹

d[p]=Depth(p)

a=max(d[1],d[2],…d[n])return(a+1)}樹的遍歷的應(yīng)用int

Depth(CSTreeT){//二叉鏈表作為存儲結(jié)構(gòu)}if(!T)return0;//空樹p=T->firstchild;d=0;while(p){//依次求子樹的深度}return(d+1);d1=Depth(p);if(d1>d)d=d1;p=p->nextsibling;BCDEFGABCEDGFA樹的遍歷的應(yīng)用int

Depth(CSTreeT){}if(!T)return0;d1=Depth(T->firstchild);d2=Depth(T->nextsibling);return(max(d1,d2));d1=d1+1;BCDEFGABCEDGFA樹的遍歷的應(yīng)用二、輸出樹中所有從根到葉子的路徑的算法:ABCDEFGHIJK對左圖所示的樹，其輸出結(jié)果應(yīng)為：ABEABFACADGHIADGHJADGHK樹的遍歷的應(yīng)用對樹先根遍歷(深度優(yōu)先)1、T為空，棧中存放的是從根到T的父結(jié)點(diǎn)的路徑2、將T壓棧，棧中存放的是從根到T的路徑3、遞歸訪問T的子樹4、將T出棧樹的遍歷的應(yīng)用void

AllPath(CSTreeT,Stack&S){//樹的先根遍歷}//AllPath

Push(S,T->data);//樹根壓棧

p=T->firstchild//T的第一顆子樹while(p){//T的所有子樹

AllPath(p,S);p=p->nextsibling;}Pop(S);//訪問完T的所有子樹

if(!T){PrintStack(S),return}樹的遍歷的應(yīng)用void

OutPath(CStreeT,Stack&S){

Push(S,T->data);

OutPath(T->firstchild,S);

OutPath(T->nextsibling,S);if(!T)return;}利用二者的先序遍歷結(jié)果相同BCDEFGABCEDGFAif(!T->firstchild){//”葉子”節(jié)點(diǎn)

printStack(S);

pop(S);}樹的遍歷的應(yīng)用三、建立樹的存儲結(jié)構(gòu)的算法:和二叉樹類似，不同的定義相應(yīng)有不同的算法。假設(shè)以二元組(F,C)的形式自上而下、自左而右依次輸入樹的各邊，建立樹的孩子-兄弟鏈表。樹的遍歷的應(yīng)用ABCDEFG對左側(cè)所示樹的輸入序列應(yīng)為:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)(‘‘,’#’)(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)ABCD可見，算法中需要一個(gè)隊(duì)列保存已建好的結(jié)點(diǎn)的指針樹的遍歷的應(yīng)用void

CreatTree(CSTree

&T){T=NULL;

for(scanf