二叉樹的遍歷和應(yīng)用

內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)說明書PAGE13內(nèi)蒙古科技大學(xué)本科生課程設(shè)計(jì)說明書題目：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)——二叉樹的遍歷和應(yīng)用學(xué)生姓名：學(xué)號(hào)：專業(yè)：班級(jí)：指導(dǎo)教師：2013年5月29日內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目二叉樹的遍歷和應(yīng)用指導(dǎo)教師時(shí)間2013.6.20——2013.6.30一、教學(xué)要求1.掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能3.提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力4.訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)二、設(shè)計(jì)資料及參數(shù)每個(gè)學(xué)生在教師提供的課程設(shè)計(jì)題目中任意選擇一題，獨(dú)立完成，題目選定后不可更換。二叉樹的遍歷和應(yīng)用以二叉鏈表表示二叉樹，在此基礎(chǔ)上實(shí)現(xiàn)對(duì)二叉樹的遍歷和應(yīng)用。要求設(shè)計(jì)類（或類模板）來描述二叉樹，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)：創(chuàng)建二叉樹輸出二叉樹二叉樹的先序、中序、后序遍歷二叉樹的按層遍歷統(tǒng)計(jì)二叉樹的葉子結(jié)點(diǎn)、計(jì)算二叉樹的深度并設(shè)計(jì)主函數(shù)測試該類（或類模板）。三、設(shè)計(jì)要求及成果1.分析課程設(shè)計(jì)題目的要求

2.寫出詳細(xì)設(shè)計(jì)說明

3.編寫程序代碼，調(diào)試程序使其能正確運(yùn)行

4.設(shè)計(jì)完成的軟件要便于操作和使用

5.設(shè)計(jì)完成后提交課程設(shè)計(jì)報(bào)告四、進(jìn)度安排資料查閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開發(fā)與測試（5天）編寫課程設(shè)計(jì)說明書和驗(yàn)收（2天）五、評(píng)分標(biāo)準(zhǔn)1.根據(jù)平時(shí)上機(jī)考勤、表現(xiàn)和進(jìn)度，教師將每天點(diǎn)名和檢查2.根據(jù)課程設(shè)計(jì)完成情況，必須有可運(yùn)行的軟件。

3.根據(jù)課程設(shè)計(jì)報(bào)告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。4.根據(jù)答辯的情況，應(yīng)能夠以清晰的思路和準(zhǔn)確、簡練的語言敘述自己的設(shè)計(jì)和回答教師的提問六、建議參考資料1．《數(shù)據(jù)結(jié)構(gòu)（C語言版）》嚴(yán)蔚敏、吳偉民主編清華大學(xué)出版社2004.112．《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編（用C/C++描述）》，李建學(xué)等編著，清華大學(xué)出版社2007.23.《數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC++語言描述》，殷人昆主編，

清華大學(xué)出版社2007.6目錄內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)任務(wù)書 I目錄 III第一章需求分析 41.1 課程設(shè)計(jì)目的 41.2 任務(wù)概述 41.3 課程設(shè)計(jì)內(nèi)容 4第二章 概要設(shè)計(jì) 62.1 設(shè)計(jì)思想 62.2 二叉樹的遍歷 62.3 運(yùn)行界面設(shè)計(jì) 7第三章 詳細(xì)設(shè)計(jì) 83.1 二叉樹的生成 83.2 二叉樹的先序遍歷 83.3 二叉樹的中序遍歷 93.4 二叉樹的后續(xù)遍歷 93.5 主程序的設(shè)計(jì) 9第四章 測試分析 124.1 二叉樹的建立 124.2 二叉樹的先序、中序、后序遍歷 12第五章 課程設(shè)計(jì)總結(jié) 14附錄：程序代碼 15致謝 20第一章需求分析課程設(shè)計(jì)目的培養(yǎng)學(xué)生用學(xué)到的書本知識(shí)解決實(shí)際問題的能力；培養(yǎng)實(shí)際工作所需要的動(dòng)手能力；培養(yǎng)學(xué)生以科學(xué)理論和工程上能力的技術(shù)，規(guī)范地開發(fā)大型、復(fù)雜、高質(zhì)量的應(yīng)用軟件和系統(tǒng)軟件具有關(guān)鍵性作用；通過課程設(shè)計(jì)的實(shí)踐，學(xué)生可以在程序設(shè)計(jì)方法、上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。任務(wù)概述學(xué)生必須仔細(xì)閱讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)方案，認(rèn)真主動(dòng)完成課程設(shè)計(jì)的要求。有問題及時(shí)主動(dòng)通過各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過程中不斷檢測自己的計(jì)劃完成情況，及時(shí)向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)計(jì)劃需要一周時(shí)間完成，一周中每天至少要上兩小時(shí)的上機(jī)來調(diào)試C或C++語言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序10小時(shí)。屬教師安排上機(jī)時(shí)間學(xué)生不得缺席。課程設(shè)計(jì)內(nèi)容二叉樹的遍歷和應(yīng)用以二叉鏈表表示二叉樹，在此基礎(chǔ)上實(shí)現(xiàn)對(duì)二叉樹的遍歷和應(yīng)用。要求設(shè)計(jì)類（或類模板）來描述二叉樹，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)：創(chuàng)建二叉樹輸出二叉樹二叉樹的先序、中序、后序遍歷二叉樹的按層遍歷統(tǒng)計(jì)二叉樹的葉子結(jié)點(diǎn)、計(jì)算二叉樹的深度并設(shè)計(jì)主函數(shù)測試該類（或類模板）。概要設(shè)計(jì)設(shè)計(jì)思想以廣義表格式輸入一個(gè)二叉樹，將其接收至一維數(shù)組中，利用棧結(jié)構(gòu)建立二叉鏈表樹；通過先、中、后訪問根結(jié)點(diǎn)遞歸算法遍歷二叉樹。例如：a(c(,d)，f(g,))建立如下圖所示二叉樹。ccadfg二叉樹的遍歷結(jié)點(diǎn)為空結(jié)點(diǎn)為空N訪問根節(jié)點(diǎn)先序遍歷方式遍歷左子樹先序遍歷方式遍歷右子樹結(jié)束Y開始運(yùn)行界面設(shè)計(jì)主菜單主菜單先序遞歸遍歷中序遞歸遍歷后序遞歸遍歷先序非遞歸遍歷中序非遞歸遍歷后序非遞歸遍歷層次遍歷結(jié)束將以廣義表形式輸入的二叉樹接收到數(shù)組str[80]中，成功建立二叉樹詳細(xì)設(shè)計(jì)二叉樹的生成structbtnode*bt;intk;{ intb;structbtnode*p,*t; printf("請(qǐng)輸入b:"); scanf("%d",&b); if(b!=0) { p=(structbtnode*)malloc(sizeof(structbtnode)); p->d=b;p->lchild=NULL;p->rchild=NULL; if(k==0)t=p; if(k==1)bt->lchild=p; if(k==2)bt->rchild=p; creatbt(p,1);creatbt(p,2); } return(t);}二叉樹的先序遍歷pretrav(bt)/***二叉樹的先序遍歷***/structbtnode*bt;{ if(bt!=NULL) { printf("%d",bt->d); pretrav(bt->lchild); pretrav(bt->rchild); } return;}二叉樹的中序遍歷intrav(bt)/***二叉樹的中序遍歷**/structbtnode*bt;{ if(bt!=NULL) { intrav(bt->lchild); printf("%d",bt->d); intrav(bt->rchild); } return;}二叉樹的后續(xù)遍歷postrav(bt)/***二叉樹的后序遍歷****/structbtnode*bt;{ if(bt!=NULL) { postrav(bt->lchild); postrav(bt->rchild); printf("%d",bt->d); } return;}主程序的設(shè)計(jì)main(){ structbtnode*bt; intk;chari; bt=(structbtnode*)malloc(sizeof(structbtnode)); k=0; printf("輸入字符'0',退出程序\n"); printf("輸入字符'1',生成二叉樹\n"); printf("輸入字符'2',二叉樹的先序遍歷\n"); printf("輸入字符'3',二叉樹的中序遍歷\n"); printf("輸入字符'4',二叉樹的后序遍歷\n"); printf("請(qǐng)輸入字符'0'-'4':"); scanf("%s",&i); for(;i!='0';) { switch(i) { case'1': { bt=creatbt(bt,k); break; } case'2': { pretrav(bt); printf("\n"); break; } case'3': { intrav(bt); printf("\n"); break; } case'4': { postrav(bt); printf("\n"); break; } default:break; } printf("輸入字符'0',退出程序\n"); printf("輸入字符'1',生成二叉樹\n"); printf("輸入字符'2',二叉樹的先序遍歷\n"); printf("輸入字符'3',二叉樹的中序遍歷\n"); printf("輸入字符'4',二叉樹的后序遍歷\n"); printf("請(qǐng)輸入字符'0'-'4':"); scanf("%s",&i); } free(bt);}測試分析二叉樹的建立二叉樹的先序、中序、后序遍歷先序中序后序課程設(shè)計(jì)總結(jié)二叉樹是數(shù)據(jù)結(jié)構(gòu)的的基本內(nèi)容。雖然程序規(guī)模不大，我依然付出了努力，仍免不了各種錯(cuò)誤的出現(xiàn)。編程過程需要很大的毅力和耐心，而且要有良好的思維和扎實(shí)的專業(yè)基礎(chǔ)知識(shí)，所以我需要不斷的學(xué)習(xí)，發(fā)現(xiàn)自身不足之處并改正它，逐步提高自己。培養(yǎng)學(xué)生用學(xué)到的書本知識(shí)解決實(shí)際問題的能力；培養(yǎng)實(shí)際工作所需要的動(dòng)手能力；培養(yǎng)學(xué)生以科學(xué)理論和工程上能力的技術(shù)，規(guī)范地開發(fā)大型、復(fù)雜、高質(zhì)量的應(yīng)用軟件和系統(tǒng)軟件具有關(guān)鍵性作用；通過課程設(shè)計(jì)的實(shí)踐，學(xué)生可以在程序設(shè)計(jì)方法、上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。通過這次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，讓我熟悉了二叉樹的結(jié)構(gòu)以及其相關(guān)的操作程序。尤其二叉樹遍歷的實(shí)現(xiàn)過程。從中我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程的理解也更深層次。附錄：程序代碼#include<stdio.h>#include<stdlib.h>structbtnode{ intd; structbtnode*lchild; structbtnode*rchild;};structbtnode*creatbt(bt,k)/*二叉樹的生成*/structbtnode*bt;intk;{ intb;structbtnode*p,*t; printf("請(qǐng)輸入b:"); scanf("%d",&b); if(b!=0) { p=(structbtnode*)malloc(sizeof(structbtnode)); p->d=b;p->lchild=NULL;p->rchild=NULL; if(k==0)t=p; if(k==1)bt->lchild=p; if(k==2)bt->rchild=p; creatbt(p,1);creatbt(p,2); } return(t);}pretrav(bt)/***二叉樹的先序遍歷***/structbtnode*bt;{ if(bt!=NULL) { printf("%d",bt->d); pretrav(bt->lchild); pretrav(bt->rchild); } return;}intrav(bt)/***二叉樹的中序遍歷**/structbtnode*bt;{ if(bt!=NULL) { intrav(bt->lchild); printf("%d",bt->d); intrav(bt->rchild); } return;}postrav(bt)/***二叉樹的后序遍歷****/structbtnode*bt;{ if(bt!=NULL) { postrav(bt->lchild); postrav(bt->rchild); printf("%d",bt->d); } return;}main(){ structbtnode*bt; intk;chari; bt=(structbtnode*)malloc(sizeof(structbtnode)); k=0; printf("輸入字符'0',退出程序\n"); printf("輸入字符'1',生成二叉樹\n"); printf("輸入字符'2',二叉樹的先序遍歷\n"); printf("輸入字符'3',二叉樹的中序遍歷\n"); printf("輸入字符'4',二叉樹的后序遍歷\n"); printf("請(qǐng)輸入字符'0'-'4':"); scanf("%s",&i); for(;i!='0';) { switch(i) { case'1': { bt=creatbt(bt,k); break; } case'2': { pretrav(bt); printf("\n"); break; } case'3': { intrav(bt); printf("\n"); break; }