數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(二叉樹的基本操作)

1、重慶大學(xué)城市科技學(xué)院課程設(shè)計(jì)報(bào)告 二叉樹的基本操作 學(xué) 院： 電氣信息學(xué)院 專 業(yè)： 軟件工程 年 級(jí)： 2011 姓 名： 班 級(jí)： 01 學(xué) 號(hào)： 20110286 成 績： 完成時(shí)間： 2013年1月2日 指導(dǎo)教師： 目錄一、需求分析3二、概要設(shè)計(jì)3三、詳細(xì)設(shè)計(jì)4四、調(diào)試結(jié)果11五、課程設(shè)計(jì)總結(jié)11一、需求分析二叉樹形象地說即樹中每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支，它是一種重要的數(shù)據(jù)類型。可以運(yùn)用于建立家譜，公司所有的員工的職位圖，以及各種事物的分類和各種機(jī)構(gòu)的職位圖表等。二叉樹是通過建立一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，達(dá)到能夠?qū)崿F(xiàn)前序遍歷，中序遍歷，后序遍歷。以及能夠從輸入的數(shù)據(jù)中得知二叉樹的葉子結(jié)點(diǎn)的個(gè)數(shù)，

2、二叉樹的深度。在此，二叉樹的每一個(gè)結(jié)點(diǎn)中必須包括：值域，左指針域，右指針域。演示程序以用戶與計(jì)算機(jī)對(duì)話的方式進(jìn)行，即在計(jì)算機(jī)終端上顯示提示信息后，由用戶在鍵盤上輸入相應(yīng)動(dòng)作的序號(hào)和相應(yīng)的輸入數(shù)據(jù)。1.1課程設(shè)計(jì)任務(wù)及要求(1)按先序次序輸入二叉樹中結(jié)點(diǎn)的值,構(gòu)造二叉鏈表表示的二叉樹t；(2)對(duì)二叉樹t作先序、中序、后序遍歷的遞歸算法,輸出結(jié)果；(3)計(jì)算二叉樹t的深度,輸出結(jié)果；(4)計(jì)算二叉樹t的葉子結(jié)點(diǎn)個(gè)數(shù)1.2課程設(shè)計(jì)思想本次課程設(shè)計(jì)中，用到的主要知識(shí)就是遞歸思想，著重體會(huì)遞歸的思想。建立二叉樹采用先序次序插入的方式。對(duì)二叉樹進(jìn)行遍歷時(shí)采用遞歸函數(shù)的方式。求二叉樹的深度及葉子結(jié)點(diǎn)個(gè)數(shù)均采

3、用遞歸方式。 二、概要設(shè)計(jì)2.1對(duì)程序中定義的核心數(shù)據(jù)結(jié)構(gòu)及對(duì)其說明：typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;在開頭定義了二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，此處采用了每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域， 即值域，左指針域和右指針域。2.2 程序模塊及其功能：本程序分為：7大模塊。二叉樹的建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、前序遍歷、中序遍歷、后序遍歷、求葉子結(jié)點(diǎn)的個(gè)數(shù)計(jì)算、中序遍歷、后序遍歷、深度、主函數(shù)。1、二叉樹的建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；首先typedef struct BiTNode：定義二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，此處采

4、用了每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，data：即值域，*lchild：左指針域和rchild：右指針域。2、二叉樹的前序遍歷；利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的前序遍歷：先訪問根結(jié)點(diǎn)，再依次訪問左右子樹。3、二叉樹的中序遍歷；利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的中序遍歷：先訪問左子數(shù)，再訪問根結(jié)點(diǎn)，最后訪問右子樹。4、二叉樹的后序遍歷；利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的前序遍歷：先訪問左右子樹，再訪問根結(jié)點(diǎn)。5、求二叉樹的深度：首先判斷二叉樹是否為空，若為空則此二叉樹的深度為0。否則，就先別求出左右子樹的深度并進(jìn)行比較，取較大的+1就為二叉樹的深度。6、二叉樹的求葉子結(jié)點(diǎn)的個(gè)數(shù)計(jì)算；先分別求得左右子樹中各葉子結(jié)點(diǎn)個(gè)數(shù)，再計(jì)算出兩

5、者之和即為二叉樹的葉子結(jié)點(diǎn)數(shù)。7、主函數(shù)。主函數(shù)中分別調(diào)用各函數(shù)。三、詳細(xì)設(shè)計(jì)3.1存儲(chǔ)結(jié)構(gòu)的建立由遞歸函數(shù)實(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個(gè)任意的字符，而且在輸入n個(gè)字符后，必須輸入n+1個(gè)0，才能得到本程序所有能夠?qū)崿F(xiàn)的功能。t=Null是將二叉樹置空。if(!(t=(bitnode *)malloc(sizeof(bitnode)，采用動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)的方式，不僅實(shí)現(xiàn)起來方便，而且還節(jié)省大量的存儲(chǔ)空間。t-data=ch;值域t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);

7、將二叉樹中的每一個(gè)結(jié)點(diǎn)設(shè)置為：值域，左指針域，右指針。這一小段程序?qū)崿F(xiàn)了二叉樹的置空，二叉樹的建立，二叉樹的存儲(chǔ)。3.2前序遍歷：先訪問根結(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹。具體函數(shù)為：void preordertraverse(bitree t)if(t)printf(%c,t-data);preordertraverse(t-lchild);preordertraverse(t-rchild);3.3中序遍歷：先訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。具體函數(shù)為：void inordertraverse(bitree t) if (t) inordertraverse(t-lchild)

8、;printf(%c,t-data);inordertraverse(t-rchild); 3.4后序遍歷：先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點(diǎn)。具體函數(shù)為：void postordertraverse(bitree t) if(t)postordertraverse(t-lchild);postordertraverse(t-rchild);printf(%c,t-data); 3.5求二叉樹的深度：先定義三個(gè)整形變量m,n.如果樹為空，則height=0；否則，先分別訪問出左右子樹的深度，再進(jìn)行比較，將較大的+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é)點(diǎn)的個(gè)數(shù)：用leafcount變量表示葉子結(jié)點(diǎn)的總個(gè)數(shù)，用leafcount(t-lchild)、leafcount(t-rchild)分別表示訪問的左右子樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。當(dāng)樹為空時(shí)討論葉子結(jié)點(diǎn)個(gè)數(shù)無意義；當(dāng)樹非空時(shí)分為：一、左右子數(shù)都不存在時(shí)，即葉子結(jié)點(diǎn)的個(gè)數(shù)為1；二、左右子樹存在，就用分別訪問出左右子樹中葉子結(jié)點(diǎn)的個(gè)數(shù)，兩者相加就為二叉樹葉子結(jié)點(diǎn)的個(gè)數(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(請(qǐng)輸入建樹字符序

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é)點(diǎn)的數(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 /存儲(chǔ)結(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); /動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)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é)點(diǎn)個(gè)數(shù)int leaf

15、count(bitree t) /leafcount表示葉子結(jié)點(diǎn)的總個(gè)數(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(請(qǐng)輸入建樹字符序列，以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é)點(diǎn)的數(shù)目為:);v=leafcount(t);printf(%d,v);printf(n); 四、測試結(jié)果五、課程設(shè)計(jì)總結(jié)-本程序基本上實(shí)現(xiàn)了前序遍歷，中序遍歷，后序遍歷，葉子結(jié)點(diǎn)個(gè)數(shù)的求出，二叉樹深度的求出等基本操作。 邁著時(shí)間的步伐，這次的課程設(shè)計(jì)也即將結(jié)束，但這個(gè)學(xué)期數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)還是具有相當(dāng)大的意義，特別是這次的課程設(shè)計(jì),它從一個(gè)程度上改變

17、了我的編程思想，如何將一個(gè)程序快速而又準(zhǔn)備的進(jìn)行編寫，進(jìn)行編譯，都成為了我思考的重點(diǎn)。同時(shí)通過這一個(gè)學(xué)期的學(xué)習(xí)，我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學(xué)習(xí)中去。在這個(gè)階段，我也明白了，好的思想，不能提留于字面上的認(rèn)知，還需要平時(shí)多練多寫一些相關(guān)的程序，并且通過修改，加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度，這才是關(guān)鍵。但在這次的課設(shè)中也遇了一些問題。做二叉樹之前，必須先構(gòu)思出怎樣建立和想要實(shí)現(xiàn)那些功能。然后分塊去建立各自的模型。由于做好了這些工作，我的課程設(shè)計(jì)進(jìn)行的還比較順利。但是，也出現(xiàn)一些很基礎(chǔ)很低級(jí)的錯(cuò)誤，后來經(jīng)過自己的仔細(xì)分析，終于圓滿完成。這說明我的程序設(shè)計(jì)基礎(chǔ)還不是太扎實(shí)，還需要多上機(jī)實(shí)現(xiàn)，不能陷入只看不做的誤區(qū)。通過這次的課程設(shè)計(jì)，我從中得到了許多經(jīng)驗(yàn)和軟件設(shè)計(jì)的一些新思路。從二叉樹問題設(shè)計(jì)以及分析中，我理解到了數(shù)據(jù)結(jié)構(gòu)對(duì)于軟件設(shè)計(jì)的重要性。它的使用，可以改變軟件的運(yùn)行周期，思路從繁化簡，并且都能夠通過其相關(guān)引導(dǎo)，將本身