第6章-樹與二叉樹2數(shù)據(jù)結(jié)構(gòu)

第六章樹和二叉樹2本講主要內(nèi)容：

復(fù)習(xí)二叉樹的性質(zhì)通過習(xí)題鞏固二叉樹的相關(guān)知識和遍歷過程二叉樹的線索化樹和森林的簡單介紹習(xí)題6.27畫出一棵二叉樹，使其先序序列為EBADCFHGIKJ中序序列為ABCDEFGHIJKEBFDAHCIKJG習(xí)題6.28畫出一棵二叉樹，使其中序序列為DCBGEAHFIJK后序序列：DCEGBFHKJIAABIGCJHKEDE習(xí)題6.33假設(shè)用兩一維數(shù)組L[1..n],R[1..n]作為有n個結(jié)點的二叉樹的存儲結(jié)構(gòu)，分別指示結(jié)點i的左孩子和右孩子。0表示空。試編寫算法判別結(jié)點u是否為結(jié)點v的子孫。分析：12345678L12345678

2050700

0R34608000

12345678

設(shè)置一個隊列，初始化為結(jié)點V(即結(jié)點v入隊列）；循環(huán)：當(dāng)隊列非空，則隊頭元素出隊列，DeQueue(Q,e)如果e=u,則否則，e的左孩子、右孩子分別入隊列重復(fù)循環(huán)算法：Statusexercise_6.33(L,R,u,v){//L[i],R[i]分別存放二叉樹第i個結(jié)點的左、右孩子，判斷u是否為v的子孫,如是，返回OK,否則返回ERROR.IniQueue(Q),EnQueue(Q,v),While(!QueueEmpty(Q)){

DeQueue(Q,e); ife=ureturnOK; else{ifL[e]<>0EnQueue(Q,L[e]) ifR[e]<>0EnQueue(Q,R[e]) } } returnERROR}習(xí)題6.34條件同上，先由L和R建立一維數(shù)組T[1..n]，使T中第i個分量指示結(jié)點i的雙親，然后編寫算法判別結(jié)點u是否為結(jié)點v的子孫。12345678分析：L12345678

2050700

0R34608000

12345678

T01123355

12345678

習(xí)題6.47層次遍歷二叉樹ABDCGHEFStatusexercise_6.47(BiTreeT,Status(*Visit)(TElemTypee)){IniQueue(Q);if(T)EnQueue(Q,T);while(!QueueEmpty(Q)){

DeQueue(Q,p);Visit(p->data)；if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}//while習(xí)題6.49判斷給定的一棵二叉樹是否為完全二叉樹分析兩種存儲方式下判斷方法：順序存儲；二叉鏈表存儲ABIGCJHDABIGCJHED如果某結(jié)點左孩子不存在，但右孩子存在，則必然不是完全二叉樹如果某結(jié)點左孩子存在，但右孩子不存在，則此后的每一個結(jié)點也應(yīng)該不村子孩子結(jié)點，否則不是完全二叉樹。ABIGCJHD如果某結(jié)點的左、右孩子不存在，則此后每一個結(jié)點的都不應(yīng)該存在孩子結(jié)點，否則必然不是完全二叉樹Statusexercise_6.49(BiTreeT,){//若二叉樹T為完全二叉樹返回TRUE,否則返回FALSEIniQueue(Q);tag=1;if(T)EnQueue(Q,T);while(!QueueEmpty(Q)&&tag){

DeQueue(Q,p);if(p->lchild){

EnQueue(Q,p->lchild); if(p->rchild)EnQueue(Q,p->rchild)elsetag=0;}else{tag=0; if(p->rchild)returnFALSE;}}//whileWhile(!QueueEmpty(Q)){

DeQueue(Q,p); if((p->lchild)||(p->rchild))returnFALSE; }returnTRUE;}習(xí)題6.39假設(shè)在二叉鏈表中增設(shè)兩個域：雙親域指示雙親結(jié)點；標(biāo)志域(mark取值0··2)以區(qū)分在遍歷過程中到達該結(jié)點時應(yīng)該向左、向右或訪問該結(jié)點。試以此存儲結(jié)構(gòu)編寫不用棧的后序遍歷算法。－＋/a×datalchildparentrchildmark分析：每一個結(jié)點的mark初始化為0mark=0則訪問左子樹，同時mark變?yōu)?1則訪問右子樹，同時mark變?yōu)?2訪問根結(jié)點Statusexercise_6.39(BiTreeT,){//后序遍歷二叉樹，二叉樹的結(jié)點有五個域：data,parent,lchild,rchild,mark;mark初始值為0P=T;while(P){

swich(p->mark){ case0: p->mark=1; if(p->lchild)p=p->lchild;break; case1: p->mark=2; if(p->rchild)p=p->rchild;break; case2: p->mark=0;visit(P); p=p->parent;break; default:; }}6.3.2線索二叉樹非線性結(jié)構(gòu)的線性化操作 增加兩個指針：分別指向結(jié)點的前驅(qū)和后繼 利用二叉鏈表的n+1個空鏈域LTag=0lchild指示左孩子1lchild指示結(jié)點的前驅(qū)RTag=0rchild指示右孩子1rchild指示結(jié)點的后繼lchildrchildLTagRTagdata線索鏈表線索二叉樹在中序線索二叉樹中找結(jié)點的后繼葉子結(jié)點的后繼：右鏈域指示非終端結(jié)點：其右子樹的第一個結(jié)點中序線索二叉樹中找結(jié)點的前驅(qū)：左標(biāo)志域為1：左鏈域指示左標(biāo)志域為0：左子樹的最后一個結(jié)點。－＋/a×febc－dNILNIL中序線索二叉樹線索鏈表的存儲結(jié)構(gòu)typedef

enum

PointerTag{Link,Thread};//Link==0:指針;Thread==1:線索typedef

struct

BiThrNode{

TElemTypedata;

struct

BiThrNOde*lchild,*rchild;//左右孩子指針

PointerTagLTag,RTag;//左右標(biāo)志}//BiThrNode,*BiThrTree;雙向線索鏈表：添加頭結(jié)點：lchild域指向二叉樹的根結(jié)點；rchild域指向中序遍歷時訪問的最后結(jié)點01thrt00－00＋00/11a00*11b00－11－11－01e01fbt中序線索鏈表問題：如何在中序線索鏈表上實現(xiàn)二叉樹的中序遍歷雙向線索鏈表的二叉樹遍歷算法StatusInOrderTraverse_Thr(BiThrTreeT,visit())p=T->lchild;while(p!=T){ while(p->LTag==Link)p=p->lchild; Visit(p->data); while(p->RTag==Thread&&p->rchild!=T){ p=p->rchild;visit(p->data);} p=p->rchild; } returnOK;}//InOrderTraverse_Thr二叉樹的線索化：遍歷過程中修改空指針在中序遍歷過程中建立中序線索化鏈表：先建立一個頭結(jié)點thrt中序訪問二叉樹用一個指針pre指向剛剛訪問過的結(jié)點－＋/a×febc－dStatusInOrderThreading(BiThrTree&Thrt,BiThrTree){if(!Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(overflow);

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

Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//如空樹，則頭結(jié)點的lchild也指向頭結(jié)點else{

Thrt->lchild=T;pre=Thrt;p=T;

IniStack(S);Push(S,p);while(p||StackEmpty(S)){ if(p){push(S,p);p=p->lchild;} else{pop(p);p->Ltag=Thread;p->lchild=pre; if(!pre->rchild){pre->Rtag=Thread;pre->rchild=p;} pre=p; p=p->rchild; } }pre->rchild=Thrt;pre->Rtag=Thread;Thrt->rchild=pre;

}returnOK;}//中序線索化二叉樹的非遞歸算法。StatusInOrderThreading(BiThrTree&Thrt,BiThrTree){if(!Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(overflow);

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

Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//如空樹，則頭結(jié)點的lchild也指向頭結(jié)點else{

Thrt->lchild=T;pre=Thrt;

InThreading(T); pre->rchild=Thrt;pre->RTag=Thread;

Thrt->rchild=pre;}returnOK;}//InOrderThreading中序遍歷二叉樹的遞歸算法VoidInthreading(BiThrTreep){//中序遍歷二叉樹的遞歸算法 if(P){

InThreading(p->lchild); if(!p->lchild){p->LTag=Thread;p->lchild=pre;} if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}

pre=p;

Inthreading(p->rchild);` }}//Inthreading6.4樹和森林6.4.1樹的存儲結(jié)構(gòu)：雙親表示法：除根結(jié)點外的每個結(jié)點都只有唯一的雙親RABCDEFGHKRDCFHGKABE－1000311666數(shù)組下標(biāo)0123456789樹的雙親表存儲表示#defineMAX_TREE_SIZE100;Typedef

struct

PTNode{

TElemTypedata;

intpatent;}//PTNode;Typedef

struct{

PTNodenodes[MAX_TREE_SIZE];

intr,n;}//PTree;優(yōu)點：parent(T,x),Root(x)操作容易實現(xiàn)確定：求結(jié)點的孩子時需要遍歷整個結(jié)構(gòu)孩子表示法：datachild1child2child3childd······datadegreechild1child2childd······D為樹的度，結(jié)點同構(gòu)，空間浪費結(jié)點不同構(gòu)，空間不浪費，操作不方便RDCFHGKABE012345678935^6^^^^^^^012^789^適用于涉及孩子的操作樹的孩子鏈表存儲表示Typedef

struct

CTNode{//孩子結(jié)點

intchild;

struct

CTNode*next; }*childptr;Typedef

struct{

TElemTypedata;

childptr

firstchild;//孩子鏈表頭指針 }CTBox;Typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r; //結(jié)點數(shù)和根的位置； }//CTree;RDCFHGKABE4440－10266635^6^^^^^^^012^789^0123456789帶雙親的孩子鏈表孩子表示法和雙親表示法結(jié)合起來，即帶雙親的孩子鏈表孩子兄弟表示法：以二叉鏈表表示兩個鏈域：firstchild和nextsibling：第一個孩子結(jié)點和下一個兄弟結(jié)點