數(shù)據結構課程設計---二叉樹的操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、、后序和層次遍歷）。</p><p>　　4．將二叉樹的遍歷結果打印輸出。</p><p><b>　　三．提示與分析</b></p><p><b>　　1．主要數(shù)據類型</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>　?、?采用教材上類似于先序遍歷的方法逐個輸入結點，建立二叉鏈表存儲的二叉樹。</p><p>　　② 采用遞歸算法對二叉樹分別進行先序、中序、后序遍歷。</p><p>　?、?以隊列為輔助結構實現(xiàn)二叉樹的層次遍歷。</p><p>　?、?結合先序遍歷，以凹入表形式輸出二叉樹。</p><p>　　//定義二叉樹結點結構和操作

19、的頭文件btree1.h </p><p>　　//定義二叉樹結點值的類型為字符型</p><p>　　typedef char ElemType; </p><p>　　//定義二叉樹結點類型</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>　　二叉樹的遍歷即是如何按照某條路徑尋訪每一個結點，使得每個結點均被訪問一次，而且僅被訪問一次。“訪問”的含義很廣，可以是對結點做出各種處理，如輸出結點的信息

22、等。遍歷對線性結構來說是一個容易解決的問題，而對于二叉樹則不然，由于二叉樹是一種非線性結構，每個結點都有可能有倆棵子樹，因而需要尋找一種規(guī)律，以便使二叉樹上的結點都能夠排列在線性隊列上，從而便于遍歷。</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>　　//定義存儲二叉樹結點指針的數(shù)組

29、空間作為隊列使用</p><p>　　int front=0, rear=0;</p><p>　　//定義隊首指針和隊尾指針，初始均置0表示空隊</p><p>　　BTreeNode* p;</p><p><b>　?。?lt;/b></p><p>　　求二叉樹的結點總數(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并結束遞歸</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>　　｝</b></p><p><b>　　}</b></p><p>　　//求二叉樹中所有結點數(shù)</p><p>　　int BinaryTree::BTreeCount()</p><p><b>　　{ </b><

34、;/p><p>　　return Count(root);</p><p><b>　　}</b></p><p>　　//用于求二叉樹中所有結點數(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、　　//求二叉樹中所有葉子結點數(shù)</p><p>　　int BinaryTree::BTreeLeafCount()</p><p><b>　　{</b></p><p>　　return LeafCount(root);</p><p><b>　　}</b></p><p

37、>　　//用于求二叉樹中所有葉子結點數(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>　　｝</b></p><p><b>　　調試結果</b></p>&l

39、t;p><b>　　測試數(shù)據</b></p><p>　　1．輸入：ABC+DE+G++F+++（其中+表示空格字符）</p><p><b>　　則輸出結果為：</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>　　第五章 實習體會</p><p>　　數(shù)據結構的實習是培養(yǎng)學生綜合運用所學知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學生實際工作能力的具體訓練和考察過程. 回顧起此數(shù)據結構實習，至今我仍

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

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

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

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

46、　　3.劉懷亮，《數(shù)據結構習題解析與實驗指導》（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 求二叉樹的結