數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---線索二叉樹的生成及其遍歷

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p>　　題 目: 線索二叉樹的生成及其遍歷</p><p>　　學(xué) 院： </p><p>　　班 級(jí)： </p><p>　

2、　學(xué) 生 姓 名： </p><p>　　學(xué) 生 學(xué) 號(hào)： </p><p>　　指 導(dǎo) 教 師： </p><p>　　2012 年12月5日</p><p><b>　　課程設(shè)計(jì)任務(wù)書<

3、/b></p><p><b>　　摘要</b></p><p>　　針對(duì)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子的信息，而得不到結(jié)點(diǎn)的前驅(qū)與后繼信息，為了使這種信息只有在遍歷的動(dòng)態(tài)過程中才能得到。增設(shè)兩個(gè)指針分別指示其前驅(qū)和后繼，但會(huì)使得結(jié)構(gòu)的存儲(chǔ)密度降低；并且利用結(jié)點(diǎn)的空鏈域存放（線索鏈表），方便。同時(shí)為了記下遍歷過程中訪問結(jié)點(diǎn)的先后關(guān)系，附設(shè)一個(gè)

4、指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，若指針 p 指向當(dāng)前訪問的結(jié)點(diǎn)，則 pre指向它的前驅(qū)。由此得到中序遍歷建立中序線索化鏈表的算法</p><p>　　本文通過建立二叉樹， 實(shí)現(xiàn)二叉樹的中序線索化并實(shí)現(xiàn)中序線索二叉樹的遍歷。實(shí)現(xiàn)對(duì)已生成的二叉樹進(jìn)行中序線索化并利用中序線索實(shí)現(xiàn)對(duì)二叉樹的遍歷的效果。</p><p>　　關(guān)鍵詞 二叉樹，中序線索二叉樹，中序線索二叉樹的遍歷 </p

5、><p><b>　　目錄</b></p><p><b>　　摘要I</b></p><p>　　第一章,需求分析1</p><p>　　第二章,概要設(shè)計(jì)1</p><p>　　第三章,詳細(xì)設(shè)計(jì)2</p><p>　　第四章,調(diào)試分析5<

6、/p><p>　　第五章,用戶使用說明5</p><p>　　第六章,測(cè)試結(jié)果5</p><p><b>　　第七章,緒論6</b></p><p>　　第八章,附錄參考文獻(xiàn)7</p><p>　　線索二叉樹的生成及其遍歷</p><p><b>　　第一章

7、需求分析</b></p><p>　　以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子的信息，而得不到結(jié)點(diǎn)的前驅(qū)與后繼信息，為了使這種信息只有在遍歷的動(dòng)態(tài)過程中才能得到。增設(shè)兩個(gè)指針分別指示其前驅(qū)和后繼，但會(huì)使得結(jié)構(gòu)的存儲(chǔ)密度降低；并且利用結(jié)點(diǎn)的空鏈域存放（線索鏈表），方便。同時(shí)為了記下遍歷過程中訪問結(jié)點(diǎn)的先后關(guān)系，附設(shè)一個(gè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，若指針 p 指向當(dāng)前訪問的結(jié)點(diǎn)，則 pr

8、e指向它的前驅(qū)。由此得到中序遍歷建立中序線索化鏈表的算法</p><p>　　本文通過建立二叉樹， 實(shí)現(xiàn)二叉樹的中序線索化并實(shí)現(xiàn)中序線索二叉樹的遍歷。實(shí)現(xiàn)對(duì)已生成的二叉樹進(jìn)行中序線索化并利用中序線索實(shí)現(xiàn)對(duì)二叉樹的遍歷的效果。主要任務(wù)：</p><p><b>　　1.建立二叉樹；</b></p><p>　　2.將二叉樹進(jìn)行中序線索化；<

9、/p><p>　　3.編寫程序，運(yùn)行并修改；</p><p>　　4.利用中序線索遍歷二叉樹</p><p>　　5.書寫課程設(shè)計(jì)論文并將所編寫的程序完善。</p><p><b>　　第二章 概要設(shè)計(jì)</b></p><p>　　下面是建立中序二叉樹的遞歸算法，其中pre為全局變量。 </p&

10、gt;<p>　　BiThrNodeType *pre; </p><p>　　BiThrTree InOrderThr(BiThrTree T) </p><p>　　{ /*中序遍歷二叉樹T，并將其中序線索化，pre為全局變量*/ </p><p>　　BiThrTree head; </p><p>　　head=(Bit

11、ThrNodeType *)malloc（sizeof（BiThrType））;/*設(shè)申請(qǐng)頭結(jié)點(diǎn)成功*/ </p><p>　　head->ltag=0;head->rtag=1;/*建立頭結(jié)點(diǎn)*/ </p><p>　　head->rchild=head;/*右指針回指*/ </p><p>　　if(！T)head->lchild=hea

12、d;/*若二叉樹為空，則左指針回指*/ </p><p>　　else{head->lchild=T;pre=head; </p><p>　　InThreading(T);/*中序遍歷進(jìn)行中序線索化*/ </p><p>　　pre->rchild=head; </p><p>　　pre->rtag=1;/*最后一個(gè)結(jié)點(diǎn)

13、線索化*/ </p><p>　　head->rchild=pre; </p><p><b>　　}; </b></p><p>　　return head; </p><p><b>　　} </b></p><p>　　void InThreading(BiThr

14、Tree p) </p><p>　　{/*通過中序遍歷進(jìn)行中序線索化*/ </p><p><b>　　if(p) </b></p><p>　　{InThreading(p->lchild);/*左子樹線索化*/ </p><p>　　if(p->lchild==NULL)/*前驅(qū)線索*/ </p&

15、gt;<p>　　{p->ltag=1; </p><p>　　p->lchild=pre; </p><p><b>　　} </b></p><p>　　if(p->rchild==NULL)p->rtag=1;/*后驅(qū)線索*/ </p><p>　　if(pre!=NULL &

16、amp;& pre->rtag==1) pre->rchild=p; </p><p><b>　　pre=p; </b></p><p>　　InThreading(p->rchild);/*右子樹線索化*/ </p><p><b>　　} </b></p><p>&

17、lt;b>　　} </b></p><p>　　進(jìn)行中序線索化的算法：</p><p>　　bithptr*pre; /* 全程變量*/ </p><p>　　voidINTHREAD(bithptr *p) </p><p>　　{if(p!=NULL) </p><p>　　{ INTHREAD(

18、p->lchild); /* 左子樹線索化*/ </p><p>　　if(p->lchild==NULL) {p->ltag=1;p->lchild=pre;} </p><p>　　if(p->rchild==NULL) p->rtag=1; </p><p>　　if(pre!=NULL && pre->

19、;rtag==1)pre->rchild=p; </p><p>　　pre=p; /* 前驅(qū)指向當(dāng)前結(jié)點(diǎn)*/ </p><p>　　INTHREAD(p->rchild); /* 右子樹線索化*/ </p><p><b>　　}</b></p><p><b>　　第三章 詳細(xì)設(shè)計(jì)</b&

20、gt;</p><p>　　#include <stdio.h></p><p>　　#include <malloc.h></p><p>　　typedef enum{Link,Thread} PointerTag; //指針標(biāo)志</p><p>　　typedef int DataType;</p&

21、gt;<p>　　typedef struct BiThreTree{ //定義結(jié)點(diǎn)元素</p><p>　　PointerTag LTag,RTag;</p><p>　　DataType data;</p><p>　　struct BiThreTree *lchild,*rchild;</p><p

22、>　　}BiThreTree;</p><p>　　BiThreTree *pre; //全局變量，用于二叉樹的線索化</p><p>　　BiThreTree *CreateTree() //按前序輸入建立二叉樹</p><p><b>　　{</b></p>

23、<p>　　BiThreTree *T;</p><p>　　DataType e;</p><p>　　scanf("%d",&e);</p><p><b>　　if(e==0)</b></p><p><b>　　T=NULL;</b></p>

24、<p><b>　　else</b></p><p>　　{T=(BiThreTree *)malloc(sizeof(BiThreTree));</p><p>　　T->data=e;</p><p>　　T->LTag=Link; //初始化時(shí)指針標(biāo)志均為Link</p><

25、p>　　T->RTag=Link;</p><p>　　T->lchild=CreateTree();</p><p>　　T->rchild=CreateTree();</p><p><b>　　}</b></p><p><b>　　return T;</b></

26、p><p><b>　　}</b></p><p>　　void InThread(BiThreTree *T)</p><p><b>　　{</b></p><p>　　BiThreTree *p;</p><p><b>　　p=T;</b></

27、p><p><b>　　if(p)</b></p><p><b>　　{</b></p><p>　　InThread(p->lchild);</p><p>　　if(!p->lchild)</p><p>　　{ p->LTag=Thread;</p

28、><p>　　p->lchild=pre;</p><p><b>　　}</b></p><p>　　if(!pre->rchild)</p><p>　　{ pre->RTag=Thread;</p><p>　　pre->rchild=p;</p><

29、p><b>　　}</b></p><p><b>　　pre=p;</b></p><p>　　InThread(p->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p>&

30、lt;p>　　BiThreTree *InOrderThrTree(BiThreTree *T) //中序線索化二叉樹</p><p><b>　　{</b></p><p>　　BiThreTree *Thre; //Thre為頭結(jié)點(diǎn)的指針</p><p>　　Thre=(BiThreTree *)ma

31、lloc(sizeof(BiThreTree));</p><p>　　Thre->lchild=T;</p><p>　　Thre->rchild=Thre;</p><p><b>　　pre=Thre;</b></p><p>　　InThread(T);</p><p>　　p

32、re->RTag=Thread;</p><p>　　pre->rchild=Thre;</p><p>　　Thre->rchild=pre;</p><p>　　return Thre;</p><p><b>　　}</b></p><p>　　void InThrTrav

33、el(BiThreTree *Thre) //中序遍歷二叉樹</p><p><b>　　{</b></p><p>　　BiThreTree *p;</p><p>　　p=Thre->lchild;</p><p>　　while(p!=Thre) //指針回指向頭結(jié)點(diǎn)時(shí)

34、結(jié)束</p><p><b>　　{ </b></p><p>　　while(p->LTag==Link)</p><p>　　p=p->lchild;</p><p>　　printf("%4d",p->data);</p><p>　　while(p-&

35、gt;RTag==Thread&&p->rchild!=Thre)</p><p>　　{p=p->rchild;</p><p>　　printf("%4d",p->data);</p><p><b>　　}</b></p><p>　　p=p->rchil

36、d;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b></p><p>　　BiThreTree *T,*Thre;</p>&

37、lt;p>　　T=CreateTree();</p><p>　　Thre=InOrderThrTree(T);</p><p>　　InThrTravel(Thre);</p><p>　　system("pause");</p><p><b>　　}</b></p><

38、p><b>　　第四章 調(diào)試分析</b></p><p>　　該程序在調(diào)試過程中遇到的問題是：對(duì)已學(xué)知識(shí)運(yùn)用能力欠缺，尤其是在編程方面，由于C語言等計(jì)算機(jī)基礎(chǔ)課程知識(shí)沒有很好的掌握同時(shí)在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)也沒有真正弄懂導(dǎo)致編程時(shí)小錯(cuò)誤不斷，而且在遇到許多小的錯(cuò)誤時(shí)靠自己很難再調(diào)整過來，但整體上是一次對(duì)所學(xué)知識(shí)的運(yùn)用鞏固，特別是對(duì)二叉樹的建立以及對(duì)它進(jìn)行線索方面，翻閱大量的書籍及搜集資料并求

39、教于計(jì)算機(jī)系的同學(xué)，才找到一些解決問題的方法，在用中序遍歷線索二叉樹時(shí)總是搞混不過也因此讓我對(duì)前序，中序，后序遍歷更加理解。同時(shí)，在經(jīng)歷了很多次修改重寫課程設(shè)計(jì)報(bào)告的悲慘經(jīng)歷后，懂得了很多關(guān)于辦公軟件方面的知識(shí)尤其是自己做的東西一定要保存并備份。</p><p>　　第五章 用戶使用說明</p><p>　　使用該程序時(shí)在打開程序的主界面后，輸入相應(yīng)要求的輸入形式，然后就輸出中序遍歷，方便

40、簡潔。</p><p>　　例如：運(yùn)行時(shí)，分別輸入（前序輸入）：1 2 3 0 0 4 0 5 0 0 6 0 0</p><p>　　建立如下所示的二叉樹：</p><p><b>　　1</b></p><p><b>　　2       

41、;6</b></p><p><b>　　3     4</b></p><p><b>　　5</b></p><p>　　中序遍歷輸出：3  2  4  5  1  6</p><p>

42、;<b>　　第六章 測(cè)試結(jié)果</b></p><p>　　運(yùn)行時(shí)，分別輸入（前序輸入）：1 2 3 0 0 4 0 5 0 0 6 0 0</p><p>　　建立如下所示的二叉樹：</p><p><b>　　1</b></p><p><b>　　2   

43、;    6</b></p><p><b>　　3     4</b></p><p><b>　　5</b></p><p>　　中序遍歷輸出：3  2  4  5  1

44、0; 6</p><p><b>　　第七章 結(jié)論</b></p><p>　　在這次的課程設(shè)計(jì)中，我明白了理論和實(shí)際還是相差很大的，理論知識(shí)能學(xué)明白單不代表程序就能編出來，大多數(shù)情況下，我們還是不具備完成這項(xiàng)項(xiàng)目的能力的。它需要我們不僅能夠?qū)⒁郧皩W(xué)過的知識(shí)與現(xiàn)學(xué)的知識(shí)融會(huì)貫通同時(shí)還要求我們學(xué)會(huì)怎樣如何整合做項(xiàng)目所需要的全部知識(shí)以及對(duì)為學(xué)知識(shí)的查詢及自學(xué)能力。更重要的

45、時(shí)她還要求我們敢于實(shí)踐勤于動(dòng)手，遇到有些不會(huì)處理的，我會(huì)上網(wǎng)去查，或者去問老師，或者去問同學(xué)。例如以前我對(duì)二叉樹的相關(guān)內(nèi)容并不是很熟悉，但經(jīng)過這次課程設(shè)計(jì)后現(xiàn)在我不僅掌握了它們的使用方法，更重要的是我學(xué)會(huì)了如何去學(xué)習(xí)，然后快速地應(yīng)用到我所需要的項(xiàng)目當(dāng)中。</p><p>　　同時(shí)我還得到了很多關(guān)于本門課程的體會(huì)：在編寫程序的過程中，把整個(gè)系統(tǒng)的框架準(zhǔn)確的描述出來是非常重要的而且寫程序是需要步步為營不然一不小心就會(huì)

46、出錯(cuò)。我們的C語言老師曾經(jīng)說過良好的代碼風(fēng)格是成功的一半。例如在寫代碼時(shí)會(huì)有大量的小括號(hào)，大括號(hào)等，老師曾說這些代碼在書寫時(shí)一定要同時(shí)寫一對(duì)，這樣就可以避免丟掉或忘寫其中的一個(gè)。真的是深有體會(huì)??！還有在編碼的過程中需要時(shí)常進(jìn)行修改，如果程序的可讀性不強(qiáng)，代碼量又龐大的話，那么對(duì)于我們來說是一件非常不幸的事情，程序反復(fù)的改來改去是非常繁瑣的。因此我們一定要養(yǎng)成良好的書寫代碼的習(xí)慣。</p><p>　　總之，通過一

47、次的課程設(shè)計(jì)，我不僅對(duì)我所設(shè)計(jì)的內(nèi)容有了更深的了解同時(shí)這門課程的知識(shí)掌握也更加牢固了，而且還學(xué)到很多關(guān)于辦公軟件方面的知識(shí)更重要的是通過和計(jì)算機(jī)方面的老師和同學(xué)的交流了解到了很多關(guān)于計(jì)算機(jī)方面及計(jì)算機(jī)相關(guān)工作的一些知識(shí)這位我在選方向時(shí)提供了很珍貴的意見?？偠灾@次收獲頗多！</p><p>　　第八章 附錄參考文獻(xiàn)</p><p>　　1． 嚴(yán)蔚敏，吳偉民 ．《數(shù)據(jù)結(jié)構(gòu)C語言版》 ：清華

48、大學(xué)出版社 ，2009</p><p>　　2.譚浩強(qiáng)著.C程序設(shè)計(jì)（第三版）.北京：清華大學(xué)出版社，2005</p><p>　　3.于海英，王國權(quán)編著的C語言程序設(shè)計(jì).清華大學(xué)出版社2012年版</p><p>　　4. 備注：還有很多我只是考了相關(guān)內(nèi)容由于計(jì)算機(jī)能力有限我不知道如何查找是什么書。</p><p><b>