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

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

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

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

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

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

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

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

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

9、/p><p>　　3.編寫程序，運行并修改；</p><p>　　4.利用中序線索遍歷二叉樹</p><p>　　5.書寫課程設(shè)計論文并將所編寫的程序完善。</p><p><b>　　第二章 概要設(shè)計</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è)申請頭結(jié)點成功*/ </p><p>　　head->ltag=0;head->rtag=1;/*建立頭結(jié)點*/ </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);/*中序遍歷進行中序線索化*/ </p><p>　　pre->rchild=head; </p><p>　　pre->rtag=1;/*最后一個結(jié)點

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>　　{/*通過中序遍歷進行中序線索化*/ </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>　　進行中序線索化的算法：</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ū)指向當前結(jié)點*/ </p><p>　　INTHREAD(p->rchild); /* 右子樹線索化*/ </p><p><b>　　}</b></p><p><b>　　第三章 詳細設(shè)計</b&

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

21、gt;<p>　　typedef struct BiThreTree{ //定義結(jié)點元素</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; //初始化時指針標志均為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é)點的指針</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é)點時

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

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

40、簡潔。</p><p>　　例如：運行時，分別輸入（前序輸入）：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>　　第六章 測試結(jié)果</b></p><p>　　運行時，分別輸入（前序輸入）：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è)計中，我明白了理論和實際還是相差很大的，理論知識能學明白單不代表程序就能編出來，大多數(shù)情況下，我們還是不具備完成這項項目的能力的。它需要我們不僅能夠?qū)⒁郧皩W過的知識與現(xiàn)學的知識融會貫通同時還要求我們學會怎樣如何整合做項目所需要的全部知識以及對為學知識的查詢及自學能力。更重要的

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

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

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

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