




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、重慶大學(xué)城市科技學(xué)院課程設(shè)計報告 二叉樹的基本操作 學(xué) 院: 電氣信息學(xué)院 專 業(yè): 軟件工程 年 級: 2011 姓 名: 班 級: 01 學(xué) 號: 20110286 成 績: 完成時間: 2013年1月2日 指導(dǎo)教師: 目錄一、需求分析3二、概要設(shè)計3三、詳細設(shè)計4四、調(diào)試結(jié)果11五、課程設(shè)計總結(jié)11一、需求分析二叉樹形象地說即樹中每個節(jié)點最多只有兩個分支,它是一種重要的數(shù)據(jù)類型??梢赃\用于建立家譜,公司所有的員工的職位圖,以及各種事物的分類和各種機構(gòu)的職位圖表等。二叉樹是通過建立一個鏈?zhǔn)酱鎯Y(jié)構(gòu),達到能夠?qū)崿F(xiàn)前序遍歷,中序遍歷,后序遍歷。以及能夠從輸入的數(shù)據(jù)中得知二叉樹的葉子結(jié)點的個數(shù),
2、二叉樹的深度。在此,二叉樹的每一個結(jié)點中必須包括:值域,左指針域,右指針域。演示程序以用戶與計算機對話的方式進行,即在計算機終端上顯示提示信息后,由用戶在鍵盤上輸入相應(yīng)動作的序號和相應(yīng)的輸入數(shù)據(jù)。1.1課程設(shè)計任務(wù)及要求(1)按先序次序輸入二叉樹中結(jié)點的值,構(gòu)造二叉鏈表表示的二叉樹t;(2)對二叉樹t作先序、中序、后序遍歷的遞歸算法,輸出結(jié)果;(3)計算二叉樹t的深度,輸出結(jié)果;(4)計算二叉樹t的葉子結(jié)點個數(shù)1.2課程設(shè)計思想本次課程設(shè)計中,用到的主要知識就是遞歸思想,著重體會遞歸的思想。建立二叉樹采用先序次序插入的方式。對二叉樹進行遍歷時采用遞歸函數(shù)的方式。求二叉樹的深度及葉子結(jié)點個數(shù)均采
3、用遞歸方式。 二、概要設(shè)計2.1對程序中定義的核心數(shù)據(jù)結(jié)構(gòu)及對其說明:typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;在開頭定義了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),此處采用了每個結(jié)點中設(shè)置三個域, 即值域,左指針域和右指針域。2.2 程序模塊及其功能:本程序分為:7大模塊。二叉樹的建立鏈?zhǔn)酱鎯Y(jié)構(gòu)、前序遍歷、中序遍歷、后序遍歷、求葉子結(jié)點的個數(shù)計算、中序遍歷、后序遍歷、深度、主函數(shù)。1、二叉樹的建立鏈?zhǔn)酱鎯Y(jié)構(gòu);首先typedef struct BiTNode:定義二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),此處采
4、用了每個結(jié)點中設(shè)置三個域,data:即值域,*lchild:左指針域和rchild:右指針域。2、二叉樹的前序遍歷;利用二叉鏈表作為存儲結(jié)構(gòu)的前序遍歷:先訪問根結(jié)點,再依次訪問左右子樹。3、二叉樹的中序遍歷;利用二叉鏈表作為存儲結(jié)構(gòu)的中序遍歷:先訪問左子數(shù),再訪問根結(jié)點,最后訪問右子樹。4、二叉樹的后序遍歷;利用二叉鏈表作為存儲結(jié)構(gòu)的前序遍歷:先訪問左右子樹,再訪問根結(jié)點。5、求二叉樹的深度:首先判斷二叉樹是否為空,若為空則此二叉樹的深度為0。否則,就先別求出左右子樹的深度并進行比較,取較大的+1就為二叉樹的深度。6、二叉樹的求葉子結(jié)點的個數(shù)計算;先分別求得左右子樹中各葉子結(jié)點個數(shù),再計算出兩
5、者之和即為二叉樹的葉子結(jié)點數(shù)。7、主函數(shù)。主函數(shù)中分別調(diào)用各函數(shù)。三、詳細設(shè)計3.1存儲結(jié)構(gòu)的建立由遞歸函數(shù)實現(xiàn)具體函數(shù)為:typedef struct bitnode telemtype data; struct bitnode *lchild,*rchild;bitnode ,*bitree;bitree createbitree(bitree t)char ch;scanf(%c,&ch);if(ch=#) t=NULL;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overflow);t-data=ch;t-lchild=creat
6、ebitree(t-lchild);t-rchild=createbitree(t-rchild);return t;在創(chuàng)建的二叉樹中,左右孩子都為字符型。char的作用是輸入n個任意的字符,而且在輸入n個字符后,必須輸入n+1個0,才能得到本程序所有能夠?qū)崿F(xiàn)的功能。t=Null是將二叉樹置空。if(!(t=(bitnode *)malloc(sizeof(bitnode),采用動態(tài)申請新結(jié)點的方式,不僅實現(xiàn)起來方便,而且還節(jié)省大量的存儲空間。t-data=ch;值域t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);
7、將二叉樹中的每一個結(jié)點設(shè)置為:值域,左指針域,右指針。這一小段程序?qū)崿F(xiàn)了二叉樹的置空,二叉樹的建立,二叉樹的存儲。3.2前序遍歷:先訪問根結(jié)點,再訪問左子樹,最后訪問右子樹。具體函數(shù)為:void preordertraverse(bitree t)if(t)printf(%c,t-data);preordertraverse(t-lchild);preordertraverse(t-rchild);3.3中序遍歷:先訪問左子樹,再訪問根結(jié)點,最后訪問右子樹。具體函數(shù)為:void inordertraverse(bitree t) if (t) inordertraverse(t-lchild)
8、;printf(%c,t-data);inordertraverse(t-rchild); 3.4后序遍歷:先訪問左子樹,再訪問右子樹,最后訪問根結(jié)點。具體函數(shù)為:void postordertraverse(bitree t) if(t)postordertraverse(t-lchild);postordertraverse(t-rchild);printf(%c,t-data); 3.5求二叉樹的深度:先定義三個整形變量m,n.如果樹為空,則height=0;否則,先分別訪問出左右子樹的深度,再進行比較,將較大的+1的結(jié)果就是所求二叉樹的深度。具體函數(shù)為:int height(bitre
9、e t)int m,n;if(t=NULL) return 0;else m=height(t-lchild);n=height(t-rchild);return (mn)?m+1:n+1;3.6求葉子結(jié)點的個數(shù):用leafcount變量表示葉子結(jié)點的總個數(shù),用leafcount(t-lchild)、leafcount(t-rchild)分別表示訪問的左右子樹中葉子結(jié)點的個數(shù)。當(dāng)樹為空時討論葉子結(jié)點個數(shù)無意義;當(dāng)樹非空時分為:一、左右子數(shù)都不存在時,即葉子結(jié)點的個數(shù)為1;二、左右子樹存在,就用分別訪問出左右子樹中葉子結(jié)點的個數(shù),兩者相加就為二叉樹葉子結(jié)點的個數(shù)。具體函數(shù)為:int leafco
10、unt(bitree t) if(!t) return 0; /空數(shù)無葉子 else if(!t-lchild&!t-rchild) return 1; else return leafcount(t-lchild)+leafcount(t-rchild);3.7主函數(shù):包括:二叉樹的數(shù)據(jù)結(jié)構(gòu)bitree t、函數(shù)createbitree、height、leafcount、前序遍歷preordertraverse、中序遍歷inordertraverse、后序遍歷postordertraverse。具體函數(shù)為:void main()bitree t;int w,v;printf(請輸入建樹字符序
11、列:);t=createbitree(t);printf(先序遍歷的結(jié)果是:);preordertraverse(t);printf(n);printf(中序遍歷的結(jié)果是:);inordertraverse(t);printf(n);printf(后序遍歷的結(jié)果是:);postordertraverse(t);printf(n);printf(二叉樹的深度是:);w=height(t);printf(%dn,w);printf(二叉樹的葉子結(jié)點的數(shù)目為:);v=leafcount(t);printf(%d,v);printf(n);3.8完整代碼:#include #include #incl
12、ude #define ok 1#define error 0#define overflow -1typedef char telemtype;typedef struct bitnode /存儲結(jié)構(gòu)的建立 telemtype data; struct bitnode *lchild,*rchild;bitnode ,*bitree;bitree createbitree(bitree t)char ch;scanf(%c,&ch);if(ch=0) t=NULL; /t=NULL是將二叉樹置空elseif(!(t=(bitnode *)malloc(sizeof(bitnode) exit
13、(overflow); /動態(tài)申請新結(jié)點t-data=ch; /值域t-lchild=createbitree(t-lchild); /左指針域t-rchild=createbitree(t-rchild); /右指針域return t; /先序遍歷void preordertraverse(bitree t) if(t)printf(%c,t-data);preordertraverse(t-lchild);preordertraverse(t-rchild); /中序遍歷void inordertraverse(bitree t)if (t) inordertraverse(t-lchil
14、d);printf(%c,t-data);inordertraverse(t-rchild); /后序遍歷 void postordertraverse(bitree t) if(t)postordertraverse(t-lchild);postordertraverse(t-rchild);printf(%c,t-data); /判斷深度 int height(bitree t)int m,n;if(t=NULL) return 0;else m=height(t-lchild);n=height(t-rchild);return (mn)?m+1:n+1; /葉子結(jié)點個數(shù)int leaf
15、count(bitree t) /leafcount表示葉子結(jié)點的總個數(shù)if(!t) return 0; /空數(shù)無葉子else if(!t-lchild&!t-rchild) return 1;else return leafcount(t-lchild)+leafcount(t-rchild); void main()bitree t;int w,v;printf(請輸入建樹字符序列,以0表示NULL:);t=createbitree(t);printf(先序遍歷的結(jié)果是:);preordertraverse(t);printf(n);printf(中序遍歷的結(jié)果是:);inordertra
16、verse(t);printf(n);printf(后序遍歷的結(jié)果是:);postordertraverse(t);printf(n);printf(二叉樹的深度是:);w=height(t);printf(%dn,w);printf(二叉樹的葉子結(jié)點的數(shù)目為:);v=leafcount(t);printf(%d,v);printf(n); 四、測試結(jié)果五、課程設(shè)計總結(jié)-本程序基本上實現(xiàn)了前序遍歷,中序遍歷,后序遍歷,葉子結(jié)點個數(shù)的求出,二叉樹深度的求出等基本操作。 邁著時間的步伐,這次的課程設(shè)計也即將結(jié)束,但這個學(xué)期數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)還是具有相當(dāng)大的意義,特別是這次的課程設(shè)計,它從一個程度上改變
17、了我的編程思想,如何將一個程序快速而又準(zhǔn)備的進行編寫,進行編譯,都成為了我思考的重點。同時通過這一個學(xué)期的學(xué)習(xí),我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學(xué)習(xí)中去。在這個階段,我也明白了,好的思想,不能提留于字面上的認知,還需要平時多練多寫一些相關(guān)的程序,并且通過修改,加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度,這才是關(guān)鍵。但在這次的課設(shè)中也遇了一些問題。做二叉樹之前,必須先構(gòu)思出怎樣建立和想要實現(xiàn)那些功能。然后分塊去建立各自的模型。由于做好了這些工作,我的課程設(shè)計進行的還比較順利。但是,也出現(xiàn)一些很基礎(chǔ)很低級的錯誤,后來經(jīng)過自己的仔細分析,終于圓滿完成。這說明我的程序設(shè)計基礎(chǔ)還不是太扎實,還需要多上機實現(xiàn),不能陷入只看不做的誤區(qū)。通過這次的課程設(shè)計,我從中得到了許多經(jīng)驗和軟件設(shè)計的一些新思路。從二叉樹問題設(shè)計以及分析中,我理解到了數(shù)據(jù)結(jié)構(gòu)對于軟件設(shè)計的重要性。它的使用,可以改變軟件的運行周期,思路從繁化簡,并且都能夠通過其相關(guān)引導(dǎo),將本身
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 上海市上戲附中2025屆高一下化學(xué)期末教學(xué)質(zhì)量檢測模擬試題含解析
- 農(nóng)機中心制度管理辦法
- 合肥建設(shè)行業(yè)管理辦法
- 殯葬服務(wù)租賃管理辦法
- 村級代管資金管理辦法
- 超高壓擠包直流電纜絕緣系統(tǒng)技術(shù)難點及解決方案研究
- 華為薪資待遇管理辦法
- 數(shù)據(jù)安全策略-第2篇-洞察及研究
- 腳手架施工方案:高空作業(yè)安全
- 廚房管理辦法實施細則
- 職工代表選舉方案及選票模版(2篇)
- 血透室護理安全管理及防范
- 廣東發(fā)布智慧公路標(biāo)準(zhǔn)體系(2024版)
- 電商直播平臺主播操作手冊
- ASTM-D3359-(附著力測試標(biāo)準(zhǔn))-中文版
- 石嘴山市直機關(guān)遴選公務(wù)員筆試真題2022
- 吉林省吉林市亞橋中學(xué)2023-2024學(xué)年七年級下學(xué)期期末考試數(shù)學(xué)試卷
- 貴州省貴陽市南明區(qū)2023-2024學(xué)年四年級下學(xué)期期末數(shù)學(xué)質(zhì)量監(jiān)測
- DL-T5706-2014火力發(fā)電工程施工組織設(shè)計導(dǎo)則
- 2024-2030年殷瓦鋼行業(yè)市場現(xiàn)狀供需分析及重點企業(yè)投資評估規(guī)劃分析研究報告
- 第一目擊者理論考試題題庫110題
評論
0/150
提交評論