課程設(shè)計(jì)任務(wù)書學(xué)生姓名：劉闖專業(yè)班級(jí)：計(jì)算機(jī)0502指導(dǎo)教師：宋華珠一工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院一題目：二叉排序樹的建立及遍歷的實(shí)現(xiàn)初始條件：理論：學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)》課程，掌握了基本的數(shù)據(jù)結(jié)構(gòu)和常用的算法；實(shí)踐：計(jì)算機(jī)技術(shù)系實(shí)驗(yàn)室提供計(jì)算機(jī)及軟件開發(fā)環(huán)境。要求完成的主要任務(wù)：（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1、系統(tǒng)應(yīng)具備的功能：（1）建立二叉排序樹；（2）中序遍歷二叉排序樹并輸出排序結(jié)果；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)及測試、設(shè)計(jì)體會(huì)等；（4）結(jié)束語；（5）參考文獻(xiàn)。時(shí)間安排：2007年7月2日一7日（第18周）7月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)教師簽名:系主任（或責(zé)任教師）簽名:2007年7月2日2007年7月2日排序二叉樹的建立及其遍歷的實(shí)現(xiàn)摘要：我所設(shè)計(jì)的課題為排序二叉樹的建立及其遍歷的實(shí)現(xiàn)，它的主要功能是將輸入的數(shù)據(jù)組合成排序二叉樹，并進(jìn)行，先序，中序和后序遍歷。設(shè)計(jì)該課題采用了C語言程序設(shè)計(jì)，簡潔而方便，它主要運(yùn)用了建立函數(shù)，調(diào)用函數(shù)，建立遞歸函數(shù)等等方面來進(jìn)行設(shè)計(jì)。指導(dǎo)教師簽名:系主任（或責(zé)任教師）簽名:2007年7月2日關(guān)鍵字：排序二叉樹，先序遍歷，中序遍歷，后序遍歷0.引言我所設(shè)計(jì)的題目為排序二叉樹的建立及其遍歷的實(shí)現(xiàn)。排序二叉樹或是一棵空樹；或是具有以下性質(zhì)的二叉樹：（1）若它的左子樹不空，則作子樹上所有的結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；（3）它的左，右子樹也分別為二叉排序樹。對(duì)排序二叉樹的建立需知道其定義及其通過插入結(jié)點(diǎn)來建立排序二叉樹，遍歷及其輸出結(jié)果。該設(shè)計(jì)根據(jù)輸入的數(shù)據(jù)進(jìn)行建立排序二叉樹。對(duì)排序二叉樹的遍歷，其關(guān)鍵是運(yùn)用遞歸調(diào)用，這將極大的方便算法設(shè)計(jì)。.需求分析建立排序二叉樹，主要是需要建立節(jié)點(diǎn)用來存儲(chǔ)輸入的數(shù)據(jù)，需要建立函數(shù)用來創(chuàng)造排序二叉樹，在函數(shù)內(nèi)，需要進(jìn)行數(shù)據(jù)比較決定數(shù)據(jù)放在左子樹還是右子樹。在遍歷二叉樹中，需要建立遞歸函數(shù)進(jìn)行遍歷。該題目包含兩方面的內(nèi)容，一為排序二叉樹的建立；二為排序二叉樹的遍歷，包括先序遍歷，中序遍歷和后序遍歷。排序二叉樹的建立主要運(yùn)用了循環(huán)語句和遞歸語句進(jìn)行，對(duì)遍歷算法運(yùn)用了遞歸語句來進(jìn)行。.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)在寫算法之前，應(yīng)對(duì)其進(jìn)行數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。本題目主要會(huì)用到建立結(jié)點(diǎn)，構(gòu)造指針變量，插入結(jié)點(diǎn)函數(shù)和建立排序二叉樹函數(shù)，求深度函數(shù)，以及先序遍歷函數(shù)，中序遍歷函數(shù)和后序遍歷函數(shù)，還有一些常用的輸入輸出語句。對(duì)建立的函明確其作用，先理清函數(shù)內(nèi)部的程序以及算法在將其應(yīng)用到整個(gè)程序中，在建立排序二叉樹時(shí)，主要用到建立節(jié)點(diǎn)函數(shù)，建立樹函數(shù)，深度函數(shù)，在遍歷樹是，用到先序遍歷函數(shù)，中序遍歷函數(shù)和后序遍歷函數(shù)。結(jié)點(diǎn)結(jié)構(gòu)體定義：typedefstructtnode/*建立節(jié)點(diǎn)*/{intdata;structtnode*lchild,*rchild;}TNODE;.算法設(shè)計(jì)在進(jìn)行算法設(shè)計(jì)時(shí)，應(yīng)將題目分為兩部分，排序二叉樹的建立，排序二叉樹的遍歷。3.1定義結(jié)點(diǎn)typedefstructtnode/*建立節(jié)點(diǎn)*/{intdata;structtnode*lchild,*rchild;}TNODE;TNODE*q;/*構(gòu)造指針變量*/TNODE*bt;3.2插入結(jié)點(diǎn)函數(shù)insert()Voidinsert(TNODE**b,TNODE*s)/*排序二叉樹中插入節(jié)點(diǎn)*/{if((*b)==NULL)(*b)=s;elseif(s->data==(*b)->data)return;elseif(s->data<(*b)->data)insert((&(*b)->lchild),s);elseif(s->data>(*b)->data)insert((&(*b)->rchild),s);}3.3創(chuàng)建樹函數(shù)creat()voidcreat(TNODE*b)/*建立排序二叉樹*/{intx;TNODE*s;b=NULL;/*初始化二叉數(shù)*/scanf("%d",&x);s=(TNODE*)malloc(sizeof(TNODE));q=s;/*將根結(jié)點(diǎn)指針地址賦值給q*/while(x!=-1)/*反復(fù)讀入節(jié)點(diǎn),直至-1結(jié)束*/{s->data=x;s->lchild=NULL;s->rchild=NULL;insert(&bt,s);scanf("%d",&x);/*節(jié)點(diǎn)插入排序二叉樹中*/s=(TNODE*)malloc(sizeof(TNODE));n=n+1;}}3.4求排序二叉樹的深度intdeep(TNODE*t)/*求排序二叉樹的深度*/{intrd;intld;if(!t)return0;else{ld=deep(t->lchild);rd=deep(t->rchild);}if(ld>rd)returnld+1;elsereturnrd+1;}3.5建立先序遍歷函數(shù)voidpreorder(TNODE*p){if(p){printf("%4d",p->data);preorder(p->lchild);preorder(p->rchild);}}3.6中序遍歷voidinorder(TNODE*p){if(p){inorder(p->lchild);printf("%4d",p->data);inorder(p->rchild);}}3.7后序遍歷voidpostorder(TNODE*p){/*先序遍歷二叉樹*//*中序遍歷二叉樹*//*后序遍歷二叉樹*/if(p){postorder(p->lchild);postorder(p->rchild);printf("%4d",p->data);}}這三個(gè)函數(shù)都應(yīng)用了遞歸調(diào)用。最后，在主函數(shù)中分別調(diào)用所建立的函數(shù)，3.8有關(guān)技術(shù)的討論在設(shè)計(jì)程序時(shí)，我發(fā)現(xiàn)用遞歸函數(shù)來寫程序會(huì)簡潔很多，能大大的縮小程序的代碼，在求排序二叉樹的深度，先序遍歷排序二叉樹，中序遍歷排序二叉樹以及和；后序遍歷排序二叉樹中，都用到了遞歸函數(shù)，大大簡化了源程序的代碼。在輸入數(shù)據(jù)時(shí)，用while函數(shù)會(huì)使數(shù)據(jù)能夠不斷的輸入進(jìn)來，解決了無法從外部輸入數(shù)據(jù)的問題，用的很巧妙。.程序?qū)崿F(xiàn)4.1調(diào)入文件#include<math.h>#include<stdio.h>#include<stdlib.h>4.2主函數(shù)main()voidmain()/*主函數(shù)*/{printf("pleaseinsertthenumbers(whenyoufinishinsertingnumbers,pleaseinsert-1totheend):\n");creat(bt);/*構(gòu)造排序二叉樹*/printf("thenumbersofthenodesare:%4d”,n);/*輸出排序二叉樹的結(jié)點(diǎn)數(shù)*/printf("\nthedepthofthetree:");printf("%4d",deep(q));/*求二叉樹的深度*/printf("\npreorder,theresultis:");preorder(q);/*先序遍歷排序二叉樹*/printf("\ninorder,theresultis:");inorder(q);/*中序遍歷排序二叉樹*/printf("\npostorder,theresultis:");postorder(q);/*后序遍歷排序二叉樹*/getchar();}然后輸出結(jié)果。在設(shè)計(jì)中，最難的那一部分為求插入結(jié)點(diǎn)函數(shù)，在函數(shù)內(nèi)部要進(jìn)行比較，將較小的數(shù)賦給左子樹，將將較大的數(shù)賦給右子樹。在其他的算法設(shè)計(jì)中，只要理清思路就不會(huì)太難。4.3運(yùn)行結(jié)果顯示程序：443452443452767819-1ZHUkjilcaL￡einuertft]*iramTil5ers<whcnifinislainsertingnmriljerx,picas&insert一1tothebnd>=443輸入數(shù)據(jù):?CAWINDOWSVystem32\cmd￡wepleaseinsertthenLimbers<whenyou.finishinsertingnunbefs,pleaseinsert-1totheend>:輸出結(jié)果:5.設(shè)計(jì)體會(huì)設(shè)計(jì)體會(huì)7S781thvBnnimbBrs：ofthenodessf?s9thedepthofthetree：5preoi*id^r!j.t>icrssuiltie"421439467&78InfCi'deF^itheresultis：1249434678postoi'derresulti客：129787B454J4Ice^ito5.設(shè)計(jì)體會(huì)設(shè)計(jì)體會(huì)我感受最深的一點(diǎn)是以前用c編程，只是注重如何編寫函數(shù)能夠完成所需要的功能，似乎沒有明確的思路該怎么設(shè)計(jì)，在哪一階段該設(shè)計(jì)什么。經(jīng)過這一次設(shè)計(jì)，我學(xué)會(huì)了怎樣設(shè)計(jì)程序，怎樣控制整個(gè)程序，它使我學(xué)會(huì)了怎樣設(shè)計(jì)程序，設(shè)計(jì)算法，設(shè)計(jì)課題。通過這個(gè)星期的課程設(shè)計(jì)，我的收獲還是不少。我的c語言水平有了比較大的提高，其中c語言關(guān)于指針，鏈表的操作理解的比以前深刻不少。另外是數(shù)據(jù)結(jié)構(gòu)方面的提高，對(duì)存儲(chǔ)結(jié)構(gòu)，及各種查找排序方面也有不少的提高。雖然我做的程序里還有寫問題，做的不夠深入，但獨(dú)立完成一個(gè)比較大一點(diǎn)的程序的經(jīng)歷也是很寶貴的。

通過這次課程設(shè)計(jì)我覺得我們學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》的方法存在一定的弊端《數(shù)據(jù)結(jié)構(gòu)》的效果直接影響到我們對(duì)其它專業(yè)課的學(xué)習(xí)和今后業(yè)務(wù)的成長。我覺得我們對(duì)于《數(shù)據(jù)結(jié)構(gòu)》的學(xué)習(xí)不僅包括理論部分的學(xué)習(xí)，還要讓我們勤動(dòng)手，多實(shí)踐。整個(gè)實(shí)驗(yàn)過程要結(jié)合教學(xué)進(jìn)度與我們的實(shí)際情況，制定實(shí)驗(yàn)的內(nèi)容。實(shí)驗(yàn)分兩部分，一是驗(yàn)證性的，主要結(jié)合課堂理論教學(xué)內(nèi)容展開，學(xué)生可以對(duì)在課堂上學(xué)到的基本算法進(jìn)行驗(yàn)證；二是設(shè)計(jì)性實(shí)驗(yàn)，堅(jiān)持“學(xué)以致用”的原則，目的是讓學(xué)生充分利用所學(xué)的理論知識(shí)進(jìn)行相對(duì)復(fù)雜的應(yīng)用設(shè)計(jì)，以進(jìn)一步提高綜合能力和創(chuàng)新實(shí)踐能力。通過這次設(shè)計(jì)，我感慨頗多，的確，從選題到定稿，從理論到實(shí)踐，在一個(gè)星期的日子里，可以說得是苦多于甜，但是可以學(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ì)的過程中遇到問題，可以說得是困難重重，這畢竟第一次做的，難免會(huì)遇到過各種各樣的問題，同時(shí)在設(shè)計(jì)的過程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過的知識(shí)理解得不夠深刻，掌握得不夠牢固，通過