數(shù)據(jù)結(jié)構(gòu)課程設(shè)計線索二叉樹算法的實現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)設(shè)計計說說明明書書線索二叉樹算法的實現(xiàn)學(xué)生姓名學(xué)號班級成績指導(dǎo)教師計算機科學(xué)與技術(shù)系計算機科學(xué)與技術(shù)系20112011 年年 9 9 月月 9 9 日日數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計評閱書題 目線索二叉樹算法的實現(xiàn)線索二叉樹算法的實現(xiàn)學(xué)生姓名學(xué)號0918014067指導(dǎo)教師評語及成績成績： 教師簽名： 年 月 日答辯教師評語及成績成績： 教師簽名： 年 月 日教研室意見總成績： 室主任簽名： 年 月 日注: 指導(dǎo)老師成績 60%，答辯成績 40%，總成績合成后按五級制計入。課程設(shè)計任務(wù)書20112012 學(xué)年第學(xué)年第 1 學(xué)期學(xué)期專業(yè)： 計算機科學(xué)與技術(shù) 學(xué)號： 0

2、918014067 姓名： 穆聞 課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè) 計 題 目： 線索二叉樹的實現(xiàn) 完 成 期 限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周設(shè)計內(nèi)容：n 個結(jié)點的二叉鏈表中含有 n+1 個空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點在某種遍歷次序下的前趨和后繼結(jié)點的指針（這種附加的指針稱為線索）。這種加上了線索的二叉樹稱為線索二叉樹(threaded binarytree)。對一棵非線索二叉樹以某種次序遍歷使其變?yōu)橐豢镁€索二叉樹的過程稱為二叉樹的線索化。由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向結(jié)點前驅(qū)或后繼的線索，而一個結(jié)點的前

3、驅(qū)或后繼結(jié)點的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷過程中修改空指針的過程。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。運用 vc+編寫一個程序?qū)崿F(xiàn)前序線索二叉樹、中序線索二叉樹和后序線索二叉樹，其中遍歷要求用先左后右的遞歸或非遞歸算法來實現(xiàn)。要求:1） 闡述設(shè)計思想，畫出流程圖；2） 任意建立一棵二叉樹，采用前序、中序、后序三種方法線索化二叉樹；3） 說明測試方法，寫出完整的運行結(jié)果；4） 從時間、空間對算法分析；5） 較好的界面設(shè)計；6） 編寫課程設(shè)計報告。 以上要求中第一個階段的任務(wù)完成后，先將設(shè)計說明書的草稿交指導(dǎo)老師面審，審查

4、合格后方可進入后續(xù)階段的工作。設(shè)計工作結(jié)束后，經(jīng)指導(dǎo)老師驗收合格后將設(shè)計說明書打印裝訂，并進行答辯。指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期： 年 月 日摘摘 要要這是一個關(guān)于線索二叉樹的程序，該程序具有創(chuàng)建二叉樹、遍歷二叉樹、線索化二叉樹。其中，遍歷和線索化都包含了先、中、后三種序列，而且對三種序列線索化后的二叉樹也進行了遍歷。該程序采用 vc 6.0 作為軟件開發(fā)環(huán)境，采用 c 語言的各種語句和結(jié)構(gòu)實現(xiàn)二叉樹的一系列操作，并采用友好的界面向用戶提供所操作的過程和數(shù)據(jù)狀態(tài)，操作簡單，界面清晰，易于被用戶所接受。關(guān)鍵字：關(guān)鍵字：線索化；遍歷；二叉樹；先序；中序；后序目目 錄錄1 1

5、課題描述課題描述.12 2 任務(wù)分析任務(wù)分析.23 3 邏輯設(shè)計及描述邏輯設(shè)計及描述.33.1 二叉樹的存儲 .33.2 二叉樹的遍歷.43.3 二叉樹的線索化.43.4 線索化二叉樹的遍歷.73.5 主函數(shù) .104 4 程序編碼程序編碼.12總結(jié)總結(jié).21參考文獻參考文獻.221 1 1 課題描述課題描述本程序重在設(shè)計二叉樹的各種線索化實現(xiàn)，以 c 語言作為編程語言，實現(xiàn)對二叉樹的先、中、后三種序列的線索化。旨在使用戶在使用過程中能直接調(diào)用各種所需函數(shù)，以及了解二叉樹的各種線索化過程。其中各函數(shù)分別為：bithrtree createbitree()；/創(chuàng)建二叉樹;bithrtree co

6、pybitree(bithrtree &rt)/復(fù)制一棵二叉樹;void preordertraverse(bithrtree t)/先序遍歷二叉樹;void inordertraverse(bithrtree t) /中序遍歷二叉樹;void postordertraverse(bithrtree t)/后序遍歷二叉樹;bool preorderthreading(bithrtree &thrt, bithrtree t)/先序線索化二叉樹;void prethreading(bithrtree p)/先序搜索結(jié)點的建立;bool inorderthreading(bithrtree &th

7、rt, bithrtree t)/中序線索化二叉樹;void inthreading(bithrtree p)/中序搜索結(jié)點的建立;void backthreading(bithrtree p)/后序搜索結(jié)點的建立;bithrtree backorderthreading(bithrtree &rt)/后序線索化二叉樹;bithrtree parent(bithrtree &thrt,bithrtree &p)/查找結(jié)點void preordertraverse_thr(bithrtree thrt)/遍歷先序線索化二叉樹;void inordertraverse_thr(bithrtree

8、thrt)/遍歷中序線索化二叉樹;void backordertraver(bithrtree thrt)/遍歷后序線索化二叉樹;void inorder_thr_t(bithrtree thrt,bithrtree &t)/將線索化后的二叉樹還原;開發(fā)工具開發(fā)工具：c 語言運行環(huán)境運行環(huán)境：visual c+6.0。2 2 2 任務(wù)分析任務(wù)分析這是一個能對二叉樹線索化的程序，其中包括對二叉樹的先序、中序、后序線索化，最后遍歷線索化并輸出遍歷結(jié)果。其中線索化要實現(xiàn)對同一個樹的線索化，即應(yīng)具備還原線索化后二叉樹的程序，并重新對二叉樹線索化。主要的功能模塊流程圖如圖 2.1 所示。創(chuàng)建一棵二叉樹遞

9、歸先序遍歷遞歸中序遍歷遞歸后序遍歷先序線索化中序線索化后序線索化遍歷先序線索化遍歷中序線索化遍歷后序線索化圖 2.1 模塊流程圖3 3 3 邏輯設(shè)計及描述邏輯設(shè)計及描述3.13.1 二叉樹的存儲二叉樹的存儲1.1.創(chuàng)建二叉樹（ createbitree(t)）設(shè)計思想：在用戶需要創(chuàng)建二叉樹時，屏幕提醒輸入樹的各個結(jié)點，包括空結(jié)點的輸入，完成輸入后，程序自動依次讀入各個結(jié)點，以空結(jié)點作為判斷結(jié)點位置的主要依據(jù)，對每個結(jié)點申請一定的存放空間，然后依次存放各結(jié)點。設(shè)計流程如圖 3.1 所示。 beginych=#n y!(t=(bithrtree)malloc(sizeof(bithrnode)t=

10、nullreturn 0;return tcharch;t-data=ch;n 結(jié)束beginbithrtreetree;yrt=nullreturntree;!(tree=(bithrtree)malloc(sizeof(bithrnode)ytree-data=rt-data;return 0;tree=nulln結(jié)束n 圖 3.1 createbitree(t ) 創(chuàng)建二叉樹 圖 3.2 copybitree(rt) 復(fù)制一棵二叉樹2.2.復(fù)制二叉樹（copybitree(rt)）設(shè)計思想：該函數(shù)的功能主要是為了避免前后兩次的線索化混亂，其實質(zhì)是重建二叉樹以方便下一次的線索化。復(fù)制的方法

11、無外乎將各個結(jié)點拷貝至另一棵樹，因為是完全一樣的二叉樹,所以連左右標(biāo)志域也要一起復(fù)制,結(jié)點位置不能發(fā)生任何變化。設(shè)計流程如圖 3.2所示，算法如算法 3.1 所示。bithrtree copybitree(bithrtree &rt) bithrtree tree;if(rt=null) tree=null; elseif(!(tree=(bithrtree)malloc(sizeof(bithrnode) return 0;tree-data=rt-data;/復(fù)制結(jié)點4 tree-ltag=rt-ltag;tree-rtag=rt-rtag;/復(fù)制左右標(biāo)志域tree-lchild=copy

12、bitree(rt-lchild);tree-rchild=copybitree(rt-rchild);/復(fù)制左右孩子return tree;算法 3.13.23.2 二叉樹的遍歷二叉樹的遍歷1.1. 先、中、后遍歷二叉樹，因為三種遍歷方法的區(qū)別只是將輸出結(jié)點的位置調(diào)換一下就可以實現(xiàn)，所以在此只列舉先序遍歷方法的設(shè)計思想，該函數(shù)是用遞歸的方法依次遍歷根結(jié)點、左子、右子，中序遍歷則是左子、根結(jié)點、右子，后序遍歷只需將根結(jié)點的訪問放在最后面執(zhí)行即可。設(shè)計流程如圖3.3，主要算法如算法 3.2 所示。void preordertraverse(bithrtree t)/前序遍歷 if (t!=nul

13、l)printf(%c ,t-data); /*訪問根結(jié)點*/preordertraverse(t-lchild);preordertraverse(t-rchild); 算法 3.2 beginyt!=nullnprintf(%c ,t-data);preordertraverse(t-lchild)preordertraverse(t-rchild)結(jié)束 beginvoid prethreading(bithrtreep);y!tnthrt-lchild=t;thrt-lchild=thrt;prethreading(thrt)pre-rchild=thrt;pre-rtag=1;thrt

14、-rchild=pre;return 1;結(jié)束 圖 3.3 preordertraverse(t)先序遍歷二叉樹 圖 3.4 preorderthreading(thrt,t)先序線索化二叉樹3.33.3 二叉樹的線索化二叉樹的線索化1.1. 先序線索化二叉樹（preorderthreading(thrt,t)）設(shè)計思想：由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向遍歷時得到的前驅(qū)或后繼的線索，因此線索化的過程即為在遍歷過程中修改空指針5 的過程，附設(shè)一個指針 pre 始終指向剛剛訪問過的結(jié)點，若指針 p 指向當(dāng)前結(jié)點，則 pre 指向他的前驅(qū)。由此可得先序遍歷建立先序線索化的算法如算法 3

15、.3 和 3.4 所示。beginypny!p-lchildny!pre-rchildnp-lchild=pre;pre=p;pre-rchild=p;yp-ltag=0nyp-rtag=0nprethreading(p-lchile);prethreading(p-rchile);結(jié)束 beginypninthreading(p-lchild);y!p-lchildny!pre-rchildnpre=p;p-lchild=pre;pre-rchild=p;結(jié)束圖 3.5 prethreading(p)先序搜索結(jié)點的建立圖 3.6 inthreading(p)中序搜索結(jié)點的建立2 2中序搜索結(jié)

16、點的建立以及線索化如圖 36 和 37 所示;后序搜索結(jié)點的建立和線索化如圖38 和 39 所示。流程圖不再多作說明。6 beginvoidinthreading(bithrtreep);!tnthrt-lchild=t;pre=thrt;inthreading(t);pre-rchild=thrt;pre-rtag=1;thrt-rchild=pre;結(jié)束y beginypnpostthreading(p-lchild);y!p-lchildny!pre-rchildnpre=p;p-ltag=1;pre-rtag=1;結(jié)束圖 3.7 inorderthreading(thrt,t)中序線索

17、化二叉樹圖 3.8 backthreading(p)后序搜索結(jié)點的建立bool preorderthreading(bithrtree &thrt,bithrtree t)/前序線索化二叉樹 void prethreading(bithrtree p);/先序遍歷進行先序線索化 thrt = (bithrtree)malloc(sizeof(bithrnode); thrt-ltag=0; thrt-rtag=1; /創(chuàng)建頭結(jié)點 thrt-rchild=thrt;/右指針回指 if (!t) thrt-lchild=thrt; /空二叉樹 else thrt-lchild = t;pre =

18、thrt; /pre: 剛剛訪問過的結(jié)點 prethreading(t);pre-rchild=thrt; pre-rtag=1;/最后一個結(jié)點線索化 thrt-rchild=pre; return 1; 算法 3.3 void prethreading(bithrtree p) if (p) 7 if(!p-lchild) p-lchild=pre; p-ltag=1; /前驅(qū)線索 if(!pre-rchild) pre-rchild=p;pre-rtag=1;/后繼線索 pre = p;/保持 pre 指向 p 的前驅(qū) if(p-ltag=0)prethreading(p-lchild);

19、 /左子樹線索化 if(p-rtag =0)prethreading(p-rchild); /右子樹線索化 /前序建立節(jié)點的搜索化算法 3.4beginbithrtreethrt;y!(thrt=(bithrtree)malloc(sizeof(bithrnode)nthrt-ltag=0;y!rtnreturn(thrt);thrt-lchild=rt;thrt-lchild=thrt;pre=thrt;postthreading(rt);thrt-rchild=pre;beginbithrtreetemp;temp-lchild=pnytemp=temp-lchild;temp-lchil

20、d!=p&temp-rchild!=pnreturntemp;y0=temp-rtagntemp=temp-lchild;ytemp=temp-rchild;結(jié)束 圖 3.9 backorderthreading (thrt,t)后序線索化二叉樹圖 3.10 bithrtree parent(thrt,p)查找結(jié)點3.43.4 線索化二叉樹的遍歷線索化二叉樹的遍歷在程序設(shè)計中,實現(xiàn)線索化二叉樹的遍歷,實質(zhì)上就是在查找每個結(jié)點的前驅(qū)和后繼,而結(jié)點是否有前驅(qū)和后繼、他們分別是什么,就要分情況去討論。1.1.中序遍歷線索化二叉樹(inordertraverse_thr(thrt)時,結(jié)點的前驅(qū)應(yīng)是遍

21、歷左子樹時訪問的第一個結(jié)點,既左子樹最左下方的結(jié)點,結(jié)點的后繼應(yīng)是遍歷右子樹時訪問的第8 beginbithrtreep;p!=thrtnprintf(%c,p-data);p-ltag=0n(p-rtag=1)&(p-rchild!=thrt)nyp-ltag=0np=p-lchild;p=p-rchild;p=p-rchild;yyyp=p-lchild;結(jié)束 beginbithrtreep;p!=thrtnp-ltag=0nprintf(%c,p-data);(p-rtag=1)&(p-rchild!=thrt)np=p-rchild;p=p-rchild;yyp=p-lchild;y結(jié)

22、束 圖 3.11 preordertraverse_thr(thrt)遍歷先序線索化二叉樹圖 3.12 inordertraverse_thr(thrt)遍歷中序線索化二叉樹一個結(jié)點,既右子樹最左下方的結(jié)點。二叉樹最左下方的結(jié)點沒有前驅(qū)，最右下方的結(jié)點沒有后繼。設(shè)計該函數(shù)的流程如圖 3.12 所示。2.2.在后序線索樹(postordertraverse_thr(thrt)中找結(jié)點后繼比較復(fù)雜，分三種情況（1）根結(jié)點沒有后繼；（2）若結(jié)點是其雙親的右孩子或是其雙親的左孩子且其雙親沒有右子樹，則后繼為雙親；（3）若結(jié)點是其雙親的左孩子且其雙親有右子樹，則后繼為其雙親的右子樹上按后序遍歷訪問的第一

23、個結(jié)點。設(shè)計該函數(shù)的流程如圖 313 所示。3.3.還原線索化二叉樹(inorder_thr_t(thrt,t):涉及該函數(shù)的主要目的是在每次線索后9 beginbithrtreep;1np!=thrtn0=p-ltagny0=p-rtagnyprintf(%c,p-data);break;ythrt=parprintf(%cn,p-data);p=par-rchild|1=par-rtagpar-rtag=0p=par;par=par-rchild;par-ltag=0par=par-lchild;p=p-lchildp=p-rchildp=thrtp=paryyynnnyy結(jié)束n圖 3.1

24、3 backordertraverse_thr(thrt) 遍歷后序線索化二叉樹10 都能清除掉前一次線索化過程中所留下的指針,因為不通順序的線索化,其修改的空指針也不同,因此,進行下一次線索化前,必須還原空指針。此函數(shù)的流程如圖 3.14 所示。beginbithrtreep,post;p!=thrtnp=thrt-rchild;p-ltag=0np-ltag=0;(p-rtag=1)&(p-rchild!=thrt)np=p-rchild;p-rtag=0;yp=p-lchild;yy結(jié)束 beginintc;c3ynreturnc;printf(n請選擇需要執(zhí)行的操作序列號:);結(jié)束 圖

25、 3.14 inorder_thr_t (thrt,t)還原線索化后的二叉樹圖 3.15 menu_select()控制選擇菜單3.53.5 主函數(shù)主函數(shù)1.1.主函數(shù)的設(shè)計流程如圖 3.17 所示,在進行所需操作之前,屏幕會提示用戶建立一棵二叉樹,然后用空的 for 循環(huán)來控制不同操作之間的循環(huán),用戶選擇序號 1,程序會自動執(zhí)行二叉樹的三種遍歷,并輸出遍歷結(jié)果;用戶選擇 2,程序會自動執(zhí)行二叉樹的線索化操作,并打印出三種線索化后的結(jié)果。操作十11 分方便。beginbithrtreet,thrt,t;打印操作菜單nchoice=menu_select();choice=1n ynchoice

26、=2choice=3break;ybreak;printf(n已結(jié)束!謝謝使用!n);y后序postordertraverse(t);前序preordertraverse(t);中序inordertraverse(t);前序preorderthreading(thrt,t);還原inorder_thr_t(thrt,t);中序inorderthreading(thrt,t);后序backordertraver(thrt); 建立后序thrt=backorderthreading(t); 遍歷線索化二叉樹遍歷二叉樹結(jié)束圖 3.17 main()主函數(shù)12 4 4 程序編碼程序編碼/-有關(guān)定義-#

27、include #include #include #include typedef struct bithrnode /線索二叉樹中結(jié)點的定義 char data; int ltag,rtag; struct bithrnode *lchild,*rchild;bithrnode,*bithrtree;/-構(gòu)建二叉樹-bithrtree createbitree() char ch;bithrtree t; scanf(%c,&ch); /從鍵盤輸入 ch； if(ch=#) t=null; /如果 ch=#,則 t 為空指針elseif(!(t=(bithrtree)malloc(size

28、of(bithrnode) return 0;t-data=ch;t-ltag=0;t-rtag=0; /線索標(biāo)志賦初值 0t-lchild=createbitree();/先序建立 t-lchild;t-rchild=createbitree();/先序建立 t-rchild; return t; /返回樹結(jié)點頭指針 bithrtree copybitree(bithrtree &rt)/復(fù)制一棵二叉樹bithrtree tree;if(rt=null) tree=null;elseif(!(tree=(bithrtree)malloc(sizeof(bithrnode) return 0;

29、tree-data=rt-data;tree-ltag=rt-ltag;tree-rtag=rt-rtag;tree-lchild=copybitree(rt-lchild);tree-rchild=copybitree(rt-rchild); return tree; /-遞歸遍歷二叉樹-void preordertraverse(bithrtree t)/先序遍歷13 if (t!=null) printf(%c ,t-data); /*訪問根結(jié)點*/ preordertraverse(t-lchild); preordertraverse(t-rchild);void inordertr

30、averse(bithrtree t) /中序遍歷 if (t!=null) inordertraverse(t-lchild); printf(%c ,t-data); /*訪問根結(jié)點*/ inordertraverse(t-rchild);void postordertraverse(bithrtree t) /后序遍歷 if (t!=null) postordertraverse(t-lchild); postordertraverse(t-rchild); printf(%c ,t-data); /*訪問根結(jié)點*/ /-線索化二叉樹-bithrtree pre; /全局變量,剛剛訪問過

31、的結(jié)點bool preorderthreading(bithrtree &thrt,bithrtree t)/先序線索二叉樹 void prethreading(bithrtree p) ; thrt = (bithrtree)malloc(sizeof(bithrnode); /創(chuàng)建頭結(jié)點 thrt-ltag=0; thrt-rtag=1; thrt-rchild=thrt; if (!t) thrt-lchild=thrt; /空二叉樹 else thrt-lchild = t; pre = thrt; /pre: 剛剛訪問過的結(jié)點； prethreading(t); pre-rchild

32、=thrt; pre-rtag=1; thrt-rchild=pre; return 1; void prethreading(bithrtree p) if (p) if (!p-lchild) p-lchild=pre;p-ltag=1; /前驅(qū)線索 if (!pre-rchild) pre-rchild=p;pre-rtag=1; /后繼線索 pre = p; if(p-ltag=0) prethreading(p-lchild); /左子樹線索化 if(p-rtag =0) prethreading(p-rchild); /右子樹線索化 /先序建立節(jié)點的搜索化bool inordert

33、hreading(bithrtree &thrt, bithrtree t)/中序線索二叉樹 void inthreading(bithrtree p) ; thrt = (bithrtree)malloc(sizeof(bithrnode); /創(chuàng)建頭結(jié)點 thrt-ltag=0; thrt-rtag=1; thrt-rchild=thrt;14 if (!t) thrt-lchild=thrt; /空二叉樹 else thrt-lchild = t; pre = thrt; /pre: 剛剛訪問過的結(jié)點； inthreading(t); pre-rchild=thrt; pre-rtag=

34、1; thrt-rchild=pre; return 1; void inthreading(bithrtree p) if (p) inthreading(p-lchild); /左子樹線索化 if (!p-lchild)/前驅(qū)線索 p-lchild=pre; p-ltag=1; if (!pre-rchild)/后繼線索 pre-rchild=p;pre-rtag=1; pre = p; inthreading(p-rchild); /右子樹線索化void backthreading(bithrtree p) if(p) backthreading(p-lchild); backthrea

35、ding(p-rchild); if(!p-lchild) p-ltag=1;p-lchild=pre; /前驅(qū)線索 if(!pre-rchild) pre-rtag=1;pre-rchild=p;/后繼線索 pre=p; /后序搜索化節(jié)點的建立bithrtree backorderthreading(bithrtree &rt) bithrtree thrt; if(!(thrt = (bithrtree) malloc (sizeof(bithrnode) exit(1);thrt-ltag= 0;thrt-rtag=1;/建頭結(jié)點thrt-rchild=thrt;/右指針回指 if(!r

36、t) thrt-lchild=thrt; /若二叉樹空，則左指針回指 else thrt-lchild=rt; pre=thrt; backthreading(rt); /后序遍歷進行后序線索化 thrt-rchild=pre; /最后一個節(jié)點處理 return thrt;bithrtree parent(bithrtree &thrt,bithrtree &p) bithrtree temp; temp=thrt; if(temp-lchild=p) return temp;/父節(jié)點是頭結(jié)點 else temp=temp-lchild; while( temp-lchild!=p & tem

37、p-rchild!=p ) if(0=temp-rtag) temp=temp-rchild;/結(jié)點有右結(jié)點，往右 else temp=temp-lchild; /如果結(jié)點沒有右孩子，去左孩子，沒有左孩子，去前驅(qū) 15 return temp; /-遍歷線索化二叉樹-void preordertraverse_thr(bithrtree thrt)/thrt:頭結(jié)點/遍歷先序線索化二叉樹bithrtree p; p=thrt-lchild; while(p!=thrt)printf(%c,p-data);/此樹不空 while(p-ltag = 0) p=p-lchild; printf(%c

38、,p-data); while(p-rtag=1)&(p-rchild!=thrt) p = p-rchild; printf(%c,p-data); if(p-ltag=0) p=p-lchild; else p=p-rchild; /void inordertraverse_thr(bithrtree thrt)/thrt:頭結(jié)點/遍歷中序線索化二叉樹bithrtree p; p=thrt-lchild; while(p!=thrt)while(p-ltag = 0) p=p-lchild;printf(%c,p-data); while(p-rtag=1)&(p-rchild!=thrt

39、) p = p-rchild; printf(%cn%c,p-data,p-data); p = p-rchild; /void backordertraver(bithrtree thrt) bithrtree p; bithrtree par; p=thrt-lchild; while(1) while(0=p-ltag) p=p-lchild; if(0=p-rtag) p=p-rchild; /p 指向第一個被訪問的結(jié)點 else break; while(p!=thrt) printf(%c,p-data); par=parent(thrt,p);/parent 是 p 的雙親: i

40、f(thrt=par) p=thrt;/若 parent 是 thrt，即 p 是根結(jié)點，則無后繼 else if(p=par-rchild|1=par-rtag) p=par; /若 p 是雙親的右孩子，或者是獨生左孩子，則后繼為雙親 else while(par-rtag=0) /若 p 是有兄弟的左孩子，則后繼為雙親的右子樹上后序遍歷訪問的第一個節(jié)點。 par=par-rchild; while(par-ltag=0) par=par-lchild; p=par; printf(%cn,p-data); 16 /-將線索化后二叉樹還原-void inorder_thr_t(bithrtr

41、ee thrt,bithrtree &t)bithrtree p,post; p=thrt-lchild; while(p!=thrt)while(p-ltag = 0) p=p-lchild; p-ltag=0; p-lchild=null; while(p-rtag=1)&(p-rchild!=thrt) p-rtag=0; post=p-rchild; p-rchild=null; p=post;p = p-rchild; p=thrt-rchild; p-rtag=0; p-rchild=null; t=thrt-lchild;free(thrt);/-選擇菜單-int menu_se

42、lect()int c;doprintf(n 請選擇需要執(zhí)行的操作序列號:); scanf(%d,&c);while(c3);return c; /-主函數(shù)-void main()int choice; bithrtree t,thrt,t; /定義樹 printf(請輸入樹的結(jié)點(#表示結(jié)點為空):n); t=createbitree(); /先序算法建立二叉樹t=copybitree(t); printf(n); /復(fù)制一顆二叉樹printf( 操作菜單 n);printf( n);printf( 1.遍歷操作二叉樹 n);printf( n);printf( 2.線索化二叉樹 n);pr

43、intf( n);printf( 3.退出所有操作 n);printf( n);for(;)choice=menu_select();switch(choice)case 1:printf(n *遍歷二叉樹*n); printf(n 遍歷二叉樹結(jié)果:n);17 preordertraverse(t); printf(n); printf(n 遍歷二叉樹結(jié)果:n); inordertraverse(t); printf(n); printf(n 遍歷二叉樹結(jié)果:n); postordertraverse(t); printf(nn);break;case 2:printf(n *線索二叉樹*n); inorderthreading(thrt,t);/中序線索化 printf(n 線索