2023年數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)之二叉樹實(shí)驗(yàn)報(bào)告題目:二叉樹的遍歷和子樹互換指導(dǎo)老師：楊政宇班級：通信1２０2姓名:徐江學(xué)號：需求分析演示程序分別用多種遍歷算法遍歷二叉樹并把數(shù)據(jù)輸出。輸入字符序列，遞歸方式建立二叉樹。3.在演示過程序中，用戶敲擊鍵盤，輸入數(shù)據(jù),即可看到數(shù)據(jù)的輸出。４.實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)的二叉樹的多種遍歷算法。遍歷算法涉及：中序遞歸遍歷算法、前序遞歸遍歷算法【選】中序遍歷非遞歸算法先序或后序遍歷非遞歸算法建立中序線索，并進(jìn)行中序遍歷和反中序遍歷5.實(shí)現(xiàn)二叉樹的按層遍歷算法６.設(shè)計(jì)一個(gè)測試用的二叉樹并創(chuàng)建相應(yīng)的內(nèi)存二叉樹，可以測試自己算法的邊界(涉及樹節(jié)點(diǎn)數(shù)為０、1以及>１的不同情形）。7.測試數(shù)據(jù):輸入數(shù)據(jù)：－+a*b-ｃd-ef概要設(shè)計(jì)說明:本程序在遞歸調(diào)用中用到了鏈表,在非遞歸調(diào)用時(shí)用到了棧。棧的抽象數(shù)據(jù)類型ADTStacｋ{數(shù)據(jù)對象：D={ai｜ai∈char,ｉ=1，2,３……..｝數(shù)據(jù)關(guān)系：R＝{<ａi-１,ａｉ>|ａi-１,aｉ∈D，ｉ=2,３…..}基本操作:IｎｉtＳtａck(&S)操作結(jié)果：構(gòu)造一個(gè)空棧ＳtackEｍpty（S)

?初始條件:棧S已存在。? 操作結(jié)果:若S為空棧,則返回OK,否則返回ＥRRＯＲ。Push(&S，e)

?初始條件:棧S已存在。

操作結(jié)果:插入元素ｅ為新的棧頂元素。

?Pｏｐ(&S，＆ｅ)

初始條件：棧S已存在且非空。?

?操作結(jié)果:刪除S的棧頂元素，并用ｅ返回其值。GｅtToｐ（S，&e)??初始條件：棧S已存在且非空。

?操作結(jié)果:用e返回S的棧頂元素。｝2.二叉樹的抽象數(shù)據(jù)類型ＡDTBinａｒyTree{ 數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。? 數(shù)據(jù)關(guān)系R：

若D＝Φ，則R=Φ,稱BinaryTreｅ為空二叉樹;?? 若D≠Φ，則R={H}，H是如下二元關(guān)系；

??（1)在D中存在惟一的稱為根的數(shù)據(jù)元素root,它在關(guān)系Ｈ下無前驅(qū)；? ?(２)若D－{root}≠Φ，則存在D-｛root}＝{D1,Dr},且Ｄ１∩Dr＝Φ；

? (3)若D1≠Φ，則D1中存在惟一的元素ｘ1，＜roｏt，x１>∈H,且存在D1上的 ??關(guān)系H1?Ｈ;若Ｄr≠Φ，則Dr中存在惟一的元素ｘr，＜rｏot，xr＞∈H,且?? ?存在上的關(guān)系Hr?Ｈ；H={<root,x1>,<root,xr＞,H1,Ｈr｝;

??（4）（Ｄ１,{H1｝)是一棵符合本定義的二叉樹，稱為根的左子樹；(Dｒ,{Hr})是一 ???棵符合本定義的二叉樹，稱為根的右子樹。?基本操作：

CrｅatｅBiTrｅe(cuò)（&T)? ?初始條件:給出二叉樹T的定義。

??操作結(jié)果：按規(guī)定構(gòu)造二叉樹T。?PrｅＯｒｄerＴrａｖeｒse_ｒe（Ｔ，ｐｒint())???初始條件：二叉樹T存在,ｐrint是二叉樹所有結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。

?操作結(jié)果:先序遞歸遍歷Ｔ，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)prｉnｔ一次且僅一次。一旦? ?? priｎt(）失敗,則操作失敗。 InＯｒderTrａversｅ(T,priｎｔ())???初始條件:二叉樹T存在,ｐrint是二叉樹所有結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。???操作結(jié)果:中序非遞歸遍歷T，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)ｐriｎt一次且僅一次。一 ? ?旦ｐrintf()失敗，則操作失敗。IｎOrderTravｅrse_re(T，ｐｒint())? 初始條件：二叉樹T在在,priｎt是二叉樹所有結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。操作結(jié)果：中序遞歸遍歷Ｔ，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一旦 ? prｉntf()失敗，則操作失敗。PreOrdｅrTraｖｅrse(T，print（))初始條件：二叉樹Ｔ存在,priｎｔ是二叉樹所有結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。

操作結(jié)果:先序非遞歸遍歷T,對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)pｒｉｎｔ一次且僅一次。一? 旦priｎｔ（）失敗，則操作失敗。Leｖｅlorｄｅr（Ｔ)初始條件:二叉樹T在在。操作結(jié)果:分層遍歷二叉樹Ｔ，并輸出。InOrdeｒThreadｉng(Thrt,T);初始條件:二叉樹T在在。操作結(jié)果:中序遍歷二叉樹，并將其中序線索化。IｎOｒdeｒTraｖerse_Ｔhr(T，priｎt);初始條件:二叉樹Ｔ在在。操作結(jié)果：中序非遞歸遍歷二叉線索樹TInThreadinｇ（ｐ）；初始條件:結(jié)點(diǎn)ｐ在在。操作結(jié)果:結(jié)點(diǎn)p及子樹線索化。3．主程序的流程:voidmain(）{?初始化; 提醒；?執(zhí)行二叉數(shù)ADＴ函數(shù);｝4．本程序包含三個(gè)模塊主程序模塊ｖoidmａin()｛初始化；{接受命令;顯示結(jié)果；｝｝鏈表模塊。遞歸調(diào)用時(shí)實(shí)現(xiàn)鏈表抽象數(shù)據(jù)類型。棧模塊。非遞歸調(diào)用時(shí)實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型。具體設(shè)計(jì)1.宏定義及全局變量#ｄefinｅTElemTyｐｅchａｒ#ｄefineSElｅmＴypeBｉTrｅe(cuò)#defineOK1#ｄefｉneOVＥＲFLOW0＃ｄｅfｉｎeERROR0#ｄｅfineSTACK_ＩＮIＴ_SIZE1０0＃ｄefineSTACＫINCＲＥMＥＮT１0SqSｔackS；BiThrTreepｒｅ;BiThrTrｅe(cuò)i；2.函數(shù)定義ｉｎtCrｅａt(yī)eBiTree(BiTrｅe(cuò)&T)；? ??? ／/創(chuàng)建二叉樹voidPreOrderＴravｅrsｅ_ｒe（ＢiTreeT，void(＊prinｔ)(TElemTypeｅ));?//先序遞歸遍歷二叉樹ｖoidＩnOrｄeｒTraveｒse（BｉＴreeT,ｉnｔ（＊priｎｔ)(TＥleｍTypｅｅ));??//中序非遞歸遍歷二叉樹ｖoidＩｎOrdｅrTraｖerｓe_ｒe(BiTrｅe(cuò)T，iｎｔ(*print)(TElｅmTｙpee)); /／中序遞歸遍歷二叉樹ｖoｉｄPｒeOrｄeｒTraｖeｒｓe(BiTreeT,inｔ（*print)(TElｅmTyｐeｅ)); //先序非遞歸遍歷二叉樹intprｉnt(TElemＴyｐee）; //打印元素voidInｉtSｔack(SqＳtack＆S）;??? //棧的初始化voｉdＰｏｐ(ＳqSｔaｃk&S,ＳＥlemＴyｐｅ&e);voｉdPｕsh(SｑSｔack＆Ｓ,SEｌeｍTyｐe&e);intＳtacｋEｍpty（SqSｔackS);iｎtGｅtTop(ＳqＳｔaｃkS，SEleｍType＆ｅ);voidLevｅlordeｒ(BiTreeT)；ｖoidＩnＯrderThreaｄing(ＢiTｈrTree&Thrt,BiTｈｒTrｅe(cuò)Ｔ)；intIｎＯｒderTraverse_Thr（BiThrTrｅe(cuò)T,int（*prｉnt)(ＴＥｌemTypee));voiｄＩｎThreaｄiｎｇ(BｉThrTreep）;3.二叉樹鏈表數(shù)據(jù)結(jié)構(gòu):tyｐeｄeｆstructBiＴNode{ ＴElｅmTｙpｅｄata；?ｓtｒucｔBiTNode*lchild,*rchiｌd;?PointｅrTaｇＬTag,RＴaｇ；}BiＴNｏde,*ＢiTree,BiTｈrNoｄｅ,*BiＴhrＴｒee;?基本操作:a)構(gòu)造二叉樹ＴiｎtCrｅaｔｅBiＴrｅｅ(BiTreｅ&T){ charcｈ； scanｆ(＂%c"，&ch);?if(cｈ＝='＇) T=NULL; ｅlｓe?{??if(！(T=(BｉTＮode*）ｍａｌloc(siｚeof(BiTNode))）) ? returnEＲROＲ;? T－>daｔａ=ch; ｉｆ(CrｅaｔeＢiＴｒee(T->lchild))Ｔ->LＴag=Liｎｋ;? if(ＣreａｔeBiＴree(T－>rchild))T->RTａｇ=Ｌinｋ;?} ｒeｔｕrｎOK;}b）先序遞歸遍歷二叉數(shù)T，并輸出所有結(jié)點(diǎn)值。vｏｉｄPreOrderＴraｖeｒse_ｒｅ(BiＴrｅe(cuò)T,int(＊priｎt)(TElemTypee)){?if（T) { if（pｒint（T->ｄａｔａ))???PｒeOrderＴrａverse＿re(T－>ｌchild,print); ＰｒeＯrdeｒTraverｓe_ｒe(T->rchｉｌd,pｒint); ?rｅｔuｒn; } ｅlｓe ?return;｝c)中序非遞歸遍歷二叉樹T，并輸出所有結(jié)點(diǎn)值voiｄInOrdeｒTraversｅ(BiTｒeｅT,ｉｎt(*prinｔ）（TElemTypｅe(cuò))){?SｑStackS;?Ｓ.base=ＮULL;S.top=NULL;?ＳEleｍＴypep=NULL；?InitSｔａｃk(Ｓ); Ｐｕｓh（S,T);?wｈiｌe（！SｔackEmpｔy(Ｓ)）?｛ whｉｌe(GetTop（Ｓ,ｐ)＆＆p)???Ｐｕｓh(S,p->ｌchild); ?Ｐop(S,p);? if(!ＳtaｃkＥmpty(S)) {? Pop(S,p)；???prｉnt（ｐ-＞ｄａｔa）;? Ｐｕsh(S,p->rcｈild); ?｝?} ｒetuｒｎ;}d)中序遞歸遍歷二叉樹T,并輸出所有結(jié)點(diǎn)值vｏｉdIｎＯrderTraverse＿re(ＢiTreｅT,int(*prｉnｔ)(TＥｌｅmTypeｅ)){iｆ(Ｔ){ＩnOrdeｒTｒaverse＿ｒe(T->ｌｃhｉlｄ,print);pｒint(T-＞daｔa）;ＩｎＯrdｅrＴｒavｅrsｅ_ｒe（T->rcｈｉｌd，print）；}}ｅ)中序遍歷二叉樹T,并將其中序線索化，Thrｔ指向頭結(jié)點(diǎn)vｏidInOrderThreading(BiＴhrTree&Ｔｈrt,BｉThrＴrｅe(cuò)T)｛?Thrt=（ＢｉThrTree)mａlloｃ（ｓiｚeof(BｉThrNode));?Ｔhrt->ＬTａg=Lｉｎk;/／建頭結(jié)點(diǎn)?Thｒt－>RTag=Threaｄ; Thｒt->rchild＝Ｔｈrｔ；//右指針回指 ｉf(!T）?Thrt->lｃhild=Thｒt; eｌse {? Ｔhrt->lchild=T;? pｒe=Tｈrt; IｎThrｅａding(T）;／／中序遍歷進(jìn)行中序線索化??pｒｅ->rchild=Ｔhrｔ； pｒｅ->RTag=Tｈread;//最后一個(gè)結(jié)點(diǎn)線索化 ?Tｈｒt->ｒchilｄ=pｒe； ｝ ｉ=Ｔhrt;}/／ＩnOrderTｈｒeadingf)結(jié)點(diǎn)ｐ線索化voidInTｈrｅａdｉｎg(ＢiＴhｒTreep）{ if(p){ ＩｎThreading(p->lchiｌｄ）;//左子樹線索化?if(!p->lchild)//建前驅(qū)線索 ?{p->LTag=Ｔhｒeａd；p－>lchilｄ=pｒｅ；}?ｉｆ(!prｅ->ｒｃｈilｄ）//建后繼線索??{pre-＞RTaｇ=Thrｅad;prｅ->rcｈild=ｐ;} ｐｒe=p;//保持pre指向p的前驅(qū)?ＩnThrｅading(ｐ－>rchild）；//右子樹線索化?} }//InThreaｄiｎgｇ)/／中序遍歷線索化二叉樹inｔＩnＯrderTraversｅ_Thr(BiＴhｒTreｅT,iｎt(*prｉnt)(TElemＴypeｅ)){?BiThrTreｅp＝NULＬ;?p＝T->lchild；?wｈile(p!=T)?{? whｉｌｅ(p->LTag==Lｉnk)? ?p＝p-＞ｌchiｌｄ; ｉf(!ｐｒiｎt（p->daｔａ）)?? rｅtｕｒｎERRＯR; ?whiｌｅ(p－＞RTag==Thｒeaｄ＆&p->rcｈiｌd!=Ｔ） {???p=ｐ－>rchｉlｄ; ? pｒｉnt（p－>data); }??p＝p->rｃhiｌｄ;?｝ returnＯK;}4．棧數(shù)據(jù)結(jié)構(gòu)：typedefsｔruｃｔ{ ?SEleｍType＊base;??SElｅｍType＊top; inｔstacｋsize；｝SｑＳｔack；基本操作:a)創(chuàng)建一個(gè)空棧voiｄInitStacｋ（SqＳｔack&S){ S.ｂase=（ＳEleｍType*)malloc（STACＫ＿INIT_SIZE*ｓizeoｆ(SElｅmTｙpe)); S.top=S．baｓｅ;??／/初始為空 S.stacksiｚｅ＝STACK＿ＩＮIT_SIZE;?retuｒｎ；｝b)棧頂插入元素voidPuｓh(SqSｔａck&S,SＥｌemＴｙpe＆e){?if(S.top－S.ｂase>=S.sｔackｓｉｚe)?{??Ｓ.base=(ＳＥlｅｍTyｐe*）reallｏc（Ｓ.bａse，(STACK_INIT_SIZE+STACKＩNＣＲEMENT)＊sizeof(ＳEleｍTyｐｅ））; ?Ｓ.top=S.ｂase+S．ｓｔａcksize；??S．stackｓize+=ＳＴACKINCREMEＮT; } *S.top+＋=ｅ；}c)棧頂刪除元素ｖｏｉdPop(SｑStack&Ｓ,SEleｍＴyｐe＆e）{?iｆ(S.toｐ=＝S.base) ?reｔｕrｎ；?e＝*－－Ｓ．top； ｒｅtuｒn；}d)判斷棧是否為空棧iｎtSｔacｋEmpty（SqＳtackS) ? ｛?if(Ｓ.tｏp=＝Ｓ.ｂase) ?returnＯK;?eｌse??rｅｔurnＥRROＲ;}e）e返回S的棧頂元素ｉntＧetToｐ(SqＳtａckＳ,SElemTyｐe&e){?iｆ（S.ｔoｐ==S.baｓe)? ｒｅturnERRＯR; e=*(S．ｔop-１); ｒｅtｕrnOK;}５.主函數(shù)voidｍaiｎ（){ｉntfｌag; BiＴreeＴ; BiThrTreeTｈrt;?ｐrintf（"***＊*＊＊******＊***＊＊*************＊***＊***************＊*\ｎ");?priｎtf("**實(shí)驗(yàn)12二叉樹的遍歷＊*\n"); pｒinｔf("＊*１.實(shí)現(xiàn)二叉樹的不同遍歷算法和二叉樹的中序線索化算法*＊\ｎ"）; printｆ("**a)中序遞歸遍歷算法；*＊\n"）; pｒintf("＊*b)先序遞歸遍歷算法;*＊\n");?prinｔf(＂*＊c)中序遍歷的非遞歸算法；**＼n"); ｐｒiｎtf（＂*＊d)先序或后序遍歷非遞歸算法之一;**＼n");?priｎtf（"**e)建立中序線運(yùn)用線索進(jìn)行中序遍歷和反中序遍歷。**\n＂);?pｒinｔf("*＊2.實(shí)現(xiàn)二叉樹的按層遍歷算法。＊*\n＂); pｒintf（"******＊＊***＊*＊＊****＊*****＊**＊＊**＊****＊＊*＊**＊*＊*****＊*＊＊**＊\ｎ＂); priｎtf("\n選擇操作：\n\ｔ1.先序與中序遍歷算法＼n\ｔ2.中序線索的中序遍歷和反中序遍歷算法\n\ｔ３.按層遍歷算法\n請選擇:"); sｃaｎｆ("%d",&ｆlａg)； switｃｈ（flag） {casｅ1:?? ???pｒintf（"前序遞歸創(chuàng)建二叉樹（空格表達(dá)此結(jié)點(diǎn)為空):\ｎ");?? getchar();? ??Creａt(yī)eBｉTrｅｅ(T)；??? priｎtf(＂中序遞歸遍歷輸出："); ??InOrｄeｒTraverse_rｅ(T，print）；????ｐrｉntf("＼n前序遞歸遍歷輸出:"）； ?? ＰrｅOrderＴraｖｅrｓe_re(T,print); ??prinｔf("\ｎ中序非遞歸遍歷輸出：");?? InＯrdeｒTrａverse（T,print); ?? ｐrinｔf("＼n前序非遞歸遍歷輸出："）；??? PreOrｄeｒTｒａverse(T,prinｔ）;??? printf（"\n")；?? bｒeak; ?ｃａse２:?pｒintf(＂前序遞歸創(chuàng)建二叉樹（空格表達(dá)此結(jié)點(diǎn)為空):\n＂); ??getchar（）；? ? CrｅaｔｅBiTrｅe(cuò)(T); ? ?pｒinｔf("＼ｎ中序遍歷線索化二叉樹：");?? InOrdeｒＴhreaｄiｎg(Thｒt,Ｔ); ?InOｒdｅrTraverｓe_Ｔhr(Thrt，print)；??? ｂreaｋ； case3:priｎｔf("前序遞歸創(chuàng)建二叉樹（空格表達(dá)此結(jié)點(diǎn)為空）:\n");??? ｇｅtｃｈar(）；?? ?CreateBiTｒee(Ｔ）；? ? ? ｐrintｆ("\ｎ按層遍歷輸出:")；??? Levelorder（T);????ｐriｎtf("\ｎ＂);????breaｋ;? ｄeｆault:rｅtｕｒn; }｝函數(shù)間調(diào)用關(guān)系mainmainInOrderTraverse_reCreateBitreePreOrderTraverse_reInOrderTraversePreOrderTraverseInOrderThreadingInOrderTraverse_ThrThreadingStack操作調(diào)試分析1、二叉樹的分層遍歷，開始時(shí)想用隊(duì)列來做，但考慮到比較麻煩，因而改為數(shù)組模擬隊(duì)列,簡樸易懂,課后可自行嘗試用隊(duì)列來做。2．

在線索化二叉樹時(shí)考慮到假如將兩種存儲(chǔ)結(jié)構(gòu)分開將導(dǎo)致兩個(gè)類型的指針不能互相傳值,導(dǎo)致許多麻煩。比較兩種存儲(chǔ)結(jié)構(gòu)發(fā)現(xiàn)，線索二叉樹比二叉樹多了兩個(gè)標(biāo)志域LTag，Rtaｇ。于是把兩種存儲(chǔ)結(jié)構(gòu)合并為BiＴhrNode,并在建立二叉樹時(shí)把ＬTag，Rtag均置為Liｎk。程序正常運(yùn)營。3．進(jìn)入演示程序BiTｒee.cｐp，完畢編譯，連接(即按下ＣtrlF5）進(jìn)入演示界面，或直接打開執(zhí)行文獻(xiàn)BiＴreｅ.exe,產(chǎn)生如下圖所示的界面：用戶需根據(jù)用戶提醒信息操作,輸入二叉樹(以空格表達(dá)空結(jié)點(diǎn)），輸入完畢后按回車鍵，屏幕上打印出相應(yīng)于該二叉樹的各種遍歷結(jié)果。如下圖:測試結(jié)果輸入：-+a＊ｂ－cｄ-ｅf屏幕輸出:中序遞歸遍歷輸出：a+b*c-d前序遞歸遍歷輸出：＋a*ｂ-cd中序非遞歸遍歷輸出:a＋b＊c-d前序非遞歸遍歷輸出：+a＊b-cd按層遍歷輸出：+a＊b-ｃd中序遍歷線索化二叉樹：ａ＋b*ｃ-ｄ附錄BiTｒee．cｐpBiＴｒee.eｘｅ#incluｄｅ<sｔdio.h>#iｎｃluｄe<ｓtdlib.h＞#defｉneＱＥlｅmTｙpeBiTNode#defiｎeTEleｍTｙpecｈaｒ#defineOK1#deｆineOVEＲFＬOW0#deｆｉneEＲROR0＃defineＳTACK_INIT＿ＳＩＺE100#ｄefineＳTACKINＣREMENT10tｙpeｄefeｎumＰointｅrＴag｛Ｌinｋ,Tｈread};?//Ｌinｋ＝=０，指針,Threａd=＝1，線索typｅdefsｔructBiTNode{ TEｌｅmTｙpedata; sｔrｕｃtBiＴNｏde*lchild,*rｃhild;?ＰoiｎterTaｇLTａg,ＲTａg;}BiＴNoｄe，*BiＴree,ＢiTｈrＮoｄｅ,*ＢiThrTree; ／/二叉樹＃deｆｉneQＥleｍTｙpeBiTNode#ｄefineSEｌemＴypeBiTreｅｔypeｄeｆsｔrｕｃt{ SElemType＊base;?ＳEleｍType*top； ｉnｔstacksｉze；}SqStａck；//全局變量ＳqStａｃkS;ＢiＴhrTｒeeprｅ;BｉＴhrTrｅe(cuò)i;/*函數(shù)聲明*/intCreatｅBiTree（ＢiTree&T);? ? ?/／創(chuàng)建二叉樹voidPreOrｄｅrTraverse_re(BiTｒeeT,ｖoid(*ｐrｉnt）(TＥleｍTyｐeｅ)); /／先序遞歸遍歷二叉樹voｉdInOｒｄｅrＴraveｒse(BiTｒeeＴ,inｔ(*ｐriｎｔ)(TＥlemTypee)); ?//中序非遞歸遍歷二叉樹voidIｎOｒdｅrTraverse_re(BｉＴｒeeＴ,inｔ(＊ｐrｉnt)（ＴEｌemTypeｅ)）; /／中序遞歸遍歷二叉樹voidPrｅOrdｅｒTｒaverse(BiTreeT,inｔ(*priｎt)（TEleｍＴypee));? //先序非遞歸遍歷二叉樹intprinｔ(TＥｌemTyｐｅe(cuò)); ?／／打印元素vｏidＩnitSｔａcｋ(SqStaｃｋ&S）;? ??／/棧的初始化vｏiｄPop(SqＳtａck&S,SEleｍTyｐe&e）;voiｄPush(SqStack&S,SEleｍType&ｅ)；ｉntSｔackＥｍpty（SqStackＳ);intGetＴoｐ(SqStａckＳ,ＳElemTypｅ＆e);voｉdＬｅvｅloｒdｅr(ＢｉTreeT)；ｖoidInOrdｅrThreａdｉｎg(BiThrTｒeｅ&Thrｔ,BiＴhｒＴrｅｅT);intIｎOrdｅrＴraverｓe_Thr(BiＴhrTｒeeT,inｔ(*pｒinｔ)(ＴＥlemＴypee));voｉdInThreadiｎg(ＢｉThrＴrｅｅｐ）;／*二叉樹的創(chuàng)建遞歸創(chuàng)建*/intCreateBiＴree(BｉTree＆T){?ｃharｃh； ｓcanf（"%c"，&ch);?ｉf(ch＝='')? T=ＮULＬ;?ｅｌｓe ｛? if（!(T=(BiＴNode*)maｌｌoｃ（ｓizeof(ＢiＴＮoｄe)))） ?ｒeturｎERＲOR；? T->data＝ch;? if(CreateBiTreｅ(T－>lｃhiｌd)）T->ＬTag＝Ｌｉｎk；??if(CｒeateＢｉTree(T->rchild))Ｔ－>RTａg＝Liｎk; }?ｒｅturnＯK；｝/****＊＊********＊*＊******＊********＊*＊＊****＊**／/＊先序遞歸遍歷輸出*／／＊＊*＊＊*＊***＊*＊***＊*＊********＊*****＊**＊***＊*＊／vｏidPｒeOrderTraversｅ_re(BiTreeT,int(＊ｐrint)(TEｌemＴyｐee)){ if（Ｔ） ｛ ?ｉf(ｐｒｉnt(T->daｔa))? ?PｒeOrｄeｒTｒａversｅ＿rｅ(T-＞lｃhild,print）；? PreOrdeｒTrａverse_re(T->rchild，priｎt);??ｒetｕrn； }?else return;}/***＊******＊****＊*＊＊＊＊***＊*＊**＊**＊*＊****＊*＊*//＊中序非遞歸遍歷輸出＊／/*＊*****＊**＊**＊＊************＊******＊*＊**＊＊**/voｉdIｎOrdｅｒＴｒavｅｒｓe(BiTreeT，ｉnｔ（＊print）(TＥlemTypee)){ SqSｔaｃkS; Ｓ.base=NＵLL;S．top＝ＮUＬL;?SElｅmTyｐep=NＵＬL;?InｉｔＳtａｃｋ(S);?Pｕsh(Ｓ,T）； whｉｌe(!StacｋEｍptｙ(Ｓ))?{??whｉle(GetTｏp(Ｓ,p)&＆p) ? Push(S,p->lchild）;??Pop(S，p）; ｉf(!StackEmｐｔy(S)）? ｛ ? Ｐop(S,ｐ);? ｐrｉnt(ｐ－>daｔa); ? Ｐｕsｈ(S,p－＞rchild); } }?return;}/**＊＊＊****＊**＊*＊**********＊***＊＊＊*****＊*****／/＊中序遞歸遍歷輸出*//＊***＊＊*＊＊***********＊＊******＊****＊*********/voidIｎOrderTｒａｖｅｒsｅ＿rｅ(BiＴreeT，iｎt(＊ｐｒiｎt)(TEｌeｍTypｅe(cuò)))｛if(T){InOrｄeｒTrａverse＿re(T->lchｉｌｄ,ｐriｎt);pｒint(Ｔ->data);ＩnＯrｄeｒTｒavｅｒse_re(Ｔ->rcｈild,prinｔ)；｝ｒeｔurn;}/*******＊*******＊****＊*******＊＊*＊****＊＊*****//*按照前序非遞歸遍歷二叉樹:棧*//*＊******＊*＊**＊*****＊**＊*****＊*******＊*＊****/vｏidPreOrｄｅrTravｅrse(BiTｒeeＴ，int(*ｐrint)（TElemＴｙｐｅｅ)）{?SqStａckS;?Ｓ.bａse=ＮULL；S.tｏp=ＮUＬL； ＳElｅｍTｙpｅp=T;／/p指向當(dāng)前訪問的結(jié)點(diǎn)InitStaｃk(Ｓ);wｈｉle(p||!StacｋEmptｙ（S)){if(ｐ)｛print(ｐ->dａｔa）；Pｕｓh(Ｓ,p);p=p->lchilｄ;}else{Pop（S，ｐ）;p=p->rcｈilｄ;}}ｒeturn;}ｖoidIｎOｒｄｅrThｒeading(ＢiThrＴreｅ&Thrｔ,BｉThrＴｒeeＴ)/／中序遍歷二叉樹T，并將其中序線索化，Ｔhrt指向頭結(jié)點(diǎn){ Ｔhrｔ=(BｉＴhrTｒee)malloc(sｉzｅof(BｉThrNｏde）)；?Thrｔ->LTag=Liｎk;//建頭結(jié)點(diǎn)?Thrt->ＲTag＝Thｒeａｄ; Thｒt－>rchild＝Tｈrt;/／右指針回指 if(!T) Ｔhrｔ-＞lchild=Thrt； ｅlｓe?｛??Tｈrt->lｃhｉld=T;? pre=Thrt;??InThｒｅadiｎｇ(T)；//中序遍歷進(jìn)行中序線索化 ?pｒe->rchild=Ｔhrｔ； pre－>RTａg＝Tｈｒeａd;//最后一個(gè)結(jié)點(diǎn)線索化 ?Tｈｒt－>ｒchilｄ=pre; } i=Thｒt；}//InOｒｄｅrＴhｒeadingvｏidＩnThreadｉｎg(BiＴｈrTreep）{if(p)｛InThreａdinｇ(p->lchild)；//左子樹線索化if(!p->lｃhilｄ）／/建前驅(qū)線索{p－>LTag=Thrｅaｄ;p->ｌｃｈｉlｄ=ｐre；}ｉｆ(?。餽e->rchｉlｄ)//建后繼線索｛pre->ＲTaｇ＝Thrｅad;pｒe->rｃhild=p;}pre=p；/／保持pre指向p的前驅(qū)InThreaｄing(p->rchilｄ);//右子樹線索化}｝/／ＩnThreadingiｎtInOｒderTｒａvｅrｓe_Tｈｒ（ＢiThrＴｒeeT，inｔ(＊print)（TＥlemTypee))／/中序遍歷線索化后的二叉樹{?ＢiThrTreep=NUＬＬ;?p＝T->lｃｈｉld； while（p!=T) { whｉlｅ（p->LTag==Lｉnk)? ?p=p->lｃhilｄ;? ｉｆ(!print（ｐ->dａt(yī)ａ）) ?rｅｔｕrnERROR; wｈｉlｅ(ｐ-＞RTag＝=Ｔhread&＆ｐ－>ｒchｉld！＝Ｔ)? {?? ｐ=p－>rchild; ? pｒｉnt（p－>dａｔa）;? } ?ｐ=p-＞rchｉld；?} rｅturnＯＫ;｝/****＊***＊＊*********＊*******以下為輔助函數(shù)******＊**************＊＊*＊＊****＊*＊＊***＊*/ｉｎtpriｎt(TElemTypee){?pｒiｎtf("%c",ｅ）; reｔurnOK；}/＊棧函數(shù)*//＊棧的初始化*/voidInitStacｋ（ＳqStａck&Ｓ）{?Ｓ.base=(SElemＴype*）mallｏc（STACＫ_INIＴ＿ＳIZE*ｓizｅoｆ（ＳElｅｍType）);?S.top＝S.ｂaｓe; ?//初始為空 Ｓ.staｃｋｓｉｚe=ＳTACK_INＩT_SIZＥ; rｅturn;}/＊棧頂插入元素*/voidPush(SqStａck&S,SElemTypｅ＆e){ ｉf(Ｓ.top-S.bａse>=S.stacｋsize)?｛ ?Ｓ.ｂase＝(SＥlｅmType*）ｒealloc（S.baｓe,(SＴＡCK＿ＩNＩT_SIZE+STＡCKＩNCＲEMENＴ）＊sizｅoｆ(SEleｍTypｅ))；? Ｓ.top=S．base+S．stackｓize;??S.sｔａcｋsize＋=SＴACKINCＲEMＥNT;?｝?*S．ｔoｐ++＝e;}/＊棧頂刪除元素*/voidPｏp(ＳqStacｋ＆Ｓ，SElｅmTｙpe&ｅ)｛?iｆ（Ｓ.ｔｏp＝＝S.ｂａｓe） rｅｔuｒn; e=*--S．top;?ｒｅturn;}inｔStaｃkEｍpty（ＳqＳtaｃkＳ)? ?／*若棧為空棧，則返回OK，否則返回EＲROR*/{ ｉf(S.top＝=S.base） ?returnOＫ;?ｅlｓe? returｎERROR;}intGeｔTop(SqSｔacｋS,ＳEｌｅmType&ｅ){ ｉf(S.toｐ=＝S.baｓe)??rｅturnＥＲROＲ;?e＝*(S.top-１); returnOK；}／*＊＊*****＊＊***＊***＊＊＊***＊＊**＊****＊*＊*******＊*＊*********＊*＊***／／*按層次順序建立一棵二叉樹＊／/**＊*＊＊*＊******＊＊*****＊********＊******＊*********＊＊***＊*＊****＊／vｏidＬevelordｅr(BiTｒｅe(cuò)T){inｔi,j;BiＴNodｅ*q[２0],*p;/*ｑ[20]用于模擬隊(duì)列,存儲(chǔ)入隊(duì)的結(jié)點(diǎn)*/p=T;ｉf(p!＝ＮＵＬL）{i=1;q［i]＝p;j=2;｝/*i為隊(duì)首位置，j為隊(duì)尾位置*／while(i!＝j(luò)){p=ｑ[i]；prｉntf("%c",ｐ->ｄata);/＊訪問隊(duì)首元素*/if(p－＞lｃｈild!=ＮＵLL）{ｑ［ｊ]=p-＞ｌchild；j++;}/*若隊(duì)首元素左鏈域不為空,則將其入隊(duì)列*/iｆ(p->rchｉld!＝ＮULＬ){ｑ[j］=ｐ-＞rchiｌd；j＋+；}/＊若隊(duì)首元素右鏈域不為空,則將其入隊(duì)列*/i+＋;／*將隊(duì)首移到下一個(gè)位置*/}}voidmain(){ iｎｔｆｌａg； BiTreeT; BiThrTｒeeThrt; priｎｔf（"*＊****＊**＊**＊＊***＊****＊******＊******＊*＊***＊*＊＊**＊*＊*******＼ｎ")；?pｒｉntf("**實(shí)驗(yàn)１2二叉樹的遍歷**\n");?prｉnｔｆ("*＊1.實(shí)現(xiàn)二叉樹的不同遍歷算法和二叉樹的中序線索化算法**\ｎ＂);?pｒinｔｆ（"*＊ａ)中序遞歸遍歷算法;*＊\n＂）; printf("**b)先序遞歸遍歷算法;