課程設(shè)計---完全二叉樹的判斷

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

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

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

文檔簡介

1、　　《完全二叉樹的判斷》　　課程設(shè)計論文　　學(xué)生姓名 　　學(xué) 號 　　所屬學(xué)院信息工程學(xué)院 　　專

2、業(yè) 計算機科學(xué)與技術(shù) 　　班級計算機 　　指導(dǎo)教師 　　教師職稱講師 　　目錄

3、　　前言1　　正文2　　2.1課程設(shè)計任務(wù)及要求2　　2.2課程設(shè)計思想2　　2.3判定是否為完全二叉樹的算法2　　2.4功能模塊說明3

4、　　2.5編碼設(shè)計4　　2.6調(diào)試5　　2.7程序運行結(jié)果6　　課程設(shè)計總結(jié)9　　參考文獻(xiàn)10

5、;　　附錄11　　前言　　在計算機科學(xué)中，二叉樹是每個結(jié)點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹

6、的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結(jié)點；深度為k的二叉樹至多有2^(k) -1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)(即葉子結(jié)點數(shù))為n0，度為2的結(jié)點數(shù)為n2，則n0 = n2 + 1。　　二叉樹也是遞歸定義的，其結(jié)點有左右子樹之分，邏輯上二叉樹有五種基本形態(tài)：<

7、p>　　(1)空二叉樹——(a)；　　(2)只有一個根結(jié)點的二叉樹——(b)； 　　(3)只有左子樹——(c)； 　　(4)只有右子樹——(d)； 　　(5)完全二叉樹——(e) 　　完全二叉樹：<

8、;/b>　　若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層有葉子結(jié)點，并且葉子結(jié)點都是從左到右依次排布，這就是完全二叉樹?！?　　　　滿二叉樹　　除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹。

9、　　深度:　　二叉樹的層數(shù)，就是高度。　　先序遍歷：　　　　先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結(jié)點向下先左后右）。　　首先訪問根結(jié)點然后遍歷左子樹，最后遍歷右子樹。在遍歷左

10、、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。　　　　例如，下圖所示二叉樹的遍歷結(jié)果是：ABDECF 　　正文　　2.1課程設(shè)計任務(wù)及要求　　該課程設(shè)計的題目為：完全二叉樹的判別。也就是對于輸入

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

12、，對于不是完全二叉樹的，有的結(jié)點會沒有左子樹或右子樹，甚至兩子樹都沒有，為跟好的表示沒有子樹的情況，在此次程序設(shè)計中用“.”來表示.　　在計算機科學(xué)中，二叉樹是每個結(jié)點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，

13、二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結(jié)點；深度為k的二叉樹至多有2^(k) -1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)(即葉子結(jié)點數(shù))為n0，度為2的結(jié)點數(shù)為n2，則n0 = n2 + 1。　　2.2課程設(shè)計思想　　對于二叉樹的構(gòu)造，可以運用插入建立，還可以用遞歸建立。

14、在此次設(shè)計中運用的是遞歸建立。運用隊列的進(jìn)隊函數(shù)進(jìn)行對二叉樹的結(jié)點的輸入。對于進(jìn)隊的第一個數(shù)據(jù)為二叉樹的根結(jié)點，如果為非空，則繼續(xù)輸入第二個進(jìn)隊元素，將其設(shè)置為該根結(jié)點的左子樹，然后將該左子樹作為新的根結(jié)點，依次進(jìn)行到下一層的結(jié)點，直至到達(dá)葉節(jié)點（即既沒有左子樹也沒有右子樹），然后對于這以后進(jìn)隊的元素則作為右子樹，用相同的方法建樹。　　2.3判定是否為完全二叉樹的算法&

15、lt;p>　　判定完全二叉樹，首先要知道什么是完全二叉樹，對完全二叉樹定義以前，要明白滿二叉樹的定義。一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。對滿二叉樹的你借點進(jìn)行連續(xù)編號，約定編號從根結(jié)點起，自上而下，自左而右。由此引出完全二叉樹的定義。深度為k的，右n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹的編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。所以對于二叉樹的判定，假如某一結(jié)點有右子樹但沒有左子樹則該

16、樹不是完全二叉樹。如果某一結(jié)點沒有右子樹或沒有左子樹，但是其后的結(jié)點有左子樹或右子樹，則該樹不是完全二叉樹。根據(jù)這種判定方法，可以判定其是不是完全二叉樹。　　完全二叉樹定義:　　若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二

17、叉樹。　　完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有N個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹。　　若一棵二叉樹至多只有最下面的兩層上的結(jié)點的度數(shù)可以小于2，并且最下層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹。　　用c語言的方法實現(xiàn)完全二叉樹的判斷算法：

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

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

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

21、>LChild!=NULL&&BiNode.front->next->data->RChild!=NULL)　　//當(dāng)左右孩子均有　　{　　//左右孩子入隊&l

22、t;/p>　　EnterQueue(&BiNode,BiNode.front->next->data->LChild);　　EnterQueue(&BiNode,BiNode.front->next->data->RChild);　　DeleteQueue(&BiNo

23、de);//節(jié)點出隊　　}　　else　　break;　　2.4功能模塊說明

24、　程序各模塊之間的關(guān)系圖:　　圖1程序模塊關(guān)系圖　　2.5編碼設(shè)計　　編碼建立上一步詳細(xì)設(shè)計結(jié)果的基礎(chǔ)上，對編碼進(jìn)行調(diào)試。　　在計算機硬件中，編碼（coding）是指用代碼來表示各組數(shù)據(jù)資料，使其

25、成為可利用計算機進(jìn)行處理和分析的信息。代碼是用來表示事物的記號，它可以用數(shù)字、字母、特殊的符號或它們之間的組合來表示　　將數(shù)據(jù)轉(zhuǎn)換為代碼或編碼字符，并能譯為原數(shù)據(jù)形式。是計算機書寫指令的過程，程序設(shè)計中的一部分。在地圖自動制圖中，按一定規(guī)則用數(shù)字與字母表示地圖內(nèi)容的過程，通過編碼，使計算機能識別地圖的各地理要素。　　n位二進(jìn)制數(shù)可以組合成2的n次方個不同的信息，給每個信息規(guī)定一個具體碼組，這種過程也叫編碼。　　數(shù)字系統(tǒng)中常用的編碼

26、有兩類，一類是二進(jìn)制編碼，另一類是二—十進(jìn)制編碼。　　下面分三種情況討論：　　//左孩子沒有右孩子沒有，繼續(xù)掃描　　if(BiNode.front->next->data->LChild==NULL&&BiNode.front->next->data->RCh

27、ild==NULL)　　{　　DeleteQueue(&BiNode);　　while(BiNode.front!=BiNode.rear)　　{

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

29、}　　return true;　　}　　//左孩子有右孩子沒有，繼續(xù)掃描　　else if(BiNode.front->next->data->LChild!=NULL&&BiN

30、ode.front->next->data->RChild==NULL)　　{　　EnterQueue(&BiNode,BiNode.front->next->data->LChild);　　DeleteQueue(&BiN

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

32、d!=NULL)　　return false;　　DeleteQueue(&BiNode);　　}　　return true;　　}</p&

33、gt;　　//左孩子沒有右孩子有，非完全二叉樹　　else if(BiNode.front->next->data->LChild==NULL&&BiNode.front->next->data->RChild!=NULL)　　return false;&

34、lt;p>　　}　　//隊列的初始化函數(shù)　　int InitQueue(LinkQueue *Q)　　{　　//將Q初始化為一個空的鏈隊列　　Q-&

35、gt;front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));　　if(Q->front!=NULL)　　{　　Q->rear=Q->front;　　Q->fr

36、ont->next=NULL;　　return true;　　}　　else　　return false;//溢出　　}</

37、b>　　//入隊函數(shù)　　int EnterQueue(LinkQueue *Q,BiTree x)　　{　　//將數(shù)據(jù)元素x插入到隊列Q中　　Lin

38、kQueueNode *NewNode;　　NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));　　if(NewNode!=NULL)　　{　　NewNode->data

39、=x;　　NewNode->next=NULL;　　Q->rear->next=NewNode;　　Q->rear=NewNode;　　return true;　　}&

40、lt;/p>　　else　　return false;//溢出　　}　　//出隊操作　　int DeleteQueue(LinkQ

41、ueue *Q)　　{　　//將隊列Q的隊頭元素出隊，并存放到x所指的存儲空間中　　LinkQueueNode *p;　　if(Q->front==Q->rear)　　return

42、 false;//隊列為空均指向頭結(jié)點　　p=Q->front->next;　　Q->front->next=Q->front->next->next;//隊頭元素p出隊　　if(Q->rear==p)//如果隊中只有一個元素p，則p出隊后成為空隊</p&g

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

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

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

46、p>　　2.7程序運行結(jié)果　　用Microsoft Visual C++ 6.0運行代碼：　　系統(tǒng)菜單圖：　　圖2人機交互界面　　按照擴展先序遍歷序列建

47、立二叉樹：　　圖3建立二叉樹　　打印輸入的二叉樹：　　圖4打印輸入的二叉樹　　判斷完全二叉樹：

48、圖5得出結(jié)論　　課程設(shè)計總結(jié)　　在這次課程設(shè)計中，我還學(xué)到了許多東西。對于程序設(shè)計中的錯誤處理也有了更多的認(rèn)識，也掌握了關(guān)于內(nèi)存泄露的相關(guān)知識。而且對于二叉鏈表也有了更好的理解，對于用遞歸法建立二叉樹也有了更多的理解。　　對于程序設(shè)計也有了更好的理解，程序

49、設(shè)計不光只是要得到相應(yīng)的運行結(jié)果就可以的，還有考慮它的健壯性，以及與用戶之間的交流，要能夠直觀的，簡潔的表示該程序的使用方法和功能，而且還要有很好的重復(fù)使用性，這樣的算法才是好的算法。　　當(dāng)然在這方面上我還有很多的不足，需要更多的努力，在反復(fù)實踐過程中不斷地完善自己在這方面的能力。　　這次的設(shè)計，讓我大大地感覺到，對于程序設(shè)計中，對語言再熟悉也比不過在設(shè)

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

51、我仍感慨頗多，從理論到實踐，在這段日子里，可以說得是苦多于甜，但是可以學(xué)到很多很多的東西，同時不僅可以鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。通過這次課程設(shè)計使我懂得了理論與實際相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨立思考的能力。在設(shè)計的過程中遇到問題，可以說得是困難重重，但可喜的是最終都得到了解決。

52、　　參考文獻(xiàn)　　[1]譚浩強編著.C++課程設(shè)計.北京：清華大學(xué)社，2004　　[2]S.B.Lippman，J.Lajoie著.潘愛民譯.C++Primer（3rd Edition）中文版.北京：中國電力出版社，2002　　[3]H

53、.M.Deitel，Paul James Deitel著.薛萬鵬譯.C++程序設(shè)計教程.北京：機械工業(yè)出版社，2000　　[4]Stephen R.Savis著.C++ For Dummies 4th edition，IDG Books Worldwide，Inc.，2002　　[5]Harvey M.Deitel .Jack W.Davidson著.邱

54、仲潘譯.C++大學(xué)教程（第二版）.北京：電子工業(yè)出版社，2002　　[6]James P.Cohoon.Jack W.Davidson著.劉瑞挺等譯.C++程序設(shè)計（第三版）.北京：電子工業(yè)出版社　　[7]Decoder編著.C/C++程序設(shè)計.北京：中國鐵道出版社，2002　　[8]Brian Overland

55、著.董梁等譯.C++語言命令譯解（第二版）.北京：機械工業(yè)出版社，2002　　[9] H.M.Deitel，Paul James Deitel著.薛萬鵬譯.C/C++程序設(shè)計大全.北京：機械工業(yè)出版社.1997　　[10]Al Strevens,Clayton Walnum著.林麗閩等譯.標(biāo)準(zhǔn)C++寶典.北京：電子工業(yè)出版社.2001

56、　　[11]Michael J.Young著.Mastering Visual C++6.0 Sybex Inc.1999　　[12]Leen Ammeraal著.劉瑞挺等譯.C++程序設(shè)計教程（第三版）.北京：zhongguo 鐵道出版社，2003　　[13] 呂鳳翥著. C++語言程序設(shè)計.北方交通大學(xué)出版社，2003</

57、p>　　[14] 袁啟昌著.C++語言程序設(shè)計.清華大學(xué)出版社,2004　　[15] 劉振安，劉燕君，孫忱C++語言課程設(shè)計.機械工業(yè)出版社，2007　　[16] 楊進(jìn)才，沈顯君，劉蓉編.C++語言程序設(shè)計教程.清華大學(xué)出版社,2006　　[17] 宋振會著. C++語言編程基礎(chǔ)教程.

58、清華大學(xué)出版社,2005　　附錄　　源代碼：　　//判斷完全二叉樹算法描述　　#include<stdio.h>　　#include<s

59、tdlib.h>　　#define true 1　　#define false 0　　//二叉樹數(shù)據(jù)結(jié)構(gòu)　　typedef struct BiTNode　　{</

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

61、;/p>　　{　　BiTree data;　　struct QueueNode *next;　　}LinkQueueNode;　　typedef struct &l

62、t;b>　　{　　LinkQueueNode *front;　　LinkQueueNode *rear;　　}LinkQueue;　　//函數(shù)聲明　　void Pri

63、nt(BiTree *root);　　void Choose(int choice,BiTree *root);　　void ReadPreOrder(BiTree *root);　　void PrintPreOrder(BiTree root);　　int Comple

64、teBinaryTree(BiTree root);　　int InitQueue(LinkQueue *Q);　　int EnterQueue(LinkQueue *Q,BiTree x);　　int DeleteQueue(LinkQueue *Q);

65、;　　//主函數(shù)　　int main()　　{　　BiTree root;　　root=NULL;//初始化無頭結(jié)點　　system("color b"

66、;);　　Print(&root);　　while(true)　　{　　printf("Press enter to continue.........");　　g

67、etchar();　　getchar();　　system("cls");　　Print(&root);　　}　　return 0;</b&

68、gt;　　}　　void Print(BiTree *root)　　{　　int choice;　　printf("--------------

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

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

71、　printf("---------------------\n");　　printf("請選擇你要的操作:");　　scanf("%d",&choice);　　getchar();//此處getchar存儲回車，避免對后面函數(shù)的影響！（很重要！

72、）　　Choose(choice,root);　　}　　void Choose(int choice,BiTree *root)　　{　　switch(c

73、hoice)　　{　　case 1:　　ReadPreOrder(root);　　break;

74、case 2:　　PrintPreOrder(*root);　　printf("\n");　　break;　　case 3:<

75、p>　　if(CompleteBinaryTree(*root))　　{　　printf("當(dāng)前二叉樹是完全二叉樹！\n");　　}　　else{<

76、;/b>　　printf("當(dāng)前二叉樹不是完全二叉樹！\n");　　}　　break;　　default:&

77、lt;p>　　exit(0);　　}　　}　　void ReadPreOrder(BiTree *root)　　//先序遍歷二叉樹，root為指向二叉樹

78、（或某一子樹）根結(jié)點的指針　　{　　char ch;　　ch=getchar();//使用getchar輸入時必須謹(jǐn)記前面有沒有多余的回車　　if(ch=='.')</p&g

79、t;　　{　　(*root)=NULL;　　}　　else　　{<p

80、>　　(*root)=(BiNode *)malloc(sizeof(BiNode));　　(*root)->data=ch;　　ReadPreOrder(&((*root)->LChild));　　ReadPreOrder(&((*root)->RChild));<

81、/p>　　}　　}　　void PrintPreOrder(BiTree root)　　{　　if(root!=NULL)<

82、/p>　　{　　printf("%c",(root)->data);　　PrintPreOrder(root->LChild);　　PrintPreOrder(root->RChild);

83、　　}　　else 　　{　　printf(".");　　}

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

85、pleteBinaryTree(BiTree root)　　{　　int flag;　　LinkQueue BiNode;//創(chuàng)建隊列　　InitQueue(&BiNode);//初始化隊

86、列　　EnterQueue(&BiNode,root);//將根節(jié)點入隊　　while(BiNode.front!=BiNode.rear)//當(dāng)隊列不為空時進(jìn)行廣度優(yōu)先掃描二叉樹　　//當(dāng)發(fā)現(xiàn)非正常節(jié)點時跳出循環(huán)　　{<

87、;/p>　　if(BiNode.front->next->data->LChild!=NULL&&BiNode.front->next->data->RChild!=NULL)　　//當(dāng)左右孩子均有　　{</b&g

88、t;　　//左右孩子入隊　　EnterQueue(&BiNode,BiNode.front->next->data->LChild);　　EnterQueue(&BiNode,BiNode.front->next->data-&g

89、t;RChild);　　DeleteQueue(&BiNode);//節(jié)點出隊　　}　　else　　break;<p&g

90、t;　　}//下面分三種情況討論　　//左孩子沒有右孩子沒有，繼續(xù)掃描　　if(BiNode.front->next->data->LChild==NULL&&BiNode.front->next->data->RChild==NULL)

91、{　　DeleteQueue(&BiNode);　　while(BiNode.front!=BiNode.rear)　　{　　if(BiNode.front->next->data->LC

92、hild!=NULL || BiNode.front->next->data->RChild!=NULL)　　return false;　　DeleteQueue(&BiNode);　　}　　return t

93、rue;　　}　　//左孩子有右孩子沒有，繼續(xù)掃描　　else if(BiNode.front->next->data->LChild!=NULL&&BiNode.front->next->data->RChild==NU

94、LL)　　{　　EnterQueue(&BiNode,BiNode.front->next->data->LChild);　　DeleteQueue(&BiNode);　　while(BiNode.f

95、ront!=BiNode.rear)　　{　　if(BiNode.front->next->data->LChild!=NULL || BiNode.front->next->data->RChild!=NULL)　　return fals

96、e;　　DeleteQueue(&BiNode);　　}　　return true;　　}　　//左孩子沒有右孩子有，非完全二叉樹</p&

97、gt;　　else if(BiNode.front->next->data->LChild==NULL&&BiNode.front->next->data->RChild!=NULL)　　return false;　　}

98、　　//隊列的初始化函數(shù)　　int InitQueue(LinkQueue *Q)　　{　　//將Q初始化為一個空的鏈隊列　　Q->front=(LinkQueueNode *)malloc(sizeof(Li

99、nkQueueNode));　　if(Q->front!=NULL)　　{　　Q->rear=Q->front;　　Q->front->next=NULL;　　r

100、eturn true;　　}　　else　　return false;//溢出　　}　　//入隊函

101、數(shù)　　int EnterQueue(LinkQueue *Q,BiTree x)　　{　　//將數(shù)據(jù)元素x插入到隊列Q中　　LinkQueueNode *NewNode;

102、　NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));　　if(NewNode!=NULL)　　{　　NewNode->data=x;　　NewNode->next

103、=NULL;　　Q->rear->next=NewNode;　　Q->rear=NewNode;　　return true;　　}　　else</b&

104、gt;　　return false;//溢出　　}　　//出隊操作　　int DeleteQueue(LinkQueue *Q)　　{&

105、lt;/b>　　//將隊列Q的隊頭元素出隊，并存放到x所指的存儲空間中　　LinkQueueNode *p;　　if(Q->front==Q->rear)　　return false;//隊列為空均指向頭結(jié)點

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

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

溫馨提示

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

課程設(shè)計---完全二叉樹的判斷

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計---完全二叉樹的判斷

文檔簡介

溫馨提示

最新文檔

評論

免費下載