數(shù)據(jù)結(jié)構(gòu)-樹和森林的表示和遍歷

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

A1

B2

C

3

D4

E5

F6

Gdata-1000225parent雙親表示法

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

typedef

struct

PTNode{

TElemTypedata;

intparent;//雙親位置域

}PTNode;雙親表示法typedef

struct{

PTNode

nodes[MAX_TREE_SIZE];

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

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

A1

B2

C3

D4

E5

F6

G

123firstchild456孩子鏈表表示法typedef

struct

CTNode

{

intchild;

struct

CTNode

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

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

typedef

struct{

TElemTypedata;

ChildPtr

firstchild;//孩子鏈的頭指針

}

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

datafirstchild孩子鏈表表示法typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

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

}

CTree;樹結(jié)構(gòu):帶雙親的孩子鏈表表示法1.雙親表示法，PARENT（T，x）可以在常量時間內(nèi)完成，但是求結(jié)點的孩子時需要遍歷整個結(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é)點結(jié)構(gòu):

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

struct

CSNode{

TElemTypedata;

struct

CSNode

*firstchild,*nextsibling;}

CSNode,*CSTree;C語言的類型描述:樹的孩子兄弟存儲表示法ABCDEFGBCEFGADrootABCDEFG森林和二叉樹的對應關系樹與二叉樹的對應關系：給定一棵樹，通過樹的二叉鏈表表示法可以找到唯一的一棵二叉樹與之對應。樹的二叉鏈表的右子樹一定是空的。森林與二叉樹的對應關系：將森林中的第二棵樹看成第一棵樹的兄弟即可。森林和二叉樹的對應關系T1T11,T12,…,T1mT2,…,TnLBTRBTroot森林和二叉樹的對應關系由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F=Φ，則B=Φ;由ROOT(T1)對應得到Node(root);否則，由(t11,t12,…,t1m)對應得到LBT;由(T2,T3,…,Tn

)對應得到RBT。森林和二叉樹的對應關系ABCDEFGHIJABCDEFGHIJ森林轉(zhuǎn)換成二叉樹:先將森林中的所有樹轉(zhuǎn)換成二叉樹GIJHBCD森林和二叉樹的對應關系ABCDEFGHIJ以第一棵二叉樹的根為樹根，將森林中所有的二叉樹轉(zhuǎn)換成一棵二叉樹AEF森林和二叉樹的對應關系由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:由LBT對應得到(t11,t12,…，t1m);若B=Φ,則F=Φ;否則，由Node(root)

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

struct

CSNode{

TElemTypedata;

struct

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

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

printStack(S);

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

CreatTree(CSTree

&T){T=NULL;

for(scanf