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

1、<p>　　《完全二叉樹的判斷》</p><p><b>　　課程設(shè)計(jì)論文</b></p><p>　　學(xué)生姓名 </p><p>　　學(xué) 號(hào) </p><p>　　所屬學(xué)院 信息工程學(xué)院 </p><p>　　專

2、 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　班 級(jí) 計(jì)算機(jī) </p><p>　　指導(dǎo)教師 </p><p>　　教師職稱 講師 </p><p><b>　　目 錄</b></p><p><b>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、de);//節(jié)點(diǎn)出隊(duì)</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　break;</b></p><p><b>　　2.4功能模塊說明</b></p><p>　

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

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

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

27、ild==NULL)</p><p><b>　　{</b></p><p>　　DeleteQueue(&BiNode);</p><p>　　while(BiNode.front!=BiNode.rear)</p><p><b>　　{</b></p><p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

64、teBinaryTree(BiTree root);</p><p>　　int InitQueue(LinkQueue *Q);</p><p>　　int EnterQueue(LinkQueue *Q,BiTree x);</p><p>　　int DeleteQueue(LinkQueue *Q);</p><p><b>

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

66、;);</p><p>　　Print(&root);</p><p>　　while(true)</p><p><b>　　{</b></p><p>　　printf("Press enter to continue.........");</p><p>　　g

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

68、gt;</p><p><b>　　}</b></p><p>　　void Print(BiTree *root)</p><p><b>　　{</b></p><p>　　int choice;</p><p>　　printf("--------------

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

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

71、　printf("---------------------\n");</p><p>　　printf("請選擇你要的操作:");</p><p>　　scanf("%d",&choice);</p><p>　　getchar();//此處getchar存儲(chǔ)回車，避免對(duì)后面函數(shù)的影響?。ê苤匾?/p>

72、）</p><p>　　Choose(choice,root);</p><p><b>　　}</b></p><p>　　void Choose(int choice,BiTree *root)</p><p><b>　　{</b></p><p>　　switch(c

73、hoice)</p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p>　　ReadPreOrder(root);</p><p><b>　　break;</b></p><p><b>　　

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

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

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

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

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

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

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

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

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

83、<p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　printf(".");</p><p><b>　　}</b></p>

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

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

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

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

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

89、t;RChild);</p><p>　　DeleteQueue(&BiNode);//節(jié)點(diǎn)出隊(duì)</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　break;</b></p><p&g

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

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

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

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

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

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

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

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

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

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

100、eturn true;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　return false;//溢出</p><p><b>　　}</b></p><p><b>　　//入隊(duì)函

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

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

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

104、gt;</p><p>　　return false;//溢出</p><p><b>　　}</b></p><p><b>　　//出隊(duì)操作</b></p><p>　　int DeleteQueue(LinkQueue *Q)</p><p><b>　　{&

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

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