基于層次遍歷的二叉樹(shù)算法設(shè)計(jì)

1、題 目: 基于層次遍歷的二叉樹(shù)算法設(shè)計(jì)初始條件：理論：學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課程，掌握了基本的數(shù)據(jù)結(jié)構(gòu)和常用的算法；實(shí)踐：計(jì)算機(jī)技術(shù)系實(shí)驗(yàn)室提供計(jì)算機(jī)及軟件開(kāi)發(fā)環(huán)境。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書撰寫等具體要求）1、系統(tǒng)應(yīng)具備的功能：（1）建立二叉樹(shù)（2）按層次遍歷二叉樹(shù)2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；3、主要算法設(shè)計(jì)；4、編程及上機(jī)實(shí)現(xiàn)；5、撰寫課程設(shè)計(jì)報(bào)告，包括：（1）設(shè)計(jì)題目；（2）摘要和關(guān)鍵字；（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、程序?qū)崿F(xiàn)及測(cè)試、不足之處、設(shè)計(jì)體會(huì)；（4）結(jié)束語(yǔ)；（5）參考文獻(xiàn)。時(shí)間安排： 2007年7月2日7日 （第18周）7月2日

2、查閱資料7月3日 系統(tǒng)設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)7月4日-5日 編程并上機(jī)調(diào)試7月6日 撰寫報(bào)告7月7日 驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書。指導(dǎo)教師簽名： 2007年7月2日系主任（或責(zé)任教師）簽名： 2007年7月2日 基于層次遍歷的二叉樹(shù)算法設(shè)計(jì)摘要：本程序設(shè)計(jì)實(shí)現(xiàn)二叉樹(shù)的層次遍歷，該程序主要部分包括：創(chuàng)建二叉樹(shù)，按層次遍歷二叉樹(shù)。.關(guān)鍵字：二叉樹(shù)，隊(duì)列，二叉鏈表，數(shù)據(jù)結(jié)構(gòu) .0.引言： 樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中一樹(shù)和二叉樹(shù)最重要。樹(shù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)夠可以用樹(shù)來(lái)形象表示。樹(shù)在計(jì)算機(jī)領(lǐng)域中也得到了廣泛應(yīng)用，如在編譯程序中，可以用樹(shù)來(lái)表示源

3、程序的語(yǔ)法結(jié)構(gòu)。二叉樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)，對(duì)它進(jìn)行操作時(shí)總需要對(duì)每個(gè)數(shù)據(jù)逐一進(jìn)行操作，這樣就存在一個(gè)操作順序問(wèn)題，由此提出了二叉樹(shù)的遍歷操作問(wèn)題，所謂遍歷二叉樹(shù)就是按某種順序訪問(wèn)二叉樹(shù)中某個(gè)結(jié)點(diǎn)一次且僅一次的過(guò)程，這里的訪問(wèn)可以是輸出.比較.更新.查看元素內(nèi)容等各種操作。1.需求分析：1.1行輸入數(shù)據(jù)構(gòu)造二叉樹(shù)。1.2用隊(duì)列存儲(chǔ)二叉樹(shù)結(jié)點(diǎn)。1.3算法實(shí)現(xiàn)層次遍歷。1.4實(shí)現(xiàn)過(guò)程: A：初始，系統(tǒng)開(kāi)始運(yùn)行后，要先構(gòu)造二叉樹(shù)，先輸入根結(jié)點(diǎn)數(shù)據(jù)信息。 B：根據(jù)提示信息輸入其左子樹(shù)，若沒(méi)有左子樹(shù)則輸入“-1”。 C：根據(jù)提示信息輸入其右子樹(shù)，若沒(méi)有右子樹(shù)則輸入“-1”。 D：在二叉樹(shù)構(gòu)造完成之后程序

4、會(huì)自動(dòng)按層次遍歷二叉樹(shù)，并且輸出相應(yīng)結(jié)點(diǎn)數(shù)據(jù)信息。 E：在完成上述過(guò)程之后按任意鍵結(jié)束程序。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：2.1樹(shù)的鏈?zhǔn)酱鎯?chǔ)typedef struct Bitnode/*樹(shù)的鏈?zhǔn)酱鎯?chǔ)*/BitTreeElementType data;struct Bitnode *lchild;/*左孩子 */struct Bitnode *rchild;/*右孩子*/BTnode,*BitTree;2.2隊(duì)列定義QueueElemtype dataQUEUESIZE;int front;/*隊(duì)列的頭指針*/int rear;/*隊(duì)列的尾指針*/queue;3.算法設(shè)計(jì)3.1主函數(shù)模塊main()“輸入

5、結(jié)點(diǎn)數(shù)據(jù)”；初始化二叉樹(shù)；“層次遍歷二叉樹(shù)”；層次遍歷二叉樹(shù)；3.2初始化二叉樹(shù)模塊Statu CreateBitTree(BitTree *T)為樹(shù)指針T分配空間；輸出“輸入數(shù)據(jù)”；存儲(chǔ)輸入數(shù)據(jù)；if ( 出入數(shù)據(jù)=空字符)結(jié)點(diǎn)不存儲(chǔ)信息；else 結(jié)點(diǎn)存儲(chǔ)輸入的信息； 輸出“創(chuàng)建左子樹(shù)”； CreateBitTree(&(*T)->lchild); 輸出“創(chuàng)建右子樹(shù)”； CreateBitTree(&(*T)->rchild);3.3層次遍歷二叉樹(shù)模塊Statu LayerTravelBitTree(BitTree T)創(chuàng)建隊(duì)列tq；向隊(duì)列tq尾插入T；whil

6、e ( 隊(duì)頭非空時(shí)) 訪問(wèn)隊(duì)頭元素； 將樹(shù)左子樹(shù)插入隊(duì)尾； 將樹(shù)右子樹(shù)插入隊(duì)尾；3.4創(chuàng)建隊(duì)列模塊int CreateQueue(queue *q)對(duì)頭指針和隊(duì)尾指針相等；3.5插入隊(duì)列元素模塊int EnQueue(queue *q, QueueElemtype c)隊(duì)尾指針加1；if (隊(duì)尾指針超過(guò)隊(duì)列長(zhǎng)度) 輸出“OVERFLOW”； 退出程序；將c存為隊(duì)尾元素；3.6刪除隊(duì)列元素模塊Statu DeQueue(queue *q, QueueElemtype *ret)if (隊(duì)頭指針和隊(duì)尾指針相等) 返回錯(cuò)誤；頭指針加1；將隊(duì)頭元素存于ret中；3.7訪問(wèn)結(jié)點(diǎn)模塊Statu Visit

7、Data(BitTreeElementType data)輸出結(jié)點(diǎn)存儲(chǔ)的信息；3.7主要技術(shù)說(shuō)明程序用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和隊(duì)列分別存儲(chǔ)二叉樹(shù)和二叉樹(shù)的結(jié)點(diǎn)。一方面采用隊(duì)列存儲(chǔ)結(jié)點(diǎn)是結(jié)合層次遍歷二叉樹(shù)和隊(duì)列“先進(jìn)先出”的特點(diǎn)綜合考慮的，因?yàn)閷哟伪闅v即從上到下從左到右依次遍歷二叉樹(shù)結(jié)點(diǎn)，而隊(duì)列恰好可以從上到下從左到右順序進(jìn)隊(duì)然后順序出隊(duì)，符合設(shè)計(jì)的要求。另一方面采用二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)而非順序存儲(chǔ)結(jié)構(gòu)是因?yàn)闃?gòu)造二叉樹(shù)需用到遞歸算法，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)容易實(shí)現(xiàn)。初始化二叉樹(shù)的實(shí)現(xiàn)：首先輸入根結(jié)點(diǎn)，若根結(jié)點(diǎn)非空則將其設(shè)為樹(shù)的根結(jié)點(diǎn)，否則返回“FALSE”；其次輸入結(jié)點(diǎn)左子樹(shù)，若非空則將其存為上一結(jié)點(diǎn)的左子樹(shù)，

8、否則輸入右子樹(shù)；若非空則將其存為上一結(jié)點(diǎn)的右子樹(shù)，否則結(jié)束，完成二叉樹(shù)初始化。遞歸重復(fù)以上操作即可初始化二叉樹(shù)。本系統(tǒng)對(duì)用戶在操作時(shí)可能進(jìn)行的錯(cuò)誤和違規(guī)操作，給出了基本的提示信息，以便用戶在非法操作后得到意想不到的結(jié)果。4.程序?qū)崿F(xiàn)4.1庫(kù)函數(shù)#include<stdio.h> /*I/O函數(shù)*/#include "conio.h"4.2定義宏#define QUEUESIZE 100 /*隊(duì)列初始容量*/#define TRUE 1#define FALSE !TRUE#define Statu int#define BitTreeElementType in

9、t#define SHUJU "%d"#define END -14.3定義全局變量typedef struct Bitnode/*樹(shù)的鏈?zhǔn)酱鎯?chǔ)*/BitTreeElementType data;struct Bitnode *lchild;/*左孩子 */struct Bitnode *rchild;/*右孩子*/BTnode,*BitTree;typedef BitTree QueueElemtype；typedef struct/*定義數(shù)據(jù)結(jié)構(gòu)*/QueueElemtype dataQUEUESIZE;int front;/*隊(duì)列的頭指針*/int rear;/*隊(duì)列

10、的尾指針*/queue;4.4函數(shù)原型int CreateQueue(queue *q);/*創(chuàng)建隊(duì)列*/int EnQueue(queue *q, QueueElemtype c);/*向隊(duì)尾插入元素c*/Statu DeQueue(queue *q, QueueElemtype *reb);/*隊(duì)頭元素出隊(duì)用reb返回其值*/Statu CreateBitTree(BitTree *T);/*初始化二叉樹(shù)*/Statu LayerTravelBitTree(BitTree T);/*層次遍歷二叉樹(shù)*/4.5主函數(shù)main()BitTree t;printf("Input data

11、 to create bittree and '");printf(SHUJU,END);printf("' will make null tree.n");/*輸入根結(jié)點(diǎn) */CreateBitTree(&t);/*初始化二叉樹(shù)*/printf("Layer order travel the tree:n");/*層次遍歷二叉樹(shù)*/LayerTravelBitTree(t);/*層次遍歷二叉樹(shù)*/4.6初始化二叉樹(shù) Statu CreateBitTree(BitTree *T)/*初始化二叉樹(shù)*/BitTreeElem

12、entType inputdata;*T = (BitTree )malloc(sizeof(BTnode);printf("Enter Data:");/*輸入數(shù)據(jù)*/fflush(stdin);scanf(SHUJU,&inputdata);if ( inputdata = END) *T = NULL; return FALSE;else (*T)->data = inputdata;/*將輸入的數(shù)據(jù)存入結(jié)點(diǎn)*/ printf("Create left sub tree.<"); CreateBitTree(&(*T)-

13、>lchild);/*遞歸循環(huán)輸入左子樹(shù)*/ printf("Create right sub tree.<"); CreateBitTree(&(*T)->rchild);/*遞歸循環(huán)輸入右子樹(shù)*/ return TRUE;4.7層次遍歷二叉樹(shù) Statu LayerTravelBitTree(BitTree T)/*層次遍歷二叉樹(shù)*/queue tq;/*隊(duì)列tq*/QueueElemtype res;/*用來(lái)返回對(duì)頭元素*/CreateQueue(&tq);/*創(chuàng)建隊(duì)列*/EnQueue(&tq,T);/*將T插入隊(duì)尾*/wh

14、ile ( DeQueue(&tq,&res) = TRUE)/*當(dāng)隊(duì)頭元素不空時(shí)執(zhí)行while循環(huán)*/ if (res) VisitData(res->data);/*訪問(wèn)隊(duì)頭元素*/ EnQueue(&tq,res->lchild);/*將結(jié)點(diǎn)左孩子插入隊(duì)尾*/ EnQueue(&tq,res->rchild);/*將結(jié)點(diǎn)右孩子插入隊(duì)尾*/ 4.8創(chuàng)建空隊(duì)列int CreateQueue(queue *q)q->front = -1;q->rear = -1;4.9隊(duì)尾插入元素（結(jié)點(diǎn)入隊(duì)）int EnQueue(queue *q

15、, QueueElemtype c)/*將元素c插入隊(duì)尾*/q->rear+;/*尾指針加1*/if (q->rear >= QUEUESIZE)/*若尾指針超出隊(duì)列長(zhǎng)度則提示錯(cuò)誤*/ printf("Queue overflow!n"); exit(0);q->dataq->rear = c;return 1;4.10隊(duì)頭元素出隊(duì)Statu DeQueue(queue *q, QueueElemtype *ret)/*隊(duì)頭元素出隊(duì)并用ret返回其值*/if (q->front = q->rear)/*若隊(duì)列為空，則返回錯(cuò)誤提示*/

16、 return FALSE;q->front+;/*頭指針加1*/*ret = q->dataq->front;return TRUE;4.11訪問(wèn)結(jié)點(diǎn)Statu VisitData(BitTreeElementType data)printf(SHUJU,data);printf("n");return TRUE;4.12程序運(yùn)行結(jié)果主界面：結(jié)果分析：實(shí)驗(yàn)結(jié)果的排序完全正確。程序可以實(shí)現(xiàn)用戶自己構(gòu)造二叉樹(shù)，然后實(shí)現(xiàn)對(duì)二叉樹(shù)的層次遍歷。程序基本上滿足了算法設(shè)計(jì)要求，但是仍有地方值得提高，仍需完善。5.設(shè)計(jì)體會(huì) 通過(guò)課程設(shè)計(jì)自己對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程有了更深一層的了解，意識(shí)到了數(shù)據(jù)結(jié)構(gòu)的重要性，同時(shí)也對(duì)c語(yǔ)言的掌握更進(jìn)一步，熟悉了對(duì)于指針，鏈表，隊(duì)列等的操作，對(duì)程序設(shè)計(jì)的過(guò)程也有了自己的一些理解：首先，要對(duì)到手的問(wèn)題要認(rèn)真思考，如何實(shí)現(xiàn)，用何種方法實(shí)現(xiàn)，力求最簡(jiǎn)，在保證正確性的基礎(chǔ)上提高程序效率；其次，確定了實(shí)現(xiàn)的方法之后就要用程序語(yǔ)言將想法表示出來(lái)；最后，進(jìn)行調(diào)試和排錯(cuò)，一個(gè)有效的方法是在前面遇到問(wèn)題時(shí)在