數(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>　　學(xué) 號(hào)： </p><p>　　系部名稱： 計(jì)算機(jī)科學(xué)與技術(shù)系</p><p

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

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

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

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

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

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

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

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

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

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

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

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

14、策略有四種：先序遍歷、中序遍歷、后序遍歷和層次遍歷。</p><p><b>　　二．基本要求</b></p><p>　　1．從鍵盤接受輸入數(shù)據(jù)（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹。</p><p><b>　　2．輸出二叉樹。</b></p><p>　　3．對(duì)二叉樹進(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>　?、?采用教材上類似于先序遍歷的方法逐個(gè)輸入結(jié)點(diǎn)，建立二叉鏈表存儲(chǔ)的二叉樹。</p><p>　?、?采用遞歸算法對(duì)二叉樹分別進(jìn)行先序、中序、后序遍歷。</p><p>　　③ 以隊(duì)列為輔助結(jié)構(gòu)實(shí)現(xiàn)二叉樹的層次遍歷。</p><p>　?、?結(jié)合先序遍歷，以凹入表形式輸出二叉樹。</p><p>　　//定義二叉樹結(jié)點(diǎn)結(jié)構(gòu)和操作

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

22、等。遍歷對(duì)線性結(jié)構(gòu)來說是一個(gè)容易解決的問題，而對(duì)于二叉樹則不然，由于二叉樹是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有可能有倆棵子樹，因而需要尋找一種規(guī)律，以便使二叉樹上的結(jié)點(diǎn)都能夠排列在線性隊(duì)列上，從而便于遍歷。</p><p>　　二叉樹室友三個(gè)基本單位組成的：根節(jié)點(diǎn) 左子樹和右子樹。因而遍歷著三個(gè)部分，便是遍歷了整個(gè)二叉樹。</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>　　//定義存儲(chǔ)二叉樹結(jié)點(diǎn)指針的數(shù)組

29、空間作為隊(duì)列使用</p><p>　　int front=0, rear=0;</p><p>　　//定義隊(duì)首指針和隊(duì)尾指針，初始均置0表示空隊(duì)</p><p>　　BTreeNode* p;</p><p><b>　?。?lt;/b></p><p>　　求二叉樹的結(jié)點(diǎn)總數(shù) 葉子節(jié)點(diǎn)個(gè)數(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; //對(duì)于空樹，返回0并結(jié)束遞歸</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　//計(jì)算左子樹的深度</p><p>　　int dep1=Depth(BT->left);</p>

32、<p>　　//計(jì)算右子樹的深度</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é)點(diǎn)數(shù)</p><p>　　int BinaryTree::BTreeCount()</p><p><b>　　{ </b><

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

37、>　　//用于求二叉樹中所有葉子結(jié)點(diǎn)數(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>　　調(diào)試結(jié)果</b></p>&l

39、t;p><b>　　測(cè)試數(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>　　第五章 實(shí)習(xí)體會(huì)</p><p>　　數(shù)據(jù)結(jié)構(gòu)的實(shí)習(xí)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程. 回顧起此數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)，至今我仍

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

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

44、熟悉，還有對(duì)C語言中經(jīng)常出現(xiàn)的錯(cuò)誤也不了解，通過實(shí)踐，使我在這幾個(gè)方面的認(rèn)識(shí)有所提高。通過實(shí)踐的學(xué)習(xí)，我認(rèn)到學(xué)好計(jì)算機(jī)要重視實(shí)踐操作，不僅僅是學(xué)習(xí)C語言，還是其它的語言，以及其它的計(jì)算機(jī)方面的知識(shí)都要重在實(shí)踐，所以后在學(xué)習(xí)過程中，我會(huì)更加注視實(shí)踐操作，使自己便好地學(xué)好計(jì)算機(jī)。 </p><p>　　在今后的日子里，認(rèn)真對(duì)待每意見事，爭(zhēng)取做到最好，努力將知識(shí)與實(shí)踐相結(jié)合，不斷鞏固，加深所學(xué)的知識(shí)，做到學(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í)題解析與上機(jī)實(shí)驗(yàn)指導(dǎo)》，中國(guó)水利水電出版社、上海交通大學(xué)出版社、東南大學(xué)出版社，2002.6</p><p>

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

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