數(shù)據(jù)結(jié)構(gòu)-6.2二叉樹遍歷

遍歷二叉樹和線索二叉TraversingBinary遍TraversingBinary

它是樹結(jié)構(gòu)、刪除、修改、查切運(yùn)算的基礎(chǔ)和。右”。遍歷規(guī)則二叉樹由根、 、 構(gòu)成，定義為D、L、 若限定先左后右，則有三種實(shí)現(xiàn)方案先序遍中序遍后序遍 先序遍中序遍后序遍typedefstructnode{intdata;structnode}node;node*root;LDR(node{if(root}

DLR(node*root{ifroot!=NULL){printf(“%d”,root->data);// DLR(root->lchild);//遞歸遍歷左DLR(root->rchild);//遞歸遍歷右LRD(nodeLRD(node{if(root}先序遍歷

ABABCDD D D DD 先序遍歷序列：ABD ABCAABCAD L LL AABCD中序遍歷序列：B LRDABCLRDABCD L LL AABCD后序遍歷序列： BCABDECDBEACDABDECDBEACDEBCA EABECFDGHK例ABECFDGHKAABCDEFGH中序序列BDBDCAEHGK后序序列DDCBHKGFE++*E*D/CAB

先序遍歷結(jié)+**/ABCD—前綴表示中序遍歷結(jié)A/B*C*D+后序遍歷結(jié)AB/C*D*E—后綴表示層次遍歷結(jié)+*E*D/CA遍歷算法的路徑是相同的，只是結(jié)點(diǎn)的時(shí)機(jī)不同。 第1次經(jīng)過 第3次經(jīng)過 時(shí)間效率:O(n)//每個(gè)結(jié)點(diǎn)只 空間效率:O(nDLR(node ifroot!=NULL)//非空二叉樹條件，等效于{if(!root->lchild&&!root->rchild) //遞歸遍歷左，直到葉子處DLR(root->rchild);}//遞歸遍歷右，直到葉子處}return(0);編寫中序遍歷T的非遞歸算法Status while(!StackEmpty(S))while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到盡頭 if((!StackEmpty(S if(!Visit(p->data))returnERROR;Push(S,p->rchild);}//ifreturnOK;編寫中序遍歷T的非遞歸算法Status while(p||!StackEmpty(S))if(p){Push(S,p);p=p->lchild);}else //根指針退棧，根結(jié)點(diǎn)，遍歷 if(!Visit(p->data))returnERROR;p=p->rchild);}//elsereturnOK;怎樣建樹？ 怎樣建樹？ 考慮1：輸入結(jié)點(diǎn)時(shí)怎樣表示“無孩子A考慮2：以何種遍歷方式來輸入和建樹B字符串輸完后 (如$)，因?yàn)?/p>

ABCDEGFABCDEGF If(ch==’’)if(!(TBiTNode*)malloc(sizeof(BiTNode))))exit(overflow); }return}BDCEAFHGDECBHGFA，請(qǐng)畫出這棵二叉樹。①由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即②由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左的子孫（即BDCE），其右部必全部是右的③繼而，根據(jù)后序中的DECB可確定B為A的左孩子，已知中序遍歷：BDCEFH已知后序遍歷：DECA

HGF （DC

（FHThreadedBinary線ThreadedBinary討論：用二叉鏈表法（l_child,r_child） 有有n+1個(gè)證明：用二叉鏈表包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必2n個(gè)鏈域（見二叉鏈表數(shù)據(jù)類型說明）除根結(jié)點(diǎn)外，二叉樹中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，意即每個(gè)結(jié)點(diǎn)地址占用了雙親的一個(gè)直接后繼，n個(gè)結(jié)點(diǎn)地址共占用了n-1個(gè)雙親的指針域。也就是說，所以，空指針數(shù)目＝2n－(n-1)=n+1個(gè) 這就是這就是線索二叉樹（ThreadedBinary例如對(duì)某二叉樹的中序遍歷結(jié)果是BDCEAFHG，意味著已 起來，這叫做“線索化①每個(gè)結(jié)點(diǎn)增加兩個(gè)域：fwd和

若結(jié)點(diǎn)有左，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；若結(jié)點(diǎn)有右，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。

為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域各各 線索

線索化過程就是在遍歷過修改空指針的過程將空的rchild改為結(jié)點(diǎn)的直接非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況0011110101GEIDJHCFB0001010111A

Rtag=1 線索二叉樹的生成——線索 線索化過程就是在遍歷修改空指針的過例1：畫出以下二叉樹對(duì)應(yīng)的中序解：對(duì)該二叉樹中序遍歷的結(jié)果為:HDIB,E,AFC

懸空

對(duì)應(yīng)的中序線索二叉樹結(jié)構(gòu)如圖所示注：此圖中序遍歷結(jié)果為:HD,I,B,E,A,FC00000A00A00B00C00B00C00D01E11F11G10D01E11F11G11H11I11H11I1

解:因?yàn)橹行虮闅v序列是：55402560280833對(duì)應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即線索二叉樹的生成算法（遞歸算法見P134-135）目的：在遍歷二叉樹的過修改空指針，添加前驅(qū)或后繼為了記下遍歷過結(jié)點(diǎn)的先后次序，需要設(shè)置兩個(gè)指針以中序遍歷建立中序線索化鏈表算StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)//中序遍歷二叉樹T，并將其中序線索化，Thrtif(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(overflow) if(!T)Thrt- else pre->rchild=Thrt；pre->RTag=Thread；Thrt->rchild=pre;}return編寫中序遍歷T的非遞歸算法VoidInThreading(BiThrTreeP){if(P){ //左線索if(!p->lchild){p->LTag=Thread;p-if(!pre->rchild){pre->RTag=Thread;pre-pre=p //右線索} （因?yàn)榻⒕€索時(shí)已遍歷一次，相當(dāng)于線性化了難點(diǎn)：索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直 最左下方的結(jié)點(diǎn)請(qǐng)注意中序遍歷規(guī)則是LDR，先左再根再附：中序線索二叉樹遍歷步驟（算法

先尋找中序遍歷之首結(jié)點(diǎn)（即最左下角結(jié)點(diǎn)），方法是：（無左孩子，已到最左下角）；首先p-p->data;并重復(fù)4）當(dāng)RTag=0時(shí)（表示有右孩子），此時(shí)應(yīng)當(dāng)從該結(jié)點(diǎn)的右孩算法流程

p=T-p=T- N Y

returnreturnp->RTag==1&&p-Y

以雙向線索鏈表對(duì)二叉樹遍歷T的算Status emTypee)) while(p=T) //空樹或遍歷結(jié)束時(shí)，pif(!Visit(p->data))returnERROR;//其左為空的結(jié) Visit(p->data); //后繼結(jié)p=p->rchild);}