課程設計---判斷完全二叉樹

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：15 大?。?43.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩14頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領

文檔簡介

1、　　課程設計報告　　課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設計 　　設計題目：完全二叉樹判斷 　　系別：計算機系 　　專

2、業(yè)： 　　組別：第三組 　　學生姓名: 學號: 　　起止日期:

3、 　　指導教師: 　　目錄　　第一章需求分析2　　1.1課程設計任務及要求2　　1.2

4、課程設計思想及開發(fā)環(huán)境2　　第二章概要設計3　　2.1 總體方案3　　2.2 功能模塊說明3　　第三章調(diào)試與操作說明4　　第四章課程設計總結(jié)與體會4　　第五

5、章致謝7　　第六章參考文獻7　　附錄（源代碼）7　　第一章需求分析　　1.1課程設計任務及要求<p&

6、gt;　　該課程設計的題目為：完全二叉樹的判別。也就是對于輸入的　　二叉樹進行判定，看是否為完全二叉樹。　　為實現(xiàn)此次課程設計的完成，對程序設計作了相應的定義與限制。首先，為了輸入的簡潔，將樹的結(jié)點樹不大于20；其次，對于二叉樹的輸入就按照前序遍歷的順序進行輸入；最后，對于程序的測試，應該從正反兩面進行測試，即輸入一個是完全二叉樹和一個不是完全二叉樹的。

7、　　由于輸入二叉樹時，對于不是完全二叉樹的，有的結(jié)點會沒有左子樹或右子樹，甚至兩子樹都沒有，為跟好的表示沒有子樹的情況，在此次程序設計中用“.”來表示　　1.2課程設計思想及開發(fā)環(huán)境　　編寫語言： C語言　　開發(fā)工具： Visual

8、C++ Visual Studio 6.0　　VC++是微軟公司開發(fā)的一個IDE(集成開發(fā)環(huán)境)。學習VC要了解很多Windows平臺的特性并且還要掌握MFC、ATL、COM等的知識， VC基于C，C++語言，主要由是MFC組成，是與系統(tǒng)聯(lián)系非常緊密的編程工具，它兼有高級，和低級語言的雙重性，功能強大，靈活，執(zhí)行效率高，幾乎可說VC在 Windows平臺無所不能。最大缺點是開發(fā)效率不高。<

9、;/p>　　對于二叉樹的構(gòu)造，可以運用插入建立，還可以用遞歸建立。在此次設計中運用的是遞歸建立。運用隊列的進隊函數(shù)進行對二叉樹的結(jié)點的輸入。對于進隊的第一個數(shù)據(jù)為二叉樹的根結(jié)點，如果為非空，則繼續(xù)輸入第二個進隊元素，將其設置為該根結(jié)點的左子樹，然后將該左子樹作為新的根結(jié)點，依次進行到下一層的結(jié)點，直至到達葉節(jié)點（即既沒有左子樹也沒有右子樹），然后對于這以后進隊的元素則作為右子樹，用相同的方法建樹。</p

10、>　　第二章概要說明　　2.1判定是否為完全二叉樹的算法　　判定完全二叉樹，首先要知道什么是完全二叉樹，對完全二叉樹定義以前，要明白滿二叉樹的定義。一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。對滿二叉樹的你借點進行連續(xù)編號，約定編號從根結(jié)點起，自上而下，自左而右。由此引出完全二叉

11、樹的定義。深度為k的，右n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹的編號從1至n的結(jié)點一一對應時，稱之為完全二叉樹。所以對于二叉樹的判定，假如某一結(jié)點有右子樹但沒有左子樹則該樹不是完全二叉樹。如果某一結(jié)點沒有右子樹或沒有左子樹，但是其后的結(jié)點有左子樹或右子樹，則該樹不是完全二叉樹。根據(jù)這種判定方法，可以判定其是不是完全二叉樹。　　2.2功能模塊說明</b

12、>　　程序各模塊之間的關系圖　　圖1程序模塊關系圖　　第三章調(diào)試與操作說明　　3.1編碼設計　　編碼建立上一步詳細設計結(jié)果的基礎上，對編碼進行調(diào)試。

13、　　3.2調(diào)試　　調(diào)試一向是我感覺很頭疼的一個環(huán)節(jié)，因為程序中會因為各種各樣的原因出現(xiàn)很多錯誤。所以在調(diào)試前應該做好充分的準備，比如說準備一本高級語言程序設計的教材以及先建立好工程和文件。　　在設計中，我使用的是Visual C++ 6.0為平臺對程序進行調(diào)試。調(diào)試之前就是要

14、把源程序輸入進去，我建立了一個.c文件。　　輸完源代碼后對代碼進行編譯，出現(xiàn)了諸多問題。比如說，會在語句后面丟掉分號、輸入的標點符號不是英語輸入中的而是中文輸入中的、語法錯誤、函數(shù)調(diào)用不匹配的問題等等。對于這些錯誤需要相當大的耐性，但是都不難解決，只要細心的檢查程序就可以更正了?？梢栽谡{(diào)試錯誤中找到出錯的地方，根據(jù)錯誤信息提示進行改錯。對于有的錯誤提示并不明白是什么錯誤，也是通過查資料書和在網(wǎng)絡

15、上搜索到底是什么錯誤，在尋求解決方法。　　在編譯沒有錯誤之后開始組建。　　在組建出現(xiàn)了內(nèi)存泄露，這是在編程中經(jīng)常出現(xiàn)的問題。產(chǎn)生這種問題的原因也有很多種。大多數(shù)情況下就是指針出現(xiàn)錯誤。于是我就開始檢查程序中使用到指針的地方，進行檢測，最后查出來問題并更正了。　　調(diào)試沒有錯誤以后，就是進行程序執(zhí)行。</p&g

16、t;　　4.程序運行結(jié)果　　系統(tǒng)菜單圖：　　圖2人機交互界面　　按照擴展先序遍歷序列建立二叉樹：　　圖3建立二叉樹&l

17、t;/b>　　打印輸入的二叉樹：　　圖4打印輸入的二叉樹　　判斷完全二叉樹：　　圖5得出結(jié)論　　第四章課程設計

18、總結(jié)與體會　　在這次課程設計中，我還學到了許多東西。對于程序設計中的錯誤處理也有了更多的認識，也掌握了關于內(nèi)存泄露的相關知識。而且對于二叉鏈表也有了更好的理解，對于用遞歸法建立二叉樹也有了更多的理解。　　對于程序設計也有了更好的理解，程序設計不光只是要得到相應的運行結(jié)果就可以的，還有考慮它的健壯性，以及與用戶之間的交流，要能夠直觀的，簡潔的表示該程序的使

19、用方法和功能，而且還要有很好的重復使用性，這樣的算法才是好的算法。　　當然在這方面上我還有很多的不足，需要更多的努力，在反復實踐過程中不斷地完善自己在這方面的能力。　　這次的設計，讓我大大地感覺到，對于程序設計中，對語言再熟悉也比不過在設計中算法和結(jié)構(gòu)分析的真知灼見。當然，成功的程序設計是要建立在熟悉語言的基礎之上的。平時語言的基本功要扎實。而每一次程序

20、設計的經(jīng)營能大大地增加對語言的熟悉和感知。程序設計的技能來自多方面，每一次的親自實踐、思考揣摩、刨根問底就會讓自己更加清楚所欠缺的是什么。所以，現(xiàn)在覺得在設計實踐中作為參考的書冊閱讀和研究遠遠比過單純的閱讀，因為它是在最緊迫的時間上填補自己最緊迫的不足。　　第五章致謝　　感謝所有幫助我的人，是你們不計回報的付出，除

21、了幫我完成了這份課程設計，也讓我感受到了身邊的溫暖。　　感謝馬強老師，您平常的教導，到現(xiàn)在我才明白是多么的有用，謝謝您的督促。　　感謝陌生的朋友，在知道我需要幫助后，第一時間提供了具有很大價值的參考資料，也明白自己還需要更多的努力。　　這次的設計，讓我大大地感覺到，對于程序設計中，對語言再熟悉也比不過在設計中算法

22、和結(jié)構(gòu)分析的真知灼見。當然，成功的程序設計是要建立在熟悉語言的基礎之上的。平時語言的基本功要扎實。而每一次程序設計的經(jīng)營能大大地增加對語言的熟悉和感知。程序設計的技能來自多方面，每一次的親自實踐、思考揣摩、刨根問底就會讓自己更加清楚所欠缺的是什么。所以，現(xiàn)在覺得在設計實踐中作為參考的書冊閱讀和研究遠遠比過單純的閱讀，因為它是在最緊迫的時間上填補自己最緊迫的不足。　　第六章參考文獻</

23、p>　　[1]：嚴蔚敏，吳偉民，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），北京：清華大學出版社，2009年　　[2]：王昆侖，李紅?！稊?shù)據(jù)結(jié)構(gòu)與算法》。北京：中國鐵道出版社　　[3]：耿國華，《數(shù)據(jù)結(jié)構(gòu)》北京：高等教育出版社，2005　　[4]：譚浩強，C程序設計（第三版）[M]，北京：清華大學出版社

24、，2008年　　附錄源代碼　　//判斷完全二叉樹算法描述　　#include<stdio.h>　　#include<stdlib.h>　　#define true 1

25、　　#define false 0　　//二叉樹數(shù)據(jù)結(jié)構(gòu)　　typedef struct BiTNode　　{　　char data;

26、　　struct BiTNode *LChild, *RChild;　　}BiNode,*BiTree;　　//含頭尾指針的鏈隊列數(shù)據(jù)結(jié)構(gòu)　　typedef struct QueueNode　　{</p&g

27、t;　　BiTree data;　　struct QueueNode *next;　　}LinkQueueNode;　　typedef struct 　　{　　LinkQ

28、ueueNode *front;　　LinkQueueNode *rear;　　}LinkQueue;　　//函數(shù)聲明　　void Print(BiTree *root);　　void Cho

29、ose(int choice,BiTree *root);　　void ReadPreOrder(BiTree *root);　　void PrintPreOrder(BiTree root);　　int CompleteBinaryTree(BiTree root);

30、　int InitQueue(LinkQueue *Q);　　int EnterQueue(LinkQueue *Q,BiTree x);　　int DeleteQueue(LinkQueue *Q);　　//主函數(shù)　　int mai

31、n()　　{　　BiTree root;　　root=NULL;//初始化無頭結(jié)點　　system("color b");　　Print(&root);</

32、p>　　while(true)　　{　　printf("Press enter to continue.........");　　getchar();　　getchar();</p

33、>　　system("cls");　　Print(&root);　　}　　return 0;　　}&l

34、t;/p>　　void Print(BiTree *root)　　{　　int choice;　　printf("---------------------\n");　　printf(&

35、quot;使用說明:本程序可實現(xiàn)基于隊列的廣度優(yōu)先遍歷算法判斷完全二叉樹.\n");　　printf("---------------------\n");　　printf("1.輸入擴展先序遍歷序列并建立對應的二叉樹.\n");　　printf("2.

36、打印當前的二叉樹的擴展先序遍歷序列.\n");　　printf("3.判斷當前的二叉樹是否為完全二叉樹.\n");　　printf("4.按其它任意鍵退出.\n");　　printf("---------------------\n");<

37、;/p>　　printf("請選擇你要的操作:");　　scanf("%d",&choice);　　getchar();//此處getchar存儲回車，避免對后面函數(shù)的影響！（很重要?。?lt;/p>　　Choose(choice,root);<

38、/p>　　}　　void Choose(int choice,BiTree *root)　　{　　switch(choice)　　{

39、;　　case 1:　　ReadPreOrder(root);　　break;　　case 2:　　PrintPre

40、Order(*root);　　printf("\n");　　break;　　case 3:　　if(CompleteBinaryTree(*root))

41、　　{　　printf("當前二叉樹是完全二叉樹！\n");　　}　　else{　　printf("當前二叉樹

42、不是完全二叉樹！\n");　　}　　break;　　default:　　exit(0);

43、　　}　　}　　void ReadPreOrder(BiTree *root)　　//先序遍歷二叉樹，root為指向二叉樹（或某一子樹）根結(jié)點的指針　　{&l

44、t;/b>　　char ch;　　ch=getchar();//使用getchar輸入時必須謹記前面有沒有多余的回車　　if(ch=='.')　　{&

45、lt;p>　　(*root)=NULL;　　}　　else　　{　　(*root)=(BiNode *)malloc(sizeof(BiNode));&

46、lt;/p>　　(*root)->data=ch;　　ReadPreOrder(&((*root)->LChild));　　ReadPreOrder(&((*root)->RChild));　　}

47、;　　}　　void PrintPreOrder(BiTree root)　　{　　if(root!=NULL)　　{

48、;　　printf("%c",(root)->data);　　PrintPreOrder(root->LChild);　　PrintPreOrder(root->RChild);　　}<

49、p>　　else 　　{　　printf(".");　　}　　}<

50、;p>　　//完全二叉樹判斷函數(shù)　　//先利用隊列找出二叉樹中第一個沒有包含兩個孩子的節(jié)點（即第一個非正常節(jié)點）　　//從第一個非正常節(jié)點后面開始出隊的所有節(jié)點均不含子節(jié)點則該二叉樹為完全二叉樹　　int CompleteBinaryTree(BiTree root)

51、;　　{　　int flag;　　LinkQueue BiNode;//創(chuàng)建隊列　　InitQueue(&BiNode);//初始化隊列　　EnterQueue(&BiNode,r

52、oot);//將根節(jié)點入隊　　while(BiNode.front!=BiNode.rear)//當隊列不為空時進行廣度優(yōu)先掃描二叉樹　　//當發(fā)現(xiàn)非正常節(jié)點時跳出循環(huán)　　{　　if(BiNode.front->next->

53、;data->LChild!=NULL&&BiNode.front->next->data->RChild!=NULL)　　//當左右孩子均有　　{　　//左右孩子入隊</b

54、>　　EnterQueue(&BiNode,BiNode.front->next->data->LChild);　　EnterQueue(&BiNode,BiNode.front->next->data->RChild);　　DeleteQueue(&am

55、p;BiNode);//節(jié)點出隊　　}　　else　　break;　　}//下面分三種情況討論　　//左孩子沒有右

56、孩子沒有，繼續(xù)掃描　　if(BiNode.front->next->data->LChild==NULL&&BiNode.front->next->data->RChild==NULL)　　{　　DeleteQueue(&a

57、mp;BiNode);　　while(BiNode.front!=BiNode.rear)　　{　　if(BiNode.front->next->data->LChild!=NULL || BiNode.front->next->data->

58、;RChild!=NULL)　　return false;　　DeleteQueue(&BiNode);　　}　　return true;　　}&

59、lt;/p>　　//左孩子有右孩子沒有，繼續(xù)掃描　　else if(BiNode.front->next->data->LChild!=NULL&&BiNode.front->next->data->RChild==NULL)　　{&l

60、t;/p>　　EnterQueue(&BiNode,BiNode.front->next->data->LChild);　　DeleteQueue(&BiNode);　　while(BiNode.front!=BiNode.rear)

61、　　{　　if(BiNode.front->next->data->LChild!=NULL || BiNode.front->next->data->RChild!=NULL)　　return false;　　DeleteQueue(&BiNode

62、);　　}　　return true;　　}　　//左孩子沒有右孩子有，非完全二叉樹　　else if(BiNode.front->next-&g

63、t;data->LChild==NULL&&BiNode.front->next->data->RChild!=NULL)　　return false;　　}　　//隊列的初始化函數(shù)　　int

64、InitQueue(LinkQueue *Q)　　{　　//將Q初始化為一個空的鏈隊列　　Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));　　if(Q->fr

65、ont!=NULL)　　{　　Q->rear=Q->front;　　Q->front->next=NULL;　　return true;　　}<

66、/b>　　else　　return false;//溢出　　}　　//入隊函數(shù)　　int EnterQueue

67、(LinkQueue *Q,BiTree x)　　{　　//將數(shù)據(jù)元素x插入到隊列Q中　　LinkQueueNode *NewNode;　　NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueu

68、eNode));　　if(NewNode!=NULL)　　{　　NewNode->data=x;　　NewNode->next=NULL;　　Q->rear->next

69、=NewNode;　　Q->rear=NewNode;　　return true;　　}　　else　　return false;//溢出</

70、p>　　}　　//出隊操作　　int DeleteQueue(LinkQueue *Q)　　{　　//將隊列Q的隊頭元素出隊，并存

71、放到x所指的存儲空間中　　LinkQueueNode *p;　　if(Q->front==Q->rear)　　return false;//隊列為空均指向頭結(jié)點　　p=Q->front->next;　　Q

72、->front->next=Q->front->next->next;//隊頭元素p出隊　　if(Q->rear==p)//如果隊中只有一個元素p，則p出隊后成為空隊　　{　　Q->rear=Q->front;

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設計---判斷完全二叉樹

文檔簡介

溫馨提示

最新文檔

評論

課程設計---判斷完全二叉樹

文檔簡介

溫馨提示

最新文檔

評論

免費下載