按層次輸入建立二叉樹

1、學(xué)號：012091034001課程設(shè)計(jì)題目按層次輸入建立二叉樹學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)一計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)班級計(jì)算機(jī)0909姓名樊旭指導(dǎo)教師張霞2011年 07月 03日目_錄課 程 設(shè) 計(jì) 任 務(wù)書. 2按層 次建立二 叉樹 的 實(shí) TOC o 1-5 h z 現(xiàn)3一、問題描述3二、設(shè)計(jì)31、存儲結(jié)構(gòu)設(shè)計(jì)32、主要算法設(shè)計(jì)33、測試用例設(shè)計(jì)5三、調(diào)試報告5四、經(jīng)驗(yàn)和體會6五、源程序清單和運(yùn)行結(jié)果6成績評定表10課程設(shè)計(jì)任務(wù)書學(xué)生姓名：旭專業(yè)班級：0909班指導(dǎo)教師：張 霞工作單位： 計(jì)算機(jī)科學(xué)系題目：按層次輸入建立二叉樹初始條件：按層次輸入擴(kuò)展的完全二叉樹中的結(jié)點(diǎn)，建立一棵二叉樹。（1

2、）用二叉鏈表作存儲結(jié)構(gòu)；（2）對建立的二叉樹給出后序遍歷的結(jié)果；（3）測試用例自己設(shè)計(jì)；要求完成的主要任務(wù):（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰 寫等具體要求）課程設(shè)計(jì)報告按學(xué)校規(guī)定格式用A4紙打?。〞鴮懀?，并應(yīng)包含如下內(nèi)容：1、問題描述簡述題目要解決的問題是什么。2、設(shè)計(jì)存儲結(jié)構(gòu)設(shè)計(jì)、主要算法設(shè)計(jì)（用類C語言或用框圖描述）、測試用 例設(shè)計(jì)；3、調(diào)試報告調(diào)試過程中遇到的問題是如何解決的；對設(shè)計(jì)和編碼的討論和分析。4、經(jīng)驗(yàn)和體會（包括對算法改進(jìn)的設(shè)想）5、附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測試數(shù)據(jù)和運(yùn)行輸出，6、設(shè)計(jì)報告、程序不得相互抄

3、襲和拷貝；若有雷同，則所有雷同者成績 均為0分。時間安排：1、第19周完成。2、7月1日14： 00到計(jì)算中心檢查程序、交課程設(shè)計(jì)報告、源程序（CD 盤）。指導(dǎo)教師簽名：年 月 日系主任（或責(zé)任教師）簽名：年 月 日按層次輸入建立二叉樹的實(shí)現(xiàn)一、問題描述按層次輸入擴(kuò)展的完全二叉樹中的結(jié)點(diǎn)，建立一棵二叉樹。（1）用二叉鏈表作存儲結(jié)構(gòu)；（2）對建立的二叉樹給出后序遍歷的結(jié)果；（3）測試用例自己設(shè)計(jì)；二、設(shè)計(jì)1、存儲結(jié)構(gòu)設(shè)計(jì)由問題采用二叉鏈表存儲結(jié)構(gòu)為：typedef struct btnode（char cdata;struct btnode *lchild,*rchild;BTNode;BTNo

4、de *Create_BiTree（）2、主要算法設(shè)計(jì)(1)函數(shù)BTNode *Create_BiTree()實(shí)現(xiàn)對二叉樹的建立，同時使用輔助數(shù)組建立二叉樹。定義頂點(diǎn)編號整型i以0作 為結(jié)束條件，以及頂點(diǎn)信息字符型ch以#作為結(jié)束條件。輔助數(shù)組p MAXSIZE】各項(xiàng)則指向依次輸入的數(shù)據(jù)。BTNode *Create_BiTree()(int i,j;char ch;BTNode *s,*t,*pMAXSIZE;printf(輸入頂點(diǎn)編號及信息，輸入0和#結(jié)束:i,ch);scanf(%d,%c,&i,&ch);while(i=0|ch=#) break;while(i!=0 &ch!=#)(

5、s=(BTNode *)malloc(sizeof(BTNode);s-cdata=ch;s-lchild=s-rchild=NULL;pi=s;if(i=1) t=s;elsej=i/2;if(i%2=0) pj-lchild=s;else pj-rchild=s;printf(輸入頂點(diǎn)編號及信息，輸入0和#結(jié)束:i,ch);scanf(%d,%c,&i,&ch);return t;(2)函數(shù) void Postorder(BTNode *bt)實(shí)現(xiàn)二叉樹的后序遍歷。使用遞歸左右子樹完成輸出。void Postorder(BTNode *bt)/*后序遞歸遍歷*/if(bt)Postorde

6、r(bt-lchild);Postorder(bt-rchild);printf(%c,bt-cdata);/* Postorder*/3、測試用例設(shè)計(jì)假設(shè)有完全一棵二叉樹，按層次遍歷為：g c f a b de，現(xiàn)按 此程序建立二叉樹按后序輸出結(jié)果應(yīng)為：a b c d e f g則正確。三、調(diào)試報告1、剛開始設(shè)想建立二叉樹時，在生成新節(jié)點(diǎn)時申請一個 輔助變量，下一次再申請一個，但是這樣的設(shè)計(jì)浪費(fèi) 存儲空間并且不易于操作，更正為輔助數(shù)組即解決這 一問題。2、判斷輸入節(jié)點(diǎn)i是上一節(jié)點(diǎn)j（j=i/2）的左右孩子時， 如果i%2=0那么說明節(jié)點(diǎn)i是j的左孩子，則 pj-lchild=s，否則 pj-

7、rchild=s 即可。3、習(xí)慣性用#include,但由于該頭文件中不 包括malloc函數(shù)和printf及scanf函數(shù)，所以不能運(yùn) 行。將其更正為#include和#include 后正確。四、經(jīng)驗(yàn)和體會我這次的課程設(shè)計(jì)相對簡單，只需建立一棵二叉樹并后 序輸出就可以了，因此總體上并無多大難度，但是在這種小 實(shí)驗(yàn)上調(diào)試過程就有了較多錯誤，雖然很多錯誤都是由于粗 心造成的，但是這也十分提醒我在以后的實(shí)驗(yàn)和工作中得多 注意小細(xì)節(jié)，不要粗心大意，不然到頭來費(fèi)時費(fèi)力。此外， 在生成節(jié)點(diǎn)時選擇正確和效率的算法和技巧也十分重要，在 程序的時間和空間上找一個折衷的思想對其效率有很大提 高，因此也要引起注

8、意。相信通過這次較正式的形式對程序的分析，會對我以后的學(xué)習(xí)起到促進(jìn)和補(bǔ)充的作用。五、源程序清單和運(yùn)行結(jié)果#include#include #define MAXSIZE 20typedef struct btnode(char cdata;struct btnode *lchild,*rchild;BTNode;BTNode *Create_BiTree()/二 叉樹的建立用輔助數(shù)組建立二叉樹int i,j;char ch;BTNode *s,*t,*pMAXSIZE;printf(輸入頂點(diǎn)編號及信息，輸入0和#結(jié)束:i,ch);scanf(%d,%c,&i,&ch);while(i=0|ch

9、=#) break;while(i!=0 &ch!=#)/建立二叉樹的存儲結(jié)構(gòu)s=(BTNode *)malloc(sizeof(BTNode);s-cdata=ch;s-lchild=s-rchild=NULL;pi=s;if(i=1) t=s;/判斷輸入結(jié)點(diǎn)是根結(jié)點(diǎn)、左孩子還是右孩子elsej=i/2;if(i%2=0) pj-lchild=s;else pj-rchild=s;printf(輸入頂點(diǎn)編號及信息，輸入0和#結(jié)束:i,ch);scanf(%d,%c,&i,&ch);return t;/ Create_BiTree1void Postorder(BTNode *bt)/*后序遞歸遍歷*/if(bt)Postorder(bt-lchild);Postorder(bt-rchild);printf(%c,bt-cdata);/ Postordervoid main()BTNode *t;t=Create_BiTree();printf(后序遍歷結(jié)果:n); Postorder(t);運(yùn)行結(jié)果截圖:運(yùn)行結(jié)果正確無誤。本科生課程設(shè)計(jì)成績評定表班級：計(jì)算機(jī)009班 姓名：旭 學(xué)號：012091034001序號評分項(xiàng)目滿分實(shí)得分1學(xué)習(xí)態(tài)