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

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

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

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

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

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

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

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

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

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

10、的尾指針*/queue;4.4函數(shù)原型int CreateQueue(queue *q);/*創(chuàng)建隊列*/int EnQueue(queue *q, QueueElemtype c);/*向隊尾插入元素c*/Statu DeQueue(queue *q, QueueElemtype *reb);/*隊頭元素出隊用reb返回其值*/Statu CreateBitTree(BitTree *T);/*初始化二叉樹*/Statu LayerTravelBitTree(BitTree T);/*層次遍歷二叉樹*/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);/*初始化二叉樹*/printf("Layer order travel the tree:n");/*層次遍歷二叉樹*/LayerTravelBitTree(t);/*層次遍歷二叉樹*/4.6初始化二叉樹 Statu CreateBitTree(BitTree *T)/*初始化二叉樹*/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)輸入左子樹*/ printf("Create right sub tree.<"); CreateBitTree(&(*T)->rchild);/*遞歸循環(huán)輸入右子樹*/ return TRUE;4.7層次遍歷二叉樹 Statu LayerTravelBitTree(BitTree T)/*層次遍歷二叉樹*/queue tq;/*隊列tq*/QueueElemtype res;/*用來返回對頭元素*/CreateQueue(&tq);/*創(chuàng)建隊列*/EnQueue(&tq,T);/*將T插入隊尾*/wh

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

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

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