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

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

2、2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周設(shè)計(jì)內(nèi)容：n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針（這種附加的指針?lè)Q為線(xiàn)索）。這種加上了線(xiàn)索的二叉樹(shù)稱(chēng)為線(xiàn)索二叉樹(shù)(ThreadedBinaryTree)。對(duì)一棵非線(xiàn)索 HYPERLINK :/ hudong /wiki/%E4%BA%8C%E5%8F%89%E6%A0%91 o 二叉樹(shù) t _blank 二叉樹(shù)以某種次序遍歷使其變?yōu)橐豢镁€(xiàn)索二叉樹(shù)的過(guò)程稱(chēng)為二叉樹(shù)的線(xiàn)索化。由于線(xiàn)索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向結(jié)點(diǎn)前驅(qū)或后繼的線(xiàn)索，而一個(gè)

3、 HYPERLINK :/ hudong /wiki/%E7%BB%93%E7%82%B9 o 結(jié)點(diǎn) t _blank 結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)的信息只有在遍歷時(shí)才能得到，因此線(xiàn)索化的過(guò)程即為在遍歷過(guò)程中修改空指針的過(guò)程。根據(jù)線(xiàn)索性質(zhì)的不同，線(xiàn)索二叉樹(shù)可分為前序線(xiàn)索二叉樹(shù)、中序線(xiàn)索二叉樹(shù)和后序線(xiàn)索二叉樹(shù)三種。運(yùn)用VC+編寫(xiě)一個(gè)程序?qū)崿F(xiàn)前序線(xiàn)索二叉樹(shù)、中序線(xiàn)索二叉樹(shù)和后序線(xiàn)索二叉樹(shù)，其中遍歷要求用先左后右的遞歸或非遞歸算法來(lái)實(shí)現(xiàn)。要求:闡述設(shè)計(jì)思想，畫(huà)出流程圖；任意建立一棵二叉樹(shù)，采用前序、中序、后序三種方法線(xiàn)索化二叉樹(shù)；說(shuō)明測(cè)試方法，寫(xiě)出完整的運(yùn)行結(jié)果；從時(shí)間、空間對(duì)算法分析；較好的界面設(shè)計(jì)；編寫(xiě)

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

5、接受。關(guān)鍵字：線(xiàn)索化；遍歷；二叉樹(shù)；先序；中序；后序目 錄TOC o 1-3 h u HYPERLINK l _Toc3720 1 課題描述 PAGEREF _Toc3720 1 HYPERLINK l _Toc32633 2 任務(wù)分析 PAGEREF _Toc32633 2 HYPERLINK l _Toc966 3 邏輯設(shè)計(jì)及描述 PAGEREF _Toc966 3 HYPERLINK l _Toc18996 PAGEREF _Toc18996 3 HYPERLINK l _Toc13020 3.2 二叉樹(shù)的遍歷 PAGEREF _Toc13020 4 HYPERLINK l _Toc25

6、406 3.3 二叉樹(shù)的線(xiàn)索化 PAGEREF _Toc25406 4 HYPERLINK l _Toc30840 3.4 線(xiàn)索化二叉樹(shù)的遍歷 PAGEREF _Toc30840 7 HYPERLINK l _Toc21848 3.5 主函數(shù) PAGEREF _Toc21848 10 HYPERLINK l _Toc31226 4 程序編碼 PAGEREF _Toc31226 12 HYPERLINK l _Toc26496 總結(jié) PAGEREF _Toc26496 21 HYPERLINK l _Toc9500 參考文獻(xiàn) PAGEREF _Toc9500 221 課題描述本程序重在設(shè)計(jì)二叉樹(shù)

7、的各種線(xiàn)索化實(shí)現(xiàn)，以C語(yǔ)言作為編程語(yǔ)言，實(shí)現(xiàn)對(duì)二叉樹(shù)的先、中、后三種序列的線(xiàn)索化。旨在使用戶(hù)在使用過(guò)程中能直接調(diào)用各種所需函數(shù)，以及了解二叉樹(shù)的各種線(xiàn)索化過(guò)程。其中各函數(shù)分別為：BiThrTree CreateBiTree()；/創(chuàng)建二叉樹(shù);BiThrTree CopyBiTree(BiThrTree &rt)/復(fù)制一棵二叉樹(shù);void PreOrderTraverse(BiThrTree T)/先序遍歷二叉樹(shù);void InOrderTraverse(BiThrTree T) /中序遍歷二叉樹(shù);void PostOrderTraverse(BiThrTree T)/后序遍歷二叉樹(shù);bool

8、PreOrderThreading(BiThrTree &Thrt, BiThrTree T)/先序線(xiàn)索化二叉樹(shù);void PreThreading(BiThrTree p)/先序搜索結(jié)點(diǎn)的建立;bool InOrderThreading(BiThrTree &Thrt, BiThrTree T)/中序線(xiàn)索化二叉樹(shù);void InThreading(BiThrTree p)/中序搜索結(jié)點(diǎn)的建立;void backThreading(BiThrTree p)/后序搜索結(jié)點(diǎn)的建立;BiThrTree backorderThreading(BiThrTree &rt)/后序線(xiàn)索化二叉樹(shù);BiThrT

9、ree parent(BiThrTree &thrt,BiThrTree &p)/查找結(jié)點(diǎn)void PreOrderTraverse_Thr(BiThrTree Thrt)/遍歷先序線(xiàn)索化二叉樹(shù);void InOrderTraverse_Thr(BiThrTree Thrt)/遍歷中序線(xiàn)索化二叉樹(shù);void backorderTraver(BiThrTree Thrt)/遍歷后序線(xiàn)索化二叉樹(shù);void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T)/將線(xiàn)索化后的二叉樹(shù)還原;開(kāi)發(fā)工具：C語(yǔ)言運(yùn)行環(huán)境：Visual c+。2 任務(wù)分析這是一個(gè)能對(duì)二叉樹(shù)線(xiàn)索化的

10、程序，其中包括對(duì)二叉樹(shù)的先序、中序、后序線(xiàn)索化，最后遍歷線(xiàn)索化并輸出遍歷結(jié)果。其中線(xiàn)索化要實(shí)現(xiàn)對(duì)同一個(gè)樹(shù)的線(xiàn)索化，即應(yīng)具備還原線(xiàn)索化后二叉樹(shù)的程序，并重新對(duì)二叉樹(shù)線(xiàn)索化。主要的功能模塊流程圖如圖2.1所示。圖 2.1 模塊流程圖3 邏輯設(shè)計(jì)及描述1.創(chuàng)建二叉樹(shù)（ CreateBiTree(T)）設(shè)計(jì)思想：在用戶(hù)需要?jiǎng)?chuàng)建二叉樹(shù)時(shí)，屏幕提醒輸入樹(shù)的各個(gè)結(jié)點(diǎn)，包括空結(jié)點(diǎn)的輸入，完成輸入后，程序自動(dòng)依次讀入各個(gè)結(jié)點(diǎn)，以空結(jié)點(diǎn)作為判斷結(jié)點(diǎn)位置的主要依據(jù)，對(duì)每個(gè)結(jié)點(diǎn)申請(qǐng)一定的存放空間，然后依次存放各結(jié)點(diǎn)。設(shè)計(jì)流程如圖3.1所示。 圖 3.1 CreateBiTree(T ) 創(chuàng)建二叉樹(shù) 圖 3.2 Cop

11、yBiTree(rt) 復(fù)制一棵二叉樹(shù)2.復(fù)制二叉樹(shù)（CopyBiTree(rt)）設(shè)計(jì)思想：該函數(shù)的功能主要是為了避免前后兩次的線(xiàn)索化混亂，其實(shí)質(zhì)是重建二叉樹(shù)以方便下一次的線(xiàn)索化。復(fù)制的方法無(wú)外乎將各個(gè)結(jié)點(diǎn)拷貝至另一棵樹(shù)，因?yàn)槭峭耆粯拥亩鏄?shù),所以連左右標(biāo)志域也要一起復(fù)制,結(jié)點(diǎn)位置不能發(fā)生任何變化。設(shè)計(jì)流程如圖3.2所示，算法如算法3.1所示。BiThrTree CopyBiTree(BiThrTree &rt) BiThrTree tree;if(rt=NULL) tree=NULL; elseif(!(tree=(BiThrTree)malloc(sizeof(BiThrNode) r

12、eturn 0;tree-data=rt-data;/復(fù)制結(jié)點(diǎn)tree-LTag=rt-LTag;tree-RTag=rt-RTag;/復(fù)制左右標(biāo)志域tree-lchild=CopyBiTree(rt-lchild);tree-rchild=CopyBiTree(rt-rchild);/復(fù)制左右孩子return tree;3.2 二叉樹(shù)的遍歷1. 先、中、后遍歷二叉樹(shù)，因?yàn)槿N遍歷方法的區(qū)別只是將輸出結(jié)點(diǎn)的位置調(diào)換一下就可以實(shí)現(xiàn)，所以在此只列舉先序遍歷方法的設(shè)計(jì)思想，該函數(shù)是用遞歸的方法依次遍歷根結(jié)點(diǎn)、左子、右子，中序遍歷則是左子、根結(jié)點(diǎn)、右子，后序遍歷只需將根結(jié)點(diǎn)的訪(fǎng)問(wèn)放在最后面執(zhí)行即可。設(shè)

13、計(jì)流程如圖3.3，主要算法如算法3.2所示。void PreOrderTraverse(BiThrTree T)/前序遍歷 if (T!=NULL)printf(%c ,T-data); /*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); 圖 PreOrderTraverse(T)先序遍歷二叉樹(shù) 圖3.4 PreOrderThreading(Thrt,T)先序線(xiàn)索化二叉樹(shù)3.3 二叉樹(shù)的線(xiàn)索化1. 先序線(xiàn)索化二叉樹(shù)（PreOrderThreading(Thrt,T)）設(shè)計(jì)思想：由于線(xiàn)索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為

14、指向遍歷時(shí)得到的前驅(qū)或后繼的線(xiàn)索，因此線(xiàn)索化的過(guò)程即為在遍歷過(guò)程中修改空指針的過(guò)程，附設(shè)一個(gè)指針pre始終指向剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)，若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向他的前驅(qū)。由此可得先序遍歷建立先序線(xiàn)索化的算法如算法3.3和3.4所示。 圖 3.5 PreThreading(p)先序搜索結(jié)點(diǎn)的建立圖3.6 InThreading(p)中序搜索結(jié)點(diǎn)的建立2中序搜索結(jié)點(diǎn)的建立以及線(xiàn)索化如圖36和37所示;后序搜索結(jié)點(diǎn)的建立和線(xiàn)索化如圖38和39所示。流程圖不再多作說(shuō)明。 圖 3.7 InOrderThreading(Thrt,T)中序線(xiàn)索化二叉樹(shù)圖 backThreading(p)后序搜索結(jié)點(diǎn)的建立

15、bool PreOrderThreading(BiThrTree &Thrt,BiThrTree T)/前序線(xiàn)索化二叉樹(shù) void PreThreading(BiThrTree p);/先序遍歷進(jìn)行先序線(xiàn)索化 Thrt = (BiThrTree)malloc(sizeof(BiThrNode); Thrt-LTag=0; Thrt-RTag=1; /創(chuàng)建頭結(jié)點(diǎn) Thrt-rchild=Thrt;/右指針回指 if (!T) Thrt-lchild=Thrt; /空二叉樹(shù) else Thrt-lchild = T;pre = Thrt; /pre: 剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn) PreThreading(T

16、);pre-rchild=Thrt; pre-RTag=1;/最后一個(gè)結(jié)點(diǎn)線(xiàn)索化 Thrt-rchild=pre; return 1; 算法3.3 void PreThreading(BiThrTree p) if (p) if(!p-lchild) p-lchild=pre; p-LTag=1; /前驅(qū)線(xiàn)索 if(!pre-rchild) pre-rchild=p;pre-RTag=1;/后繼線(xiàn)索 pre = p;/保持pre指向p的前驅(qū) if(p-LTag=0)PreThreading(p-lchild); /左子樹(shù)線(xiàn)索化 if(p-RTag =0)PreThreading(p-rchil

17、d); /右子樹(shù)線(xiàn)索化 /前序建立節(jié)點(diǎn)的搜索化 圖3.9 backOrderThreading (Thrt,T)后序線(xiàn)索化二叉樹(shù)0 BiThrTree parent(thrt,p)查找結(jié)點(diǎn)3.4 線(xiàn)索化二叉樹(shù)的遍歷在程序設(shè)計(jì)中,實(shí)現(xiàn)線(xiàn)索化二叉樹(shù)的遍歷,實(shí)質(zhì)上就是在查找每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼,而結(jié)點(diǎn)是否有前驅(qū)和后繼、他們分別是什么,就要分情況去討論。1.中序遍歷線(xiàn)索化二叉樹(shù)(InOrderTraverse_Thr(Thrt)時(shí),結(jié)點(diǎn)的前驅(qū)應(yīng)是遍歷左子樹(shù)時(shí)訪(fǎng)問(wèn)的第一個(gè)結(jié)點(diǎn),既左子樹(shù)最左下方的結(jié)點(diǎn),結(jié)點(diǎn)的后繼應(yīng)是遍歷右子樹(shù)時(shí)訪(fǎng)問(wèn)的第 圖 3.11 PreOrderTraverse_Thr(Thrt)遍

18、歷先序線(xiàn)索化二叉樹(shù)圖 3.12 InOrderTraverse_Thr(Thrt)遍歷中序線(xiàn)索化二叉樹(shù)一個(gè)結(jié)點(diǎn),既右子樹(shù)最左下方的結(jié)點(diǎn)。二叉樹(shù)最左下方的結(jié)點(diǎn)沒(méi)有前驅(qū)，最右下方的結(jié)點(diǎn)沒(méi)有后繼。設(shè)計(jì)該函數(shù)的流程如圖所示。2.在后序線(xiàn)索樹(shù)(PostOrderTraverse_Thr(Thrt)中找結(jié)點(diǎn)后繼比較復(fù)雜，分三種情況（1）根結(jié)點(diǎn)沒(méi)有后繼；（2）若結(jié)點(diǎn)是其雙親的右孩子或是其雙親的左孩子且其雙親沒(méi)有右子樹(shù)，則后繼為雙親；（3）若結(jié)點(diǎn)是其雙親的左孩子且其雙親有右子樹(shù)，則后繼為其雙親的右子樹(shù)上按后序遍歷訪(fǎng)問(wèn)的第一個(gè)結(jié)點(diǎn)。設(shè)計(jì)該函數(shù)的流程如圖313所示。3.還原線(xiàn)索化二叉樹(shù)(InOrder_Thr_T

19、(Thrt,T):涉及該函數(shù)的主要目的是在每次線(xiàn)索后圖 3.13 backOrderTraverse_Thr(Thrt) 遍歷后序線(xiàn)索化二叉樹(shù)都能清除掉前一次線(xiàn)索化過(guò)程中所留下的指針,因?yàn)椴煌樞虻木€(xiàn)索化,其修改的空指針也不同,因此,進(jìn)行下一次線(xiàn)索化前,必須還原空指針。此函數(shù)的流程如圖所示。 圖 InOrder_Thr_T (Thrt,T)還原線(xiàn)索化后的二叉樹(shù) menu_select()控制選擇菜單3.5 主函數(shù)1.主函數(shù)的設(shè)計(jì)流程如圖3.17所示,在進(jìn)行所需操作之前,屏幕會(huì)提示用戶(hù)建立一棵二叉樹(shù),然后用空的for循環(huán)來(lái)控制不同操作之間的循環(huán),用戶(hù)選擇序號(hào)1,程序會(huì)自動(dòng)執(zhí)行二叉樹(shù)的三種遍歷,并

20、輸出遍歷結(jié)果;用戶(hù)選擇2,程序會(huì)自動(dòng)執(zhí)行二叉樹(shù)的線(xiàn)索化操作,并打印出三種線(xiàn)索化后的結(jié)果。操作十分方便。圖3.17 main()主函數(shù)4 程序編碼/有關(guān)定義#include #include #include #include typedef struct BiThrNode /線(xiàn)索二叉樹(shù)中結(jié)點(diǎn)的定義 char data; int LTag,RTag; struct BiThrNode *lchild,*rchild;BiThrNode,*BiThrTree;/構(gòu)建二叉樹(shù)BiThrTree CreateBiTree() char ch;BiThrTree T; scanf(%c,&ch); /從

21、鍵盤(pán)輸入ch； if(ch=#) T=NULL; /如果ch=#,則T為空指針elseif(!(T=(BiThrTree)malloc(sizeof(BiThrNode) return 0;T-data=ch;T-LTag=0;T-RTag=0; /線(xiàn)索標(biāo)志賦初值0T-lchild=CreateBiTree();/先序建立T-lchild;T-rchild=CreateBiTree();/先序建立T-rchild; return T; /返回樹(shù)結(jié)點(diǎn)頭指針 BiThrTree CopyBiTree(BiThrTree &rt)/復(fù)制一棵二叉樹(shù)BiThrTree tree;if(rt=NULL)

22、tree=NULL;elseif(!(tree=(BiThrTree)malloc(sizeof(BiThrNode) return 0;tree-data=rt-data;tree-LTag=rt-LTag;tree-RTag=rt-RTag;tree-lchild=CopyBiTree(rt-lchild);tree-rchild=CopyBiTree(rt-rchild); return tree; /遞歸遍歷二叉樹(shù)void PreOrderTraverse(BiThrTree T)/先序遍歷 if (T!=NULL) printf(%c ,T-data); /*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ PreO

23、rderTraverse(T-lchild); PreOrderTraverse(T-rchild);void InOrderTraverse(BiThrTree T) /中序遍歷 if (T!=NULL) InOrderTraverse(T-lchild); printf(%c ,T-data); /*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ InOrderTraverse(T-rchild);void PostOrderTraverse(BiThrTree T) /后序遍歷 if (T!=NULL) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild);

24、printf(%c ,T-data); /*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/ /線(xiàn)索化二叉樹(shù)BiThrTree pre; /全局變量,剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)bool PreOrderThreading(BiThrTree &Thrt,BiThrTree T)/先序線(xiàn)索二叉樹(shù) void PreThreading(BiThrTree p) ; Thrt = (BiThrTree)malloc(sizeof(BiThrNode); /創(chuàng)建頭結(jié)點(diǎn) Thrt-LTag=0; Thrt-RTag=1; Thrt-rchild=Thrt; if (!T) Thrt-lchild=Thrt; /空二叉樹(shù) else Thrt-lchi

25、ld = T; pre = Thrt; /pre: 剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)； PreThreading(T); pre-rchild=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ū)線(xiàn)索 if (!pre-rchild) pre-rchild=p;pre-RTag=1; /后繼線(xiàn)索 pre = p; if(p-LTag=0) PreThreading(p-lchild); /左子樹(shù)線(xiàn)索化 if(p-RT

26、ag =0) PreThreading(p-rchild); /右子樹(shù)線(xiàn)索化 /先序建立節(jié)點(diǎn)的搜索化bool InOrderThreading(BiThrTree &Thrt, BiThrTree T)/中序線(xiàn)索二叉樹(shù) void InThreading(BiThrTree p) ; Thrt = (BiThrTree)malloc(sizeof(BiThrNode); /創(chuàng)建頭結(jié)點(diǎn) Thrt-LTag=0; Thrt-RTag=1; Thrt-rchild=Thrt; if (!T) Thrt-lchild=Thrt; /空二叉樹(shù) else Thrt-lchild = T; pre = Thr

27、t; /pre: 剛剛訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)； InThreading(T); pre-rchild=Thrt; pre-RTag=1; Thrt-rchild=pre; return 1; void InThreading(BiThrTree p) if (p) InThreading(p-lchild); /左子樹(shù)線(xiàn)索化 if (!p-lchild)/前驅(qū)線(xiàn)索 p-lchild=pre; p-LTag=1; if (!pre-rchild)/后繼線(xiàn)索 pre-rchild=p;pre-RTag=1; pre = p; InThreading(p-rchild); /右子樹(shù)線(xiàn)索化void backTh

28、reading(BiThrTree p) if(p) backThreading(p-lchild); backThreading(p-rchild); if(!p-lchild) p-LTag=1;p-lchild=pre; /前驅(qū)線(xiàn)索 if(!pre-rchild) pre-RTag=1;pre-rchild=p;/后繼線(xiàn)索 pre=p; /后序搜索化節(jié)點(diǎn)的建立BiThrTree backorderThreading(BiThrTree &rt) BiThrTree thrt; if(!(thrt = (BiThrTree) malloc (sizeof(BiThrNode) exit(1

29、);thrt-LTag= 0;thrt-RTag=1;/建頭結(jié)點(diǎn)thrt-rchild=thrt;/右指針回指 if(!rt) thrt-lchild=thrt; /若二叉樹(shù)空，則左指針回指 else thrt-lchild=rt; pre=thrt; backThreading(rt); /后序遍歷進(jìn)行后序線(xiàn)索化 thrt-rchild=pre; /最后一個(gè)節(jié)點(diǎn)處理 return thrt;BiThrTree parent(BiThrTree &thrt,BiThrTree &p) BiThrTree temp; temp=thrt; if(temp-lchild=p) return tem

30、p;/父節(jié)點(diǎn)是頭結(jié)點(diǎn) else temp=temp-lchild; while( temp-lchild!=p & temp-rchild!=p ) if(0=temp-RTag) temp=temp-rchild;/結(jié)點(diǎn)有右結(jié)點(diǎn)，往右 else temp=temp-lchild; /如果結(jié)點(diǎn)沒(méi)有右孩子，去左孩子，沒(méi)有左孩子，去前驅(qū) return temp; /遍歷線(xiàn)索化二叉樹(shù)void PreOrderTraverse_Thr(BiThrTree Thrt)/Thrt:頭結(jié)點(diǎn)/遍歷先序線(xiàn)索化二叉樹(shù)BiThrTree p; p=Thrt-lchild; while(p!=Thrt)printf(

31、%c,p-data);/此樹(shù)不空 while(p-LTag = 0) p=p-lchild; printf(%c,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é)點(diǎn)/遍歷中序線(xiàn)索化二叉樹(shù)BiThrTree p; p=Thrt-lchild; while(p!=Thrt)while(p-LTag = 0) p=p-l

32、child;printf(%c,p-data); while(p-RTag=1)&(p-rchild!=Thrt) 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指向第一個(gè)被訪(fǎng)問(wèn)的結(jié)點(diǎn) else break; while(p!=Thrt) p

33、rintf(%c,p-data); par=parent(Thrt,p);/parent是p的雙親: if(Thrt=par) p=Thrt;/若parent是thrt，即p是根結(jié)點(diǎn)，則無(wú)后繼 else if(p=par-rchild|1=par-RTag) p=par; /若p是雙親的右孩子，或者是獨(dú)生左孩子，則后繼為雙親 else while(par-RTag=0) /若p是有兄弟的左孩子，則后繼為雙親的右子樹(shù)上后序遍歷訪(fǎng)問(wèn)的第一個(gè)節(jié)點(diǎn)。 par=par-rchild; while(par-LTag=0) par=par-lchild; p=par; printf(%cn,p-data);

34、 /將線(xiàn)索化后二叉樹(shù)還原void InOrder_Thr_T(BiThrTree 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=Thr

35、t-lchild;free(Thrt);/選擇菜單int menu_select()int c;doprintf(n請(qǐng)選擇需要執(zhí)行的操作序列號(hào):); scanf(%d,&c);while(c3);return c; /主函數(shù)void main()int choice; BiThrTree T,Thrt,t; /定義樹(shù) printf(請(qǐng)輸入樹(shù)的結(jié)點(diǎn)(#表示結(jié)點(diǎn)為空):n); T=CreateBiTree(); /先序算法建立二叉樹(shù)t=CopyBiTree(T); printf(n); /復(fù)制一顆二叉樹(shù)printf( 操作菜單 n);printf( n);printf( 1.遍歷操作二叉樹(shù) n);

36、printf( n);printf( 2.線(xiàn)索化二叉樹(shù) n);printf( n);printf( 3.退出所有操作 n);printf( n);for(;)choice=menu_select();switch(choice)case 1:printf(n *遍歷二叉樹(shù)*n); printf(n 遍歷二叉樹(shù)結(jié)果:n); PreOrderTraverse(T); printf(n); printf(n 遍歷二叉樹(shù)結(jié)果:n); InOrderTraverse(T); printf(n); printf(n 遍歷二叉樹(shù)結(jié)果:n); PostOrderTraverse(T); printf(nn);break;case 2:printf(n *線(xiàn)索二叉樹(shù)*n); InOrderThreading(Thrt,T);/中序線(xiàn)索化 printf(n 線(xiàn)索化后的內(nèi)容:n); InOrderTraverse_Thr(Thrt); /遍歷中序線(xiàn)索化二叉樹(shù) pri