數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---二叉樹的操作

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p>　　題 目： 二叉樹的操作 </p><p>　　學(xué)生姓名： </p><p>　　學(xué) 號： </p><p>　　系部名稱： 計算機科學(xué)與技術(shù)系</p><p

2、>　　專業(yè)班級： </p><p>　　指導(dǎo)教師： </p><p>　課 程 設(shè) 計 任 務(wù) 書</p><p>　組內(nèi)學(xué)生姓名人數(shù)1</p><p>　系部名稱計算機科學(xué)與技術(shù)系專業(yè)軟件工程班級、學(xué)號</p><p>　指導(dǎo)教師姓名職稱從事專業(yè)軟件工程</p><p&g

3、t;　題目名稱二叉樹的操作</p><p>　課程設(shè)計的目的、意義目的在于通過課程設(shè)計的綜合訓(xùn)練，幫助學(xué)生深入系統(tǒng)地掌握數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容和基本方法，培養(yǎng)學(xué)生綜合運用所學(xué)知識分析解決實際問題和編程等實際動手能力。熟練的掌握二叉樹的基本操作。</p><p>　二、課程設(shè)計的主要內(nèi)容、技術(shù)要求（包括原始數(shù)據(jù)、技術(shù)參數(shù)、設(shè)計要求、工作量要求等）實現(xiàn)二叉樹的先序、中序和后序遍歷；求二叉樹的結(jié)

4、點總數(shù)、葉子結(jié)點個數(shù)及二叉樹的深度。</p><p>　三、課程設(shè)計完成后應(yīng)提交的成果完整的論文和部分源代碼</p><p>　四、課程設(shè)計的工作進(jìn)度安排（1）復(fù)習(xí)與設(shè)計題目相關(guān)的數(shù)據(jù)結(jié)構(gòu)知識，查閱文獻(xiàn)資料 （1天）（2）確定設(shè)計方案，設(shè)計模塊結(jié)構(gòu)及各模塊流程 （1天）（3）編碼、調(diào)試與測試

5、 （5天）（4）撰寫課程設(shè)計報告 （2天）（5）設(shè)計演示 （1天） </p><p>　五、主要參考資料1.嚴(yán)蔚敏、吳偉民，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），北京：清華大學(xué)出版社，2006.52.寧正元、易金聰，《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機實驗指導(dǎo)》，中國水利水電出版社、上海

6、交通大學(xué)出版社、東南大學(xué)出版社，2002.6</p><p>　六、備注</p><p>　指導(dǎo)教師簽字：年 月 日教研室主任簽字： 年 月 日</p><p><b>　　程序要求</b></p><p>　　1）完成二叉樹的基本操作。</p><p>　　2）建

7、立以二叉鏈表為存儲結(jié)構(gòu)的二叉樹；</p><p>　　3）實現(xiàn)二叉樹的先序、中序和后序遍歷；</p><p>　　4）求二叉樹的結(jié)點總數(shù)、葉子結(jié)點個數(shù)及二叉樹的深度。</p><p><b>　　算法分析</b></p><p>　　建立以二叉鏈表為存儲結(jié)構(gòu)的二叉樹，在次二叉樹上進(jìn)行操作；</p><

8、p>　　1先序遍歷二叉樹的操作定義為：</p><p>　　若二叉樹唯恐則為空操作；否則</p><p><b>　?。?）訪問根節(jié)點；</b></p><p>　?。?）先序遍歷做字?jǐn)?shù)和；</p><p>　?。?）先序遍歷有子樹；</p><p>　　2中序遍歷二叉樹的操作定義為：<

9、;/p><p>　　若二叉樹為空，則空操作;否則 </p><p>　?。?）中序遍歷做子樹；</p><p><b>　?。?）訪問根節(jié)點；</b></p><p>　?。?）中序遍歷有子樹；</p><p>　　3后續(xù)遍歷二叉樹的操作定義為：</p><p>　　若二叉樹為

10、空則為空操作；否則</p><p>　?。?)后序遍歷左子樹 ;</p><p>　?。?)后序遍歷右子樹;</p><p>　?。?）訪問根節(jié)點 ； </p><p>　　二叉樹的結(jié)點總數(shù)、葉子結(jié)點個數(shù)及二叉樹的深度。</p><p><b>　　二叉樹的基本操作和</b></p>

11、<p>　　算法實現(xiàn) </p><p>　　二叉樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，是另一種樹形結(jié)構(gòu)，它的特點是每個節(jié)點之多有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點)，并且二叉樹的結(jié)點有左右之分，其次序不能隨便顛倒。</p><p><b>　　二叉樹創(chuàng)建</b></p><p>　　二叉樹的很多操作都是基于遍歷實現(xiàn)的。二叉

12、樹的遍歷是采用某種策略使得采用樹形結(jié)構(gòu)組織的若干年借點對應(yīng)于一個線性序列。二叉樹的遍歷策略有四種：先序遍歷 中續(xù)遍歷 后續(xù)遍歷和層次遍歷。</p><p><b>　　基本要求</b></p><p>　　1 從鍵盤接受輸入數(shù)據(jù)（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹。</p><p><b>　　2 輸出二叉樹。</b&g

13、t;</p><p>　　3 對二叉樹進(jìn)行遍歷（先序，中序，后序和層次遍歷）</p><p>　　4 將二叉樹的遍歷打印出來。</p><p><b>　　一．問題描述</b></p><p>　　二叉樹的很多操作都是基于遍歷實現(xiàn)的。二叉樹的遍歷是采用某種策略使得采用樹型結(jié)構(gòu)組織的若干結(jié)點對應(yīng)于一個線性序列。二叉樹的遍歷

14、策略有四種：先序遍歷、中序遍歷、后序遍歷和層次遍歷。</p><p><b>　　二．基本要求</b></p><p>　　1．從鍵盤接受輸入數(shù)據(jù)（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹。</p><p><b>　　2．輸出二叉樹。</b></p><p>　　3．對二叉樹進(jìn)行遍歷（先序、中序

15、、后序和層次遍歷）。</p><p>　　4．將二叉樹的遍歷結(jié)果打印輸出。</p><p><b>　　三．提示與分析</b></p><p><b>　　1．主要數(shù)據(jù)類型</b></p><p><b>　　① 二叉鏈表</b></p><p>　　#

16、 define DataType char /*元素類型*/</p><p>　　typedef struct BiTNode</p><p>　　{DataType data;</p><p>　　struct BiTNode *lchild, *rchild;</p><p>　　}BiTNode, *BiTree;</p>

17、<p>　　② 二叉樹的遍歷序列</p><p>　　DataType preorder[n];</p><p>　　DataType inorder[n];</p><p>　　DataType postorder[n];</p><p><b>　　2．基本功能分析</b></p><

18、;p>　?、?采用教材上類似于先序遍歷的方法逐個輸入結(jié)點，建立二叉鏈表存儲的二叉樹。</p><p>　?、?采用遞歸算法對二叉樹分別進(jìn)行先序、中序、后序遍歷。</p><p>　?、?以隊列為輔助結(jié)構(gòu)實現(xiàn)二叉樹的層次遍歷。</p><p>　?、?結(jié)合先序遍歷，以凹入表形式輸出二叉樹。</p><p>　　//定義二叉樹結(jié)點結(jié)構(gòu)和操作

19、的頭文件btree1.h </p><p>　　//定義二叉樹結(jié)點值的類型為字符型</p><p>　　typedef char ElemType; </p><p>　　//定義二叉樹結(jié)點類型</p><p>　　struct BTreeNode {</p><p>　　ElemType data;</p&

20、gt;<p>　　BTreeNode* left;</p><p>　　BTreeNode* right;</p><p><b>　　}; </b></p><p>　　//初始化二叉樹，即把樹根指針置空</p><p>　　void InitBTree(BTreeNode*& BT);<

21、/p><p>　　//判斷二叉樹是否為空</p><p>　　bool BTreeEmpty(BTreeNode* BT);</p><p>　　1.1.1 二叉樹的遍歷</p><p>　　二叉樹的遍歷即是如何按照某條路徑尋訪每一個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次?！霸L問”的含義很廣，可以是對結(jié)點做出各種處理，如輸出結(jié)點的信息

22、等。遍歷對線性結(jié)構(gòu)來說是一個容易解決的問題，而對于二叉樹則不然，由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點都有可能有倆棵子樹，因而需要尋找一種規(guī)律，以便使二叉樹上的結(jié)點都能夠排列在線性隊列上，從而便于遍歷。</p><p>　　二叉樹室友三個基本單位組成的：根節(jié)點 左子樹和右子樹。因而遍歷著三個部分，便是遍歷了整個二叉樹。</p><p>　　void TraverseBTree(BTreeNo

23、de* BT, int mark)</p><p><b>　　{</b></p><p>　　if(mark==1) { //先序遍歷</p><p>　　if(BT!=NULL) {</p><p>　　cout<<BT->data<<' ';</p>&

24、lt;p>　　TraverseBTree(BT->left,mark);</p><p>　　TraverseBTree(BT->right,mark);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else if(mark=

25、=2) { //中序遍歷</p><p>　　if(BT!=NULL) {</p><p>　　TraverseBTree(BT->left,mark);</p><p>　　cout<<BT->data<<' ';</p><p>　　TraverseBTree(BT->right

26、,mark);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else if(mark==3) { //后序遍歷</p><p>　　if(BT!=NULL) {</p><p>　　TraverseBTree(BT-&

27、gt;left,mark);</p><p>　　TraverseBTree(BT->right,mark);</p><p>　　cout<<BT->data<<' ';</p><p><b>　　}</b></p><p><b>　　}</b&g

28、t;</p><p>　　else if(mark==4) //按層遍歷</p><p><b>　　{</b></p><p>　　const MaxLength=30;</p><p>　　BTreeNode* Q[MaxLength];</p><p>　　//定義存儲二叉樹結(jié)點指針的數(shù)組

29、空間作為隊列使用</p><p>　　int front=0, rear=0;</p><p>　　//定義隊首指針和隊尾指針，初始均置0表示空隊</p><p>　　BTreeNode* p;</p><p><b>　?。?lt;/b></p><p>　　求二叉樹的結(jié)點總數(shù) 葉子節(jié)點個數(shù)</

30、p><p><b>　　及二叉樹的深度</b></p><p>　　//用于求二叉樹深度的遞歸函數(shù)</p><p>　　int Depth(BTreeNode* BT)</p><p><b>　　{</b></p><p>　　if(BT==NULL)</p>&

31、lt;p>　　return 0; //對于空樹，返回0并結(jié)束遞歸</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　//計算左子樹的深度</p><p>　　int dep1=Depth(BT->left);</p>

32、<p>　　//計算右子樹的深度</p><p>　　int dep2=Depth(BT->right);</p><p><b>　　//返回樹的深度</b></p><p>　　if(dep1>dep2) return dep1+1; </p><p>　　else return dep2+1

33、;</p><p><b>　?。?lt;/b></p><p><b>　　}</b></p><p>　　//求二叉樹中所有結(jié)點數(shù)</p><p>　　int BinaryTree::BTreeCount()</p><p><b>　　{ </b><

34、;/p><p>　　return Count(root);</p><p><b>　　}</b></p><p>　　//用于求二叉樹中所有結(jié)點數(shù)的遞歸函數(shù)</p><p>　　int Count(BTreeNode* BT)</p><p><b>　　{</b></p

35、><p>　　if(BT==NULL) return 0;</p><p><b>　　else</b></p><p>　　return Count(BT->left)+Count(BT->right)+1;</p><p><b>　　}</b></p><p>

36、　　//求二叉樹中所有葉子結(jié)點數(shù)</p><p>　　int BinaryTree::BTreeLeafCount()</p><p><b>　　{</b></p><p>　　return LeafCount(root);</p><p><b>　　}</b></p><p

37、>　　//用于求二叉樹中所有葉子結(jié)點數(shù)的遞歸函數(shù)</p><p>　　int LeafCount(BTreeNode* BT)</p><p><b>　　{</b></p><p>　　if(BT==NULL) return 0;</p><p>　　else if(BT->left==NULL &

38、& BT->right==NULL) return 1;</p><p>　　else return LeafCount(BT->left)+LeafCount(BT->right);</p><p><b>　?。?lt;/b></p><p><b>　　調(diào)試結(jié)果</b></p>&l

39、t;p><b>　　測試數(shù)據(jù)</b></p><p>　　1．輸入：ABC+DE+G++F+++（其中+表示空格字符）</p><p><b>　　則輸出結(jié)果為：</b></p><p>　　先序：ABCDEGF</p><p>　　中序：CBEGDFA</p><p>

40、;　　后序：CGEFDBA</p><p>　　2．輸入：AB+DG+++CE++F++</p><p>　　先序：ABDGCEF</p><p>　　中序：BGDAECF</p><p>　　后序：GDBEFCA</p><p>　　3．輸入：ABDF++++C+E+G++</p><p>　

41、　先序：ABDFCEG</p><p>　　中序：FDBACEG</p><p>　　后序：FDBGECA</p><p>　　第五章 實習(xí)體會</p><p>　　數(shù)據(jù)結(jié)構(gòu)的實習(xí)是培養(yǎng)學(xué)生綜合運用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程. 回顧起此數(shù)據(jù)結(jié)構(gòu)實習(xí)，至今我仍

42、感慨頗多，的確，從選題到定稿，從理論到實踐，在整整兩星期的日子里，可以說得是苦多于甜，但是可以學(xué)到很多很多的的東西，同時不僅可以鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。通過這次實習(xí)使我懂得了理論與實際相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，從而提高自己的實際動手能力和獨立思考的能力。在設(shè)計的過程中遇到問題，可以說得是困難重重，這畢竟第一次做的，難免會遇

43、到過各種各樣的問題，同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固。</p><p>　　經(jīng)過兩個星期的上機實踐學(xué)習(xí)，使我對數(shù)據(jù)機構(gòu)有了更進(jìn)一步的認(rèn)識和了解，要想學(xué)好它要重在實踐，要通過不斷的上機操作才能更好地學(xué)習(xí)它，通過實踐，我也發(fā)現(xiàn)我的好多不足之處，首先是自己對知識點的掌握不夠熟悉，通過學(xué)習(xí)也有所改進(jìn)；再有對C語言的一些標(biāo)準(zhǔn)庫函數(shù)不太了解，還有對函數(shù)調(diào)用的正確使用不夠

44、熟悉，還有對C語言中經(jīng)常出現(xiàn)的錯誤也不了解，通過實踐，使我在這幾個方面的認(rèn)識有所提高。通過實踐的學(xué)習(xí)，我認(rèn)到學(xué)好計算機要重視實踐操作，不僅僅是學(xué)習(xí)C語言，還是其它的語言，以及其它的計算機方面的知識都要重在實踐，所以后在學(xué)習(xí)過程中，我會更加注視實踐操作，使自己便好地學(xué)好計算機。 </p><p>　　在今后的日子里，認(rèn)真對待每意見事，爭取做到最好，努力將知識與實踐相結(jié)合，不斷鞏固，加深所學(xué)的知識，做到學(xué)

45、以致用。</p><p><b>　　參考文獻(xiàn)：</b></p><p>　　1.嚴(yán)蔚敏、吳偉民，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），北京：清華大學(xué)出版社，2006.5</p><p>　　2.寧正元、易金聰，《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機實驗指導(dǎo)》，中國水利水電出版社、上海交通大學(xué)出版社、東南大學(xué)出版社，2002.6</p><p>

46、　　3.劉懷亮，《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實驗指導(dǎo)》（C語言描述），冶金工業(yè)出版社，2005.2</p><p>　　目 錄</p><p>　　程序要求 —————————————— 1</p><p>　　算法分析 —————————————— 1 </p><p>　　二叉樹的基本操作和算法實現(xiàn)———————

47、 1 </p><p>　　1.1 二叉樹的創(chuàng)建 ---------------------------------- 4</p><p>　　1.1.1 二叉樹的遍歷 -------------------------------- 7 </p><p>　　1.1.1.1 求二叉樹的結(jié)