版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
1、<p><b> 學年論文(設計)</b></p><p><b> ?。ū究疲?lt;/b></p><p> 學 院 </p><p> 專 業(yè) </p><p> 年 級
2、 </p><p> 姓 名 </p><p> 論文(設計)題目 </p><p> 指導教師 職稱 </p><p> 成 績
3、 </p><p> 2012 年 月 日</p><p><b> 摘要:</b></p><p> 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關(guān)系和操作的學科。作為研究對象的數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(又稱映像),稱為數(shù)據(jù)的
4、物理結(jié)構(gòu),又稱存儲結(jié)構(gòu)。相同的邏輯結(jié)構(gòu)可以具有不同的存儲結(jié)構(gòu),因而有不同的算法。</p><p> 本次課程設計,程序中的數(shù)據(jù)采用“樹形結(jié)構(gòu)”作為其數(shù)據(jù)結(jié)構(gòu)。具體采用的是二叉樹。二叉樹是樹形結(jié)構(gòu)的一個重要的類型,二叉樹是n(n>0)個結(jié)點的有限集,它或者是空集(n>0),或者由一個根結(jié)點以及兩棵互不相交的,分別稱為左子樹和右子樹的二叉樹組成。</p><p> 二叉樹的順序
5、存儲結(jié)構(gòu)是把二叉樹所有結(jié)點,按照一定的次序排序,存儲到一片連續(xù)的存儲單元中。但二叉樹的順序存儲結(jié)構(gòu)浪費空間并且插入、刪除不方便。二叉樹的鏈式存儲每個結(jié)點至少包含三個域:數(shù)據(jù)域、左指針域、右指針域,不浪費空間。二叉樹的存儲結(jié)構(gòu)和算法比較簡單,特別適合計算機處理,即使一般形式的樹也可簡單的轉(zhuǎn)換為二叉樹。</p><p> 現(xiàn)實中經(jīng)常用到二叉樹,因此本課程設計主要實現(xiàn)了二叉樹的建立、三種遍歷,計算二叉數(shù)的樹深、統(tǒng)計葉
6、子結(jié)點的個數(shù)等功能。</p><p> 關(guān)鍵詞:二叉樹;遍歷;樹深;葉子結(jié)點</p><p><b> 學生簽名: </b></p><p> 2012年 月 日</p><p><b> 目錄</b></p><p><b> 一、需求分析
7、4</b></p><p><b> 二、概要設計5</b></p><p><b> 三、詳細設計6</b></p><p> 四、調(diào)試分析及測試12</p><p> 五、課程設計總結(jié)20</p><p><b> 參考文獻21
8、</b></p><p><b> 附錄21</b></p><p><b> 二叉樹基本操作</b></p><p><b> 需求分析</b></p><p> 二叉樹形象地說即樹中每個節(jié)點最多只有兩個分支,它是一種重要的數(shù)據(jù)類型。可以運用于建立家譜,
9、公司所有的員工的職位圖,以及各種事物的分類和各種機構(gòu)的職位圖表等。</p><p> 二叉樹是通過建立一個鏈式存儲結(jié)構(gòu),達到能夠?qū)崿F(xiàn)前序遍歷,中序遍歷,后序遍歷。以及能夠從輸入的數(shù)據(jù)中得知二叉樹的葉子結(jié)點的個數(shù),二叉樹的深度。在此,二叉樹的每一個結(jié)點中必須包括:值域,左指針域,右指針域。演示程序以用戶與計算機對話的方式進行,即在計算機終端上顯示提示信息后,由用戶在鍵盤上輸入相應動作的序號和相應的輸入數(shù)據(jù)。<
10、;/p><p><b> 1.1 選題理由</b></p><p> 根據(jù)自己的知識功底和能力水平擇選了二叉樹問題. 而且隨著計算機技術(shù)的飛速發(fā)展,越來越多的問題正逐漸改用計算機解答,并且有些技術(shù)已經(jīng)非常成熟。運用所學計算機知識來研究二叉樹的有關(guān)內(nèi)容可以鍛煉和提高我編程 和獨立解決問題的能力,還可以使我增強信心,為我以后的編程開個好頭,故我選擇了這個課題。</p
11、><p> 1.2課程設計任務及要求</p><p> (1)按先序次序輸入二叉樹中結(jié)點的值,構(gòu)造二叉鏈表表示的二叉樹t;</p><p> (2)對二叉樹t作先序、中序、后序遍歷的遞歸算法,輸出結(jié)果;</p><p> (3)計算二叉樹t的深度,輸出結(jié)果;</p><p> (4)計算二叉樹t的葉子結(jié)點個數(shù)&l
12、t;/p><p><b> 1.3課程設計思想</b></p><p> 本次課程設計中,用到的主要知識就是遞歸思想,著重體會遞歸的思想。建立二叉樹采用先序次序插入的方式。對二叉樹進行遍歷時采用遞歸函數(shù)的方式。求二叉樹的深度及葉子結(jié)點個數(shù)均采用遞歸方式。 </p><p> 1.4軟硬件運行環(huán)境及開發(fā)工具</p><p&g
13、t; WindowsXP操作系統(tǒng)、Microsoft Visual C++ 6.0</p><p><b> 概要設計</b></p><p> 2.1對程序中定義的核心數(shù)據(jù)結(jié)構(gòu)及對其說明:</p><p> typedef struct BiTNode</p><p><b> { </
14、b></p><p> char data;</p><p> struct BiTNode *lchild,*rchild;</p><p> }BiTNode,*BiTree;</p><p> 在開頭定義了二叉樹的鏈式存儲結(jié)構(gòu),此處采用了每個結(jié)點中設置三個域, 即值域,左指針域和右指針域。</p><p
15、> 2.2 程序模塊及其功能:</p><p> 本程序分為:7大模塊。二叉樹的建立鏈式存儲結(jié)構(gòu)、前序遍歷、中序遍歷、后序遍歷、求葉子結(jié)點的個數(shù)計算、中序遍歷、后序遍歷、深度、主函數(shù)。</p><p> 1、二叉樹的建立鏈式存儲結(jié)構(gòu);首先typedef struct BiTNode:定義二叉樹的鏈式存儲結(jié)構(gòu),此處采用了每個結(jié)點中設置三個域,data:即值域,*lchild:左指
16、針域和rchild:右指針域。</p><p> 2、二叉樹的前序遍歷;利用二叉鏈表作為存儲結(jié)構(gòu)的前序遍歷:先訪問根結(jié)點,再依次訪問左右子樹。</p><p> 3、二叉樹的中序遍歷;利用二叉鏈表作為存儲結(jié)構(gòu)的中序遍歷:先訪問左子數(shù),再訪問根結(jié)點,最后訪問右子樹。</p><p> 4、二叉樹的后序遍歷;利用二叉鏈表作為存儲結(jié)構(gòu)的前序遍歷:先訪問左右子樹,再訪
17、問根結(jié)點。</p><p> 5、求二叉樹的深度:首先判斷二叉樹是否為空,若為空則此二叉樹的深度為0。否則,就先別求出左右子樹的深度并進行比較,取較大的+1就為二叉樹的深度。</p><p> 6、二叉樹的求葉子結(jié)點的個數(shù)計算;先分別求得左右子樹中各葉子結(jié)點個數(shù),再計算出兩者之和即為二叉樹的葉子結(jié)點數(shù)。</p><p> 7、主函數(shù)。主函數(shù)中分別調(diào)用各函數(shù)。&
18、lt;/p><p><b> 詳細設計</b></p><p> 1、存儲結(jié)構(gòu)的建立由遞歸函數(shù)實現(xiàn)</p><p><b> 具體函數(shù)為:</b></p><p> typedef struct bitnode</p><p><b> {</b>
19、</p><p> telemtype data;</p><p> struct bitnode *lchild,*rchild;</p><p> }bitnode ,*bitree;</p><p> bitree createbitree(bitree t)</p><p><b> {&l
20、t;/b></p><p><b> char ch;</b></p><p> scanf("%c",&ch);</p><p> if(ch=='#') t=NULL;</p><p><b> else</b></p>&
21、lt;p><b> {</b></p><p> if(!(t=(bitnode *)malloc(sizeof(bitnode)))) exit(overflow);</p><p> t->data=ch;</p><p> t->lchild=createbitree(t->lchild);</p&g
22、t;<p> t->rchild=createbitree(t->rchild);</p><p><b> }</b></p><p><b> return t;</b></p><p><b> }</b></p><p> 在創(chuàng)建的二
23、叉樹中,左右孩子都為字符型。</p><p> char的作用是輸入n個任意的字符,而且在輸入n個字符后,必須輸入n+1個'#',才能得到本程序所有能夠?qū)崿F(xiàn)的功能。t=Null是將二叉樹置空。</p><p> if(!(t=(bitnode *)malloc(sizeof(bitnode)))),采用動態(tài)申請新結(jié)點的方式,不僅實現(xiàn)起來方便,而且還節(jié)省大量的存儲空間。&
24、lt;/p><p> t->data=ch;值域</p><p> t->lchild=createbitree(t->lchild);</p><p> t->rchild=createbitree(t->rchild);</p><p> 將二叉樹中的每一個結(jié)點設置為:值域,左指針域,右指針。</p
25、><p> 這一小段程序?qū)崿F(xiàn)了二叉樹的置空,二叉樹的建立,二叉樹的存儲。</p><p> 2、前序遍歷:先訪問根結(jié)點,再訪問左子樹,最后訪問右子樹。</p><p><b> 具體函數(shù)為:</b></p><p> void preordertraverse(bitree t)</p><p&g
26、t;<b> {</b></p><p><b> if(t)</b></p><p><b> {</b></p><p> printf("%c",t->data);</p><p> preordertraverse(t->lch
27、ild);</p><p> preordertraverse(t->rchild);</p><p><b> }</b></p><p><b> }</b></p><p> 3、中序遍歷:先訪問左子樹,再訪問根結(jié)點,最后訪問右子樹。</p><p>&l
28、t;b> 具體函數(shù)為:</b></p><p> void inordertraverse(bitree t)</p><p><b> {</b></p><p><b> if (t)</b></p><p><b> {</b></p&g
29、t;<p> inordertraverse(t->lchild);</p><p> printf("%c",t->data);</p><p> inordertraverse(t->rchild);</p><p><b> }</b></p><p>&
30、lt;b> }</b></p><p> 4、后序遍歷:先訪問左子樹,再訪問右子樹,最后訪問根結(jié)點。</p><p><b> 具體函數(shù)為:</b></p><p> void postordertraverse(bitree t)</p><p><b> {</b>&
31、lt;/p><p><b> if(t)</b></p><p><b> {</b></p><p> postordertraverse(t->lchild);</p><p> postordertraverse(t->rchild);</p><p>
32、 printf("%c",t->data);</p><p><b> }</b></p><p><b> }</b></p><p> 5、求二叉樹的深度:</p><p> 先定義三個整形變量m,n.如果樹為空,則height=0;</p>&
33、lt;p> 否則,先分別訪問出左右子樹的深度,再進行比較,將較大的+1的結(jié)果就是所求二叉樹的深度。</p><p><b> 具體函數(shù)為:</b></p><p> int height(bitree t)</p><p><b> {</b></p><p><b> i
34、nt m,n;</b></p><p> if(t==NULL) return 0;</p><p><b> else </b></p><p><b> {</b></p><p> m=height(t->lchild);</p><p>
35、n=height(t->rchild);</p><p> return (m>n)?m+1:n+1;</p><p><b> }</b></p><p><b> }</b></p><p> 6、求葉子結(jié)點的個數(shù):</p><p> 用leafco
36、unt變量表示葉子結(jié)點的總個數(shù),用leafcount(t->lchild)、leafcount(t->rchild)分別表示訪問的左右子樹中葉子結(jié)點的個數(shù)。</p><p> 當樹為空是此時討論葉子結(jié)點個數(shù)無意義;</p><p><b> 當樹非空時分為:</b></p><p> 一、左右子數(shù)都不存在時,即葉子結(jié)點的個數(shù)為
37、1;</p><p> 二、左右子樹存在,就用分別訪問出左右子樹中葉子結(jié)點的個數(shù),兩者相加就為二叉樹葉子結(jié)點的個數(shù)。</p><p><b> 具體函數(shù)為:</b></p><p> int leafcount(bitree t)</p><p><b> {</b></p>
38、<p> if(!t) return 0; //空數(shù)無葉子</p><p> else if(!t->lchild&&!t->rchild) return 1;</p><p> else return leafcount(t->lchild)+leafcount(t->rchild);</p><p>
39、<b> }</b></p><p><b> 7、主函數(shù):</b></p><p> 包括:二叉樹的數(shù)據(jù)結(jié)構(gòu)bitree t、函數(shù)createbitree、height、leafcount、前序遍歷preordertraverse、中序遍歷inordertraverse、后序遍歷postordertraverse。</p>
40、<p><b> 具體函數(shù)為:</b></p><p> void main()</p><p><b> {</b></p><p><b> bitree t;</b></p><p><b> int w,v;</b></p
41、><p> printf("請輸入建樹字符序列:");</p><p> t=createbitree(t);</p><p> printf("先續(xù)遍歷的結(jié)果是:");</p><p> preordertraverse(t);</p><p> printf("
42、;\n");</p><p> printf("中續(xù)遍歷的結(jié)果是:");</p><p> inordertraverse(t);</p><p> printf("\n");</p><p> printf("后續(xù)遍歷的結(jié)果是:");</p><
43、;p> postordertraverse(t);</p><p> printf("\n");</p><p> printf("二叉樹的深度是:");</p><p> w=height(t);</p><p> printf("%d\n",w);</p&g
44、t;<p> printf("二叉樹的葉子結(jié)點的數(shù)目為:");</p><p> v=leafcount(t);</p><p> printf("%d",v);</p><p> printf("\n");</p><p><b> }</b
45、></p><p><b> 8、完整代碼:</b></p><p> #include <stdio.h></p><p> #include <malloc.h></p><p> #include <process.h></p><p>
46、#define ok 1</p><p> #define error 0</p><p> #define overflow -1</p><p> typedef char telemtype;</p><p> typedef struct bitnode</p><p><b> {<
47、/b></p><p> telemtype data;</p><p> struct bitnode *lchild,*rchild;</p><p> }bitnode ,*bitree;</p><p> bitree createbitree(bitree t)</p><p><b>
48、; {</b></p><p><b> char ch;</b></p><p> scanf("%c",&ch);</p><p> if(ch=='#') t=NULL;</p><p><b> else</b></p&
49、gt;<p><b> {</b></p><p> if(!(t=(bitnode *)malloc(sizeof(bitnode)))) exit(overflow);</p><p> t->data=ch;</p><p> t->lchild=createbitree(t->lchild);&l
50、t;/p><p> t->rchild=createbitree(t->rchild);</p><p><b> }</b></p><p><b> return t;</b></p><p><b> }</b></p><p>
51、 void preordertraverse(bitree t)</p><p><b> {</b></p><p><b> if(t)</b></p><p><b> {</b></p><p> printf("%c",t->data
52、);</p><p> preordertraverse(t->lchild);</p><p> preordertraverse(t->rchild);</p><p><b> }</b></p><p><b> }</b></p><p> v
53、oid inordertraverse(bitree t)</p><p><b> {</b></p><p><b> if (t)</b></p><p><b> {</b></p><p> inordertraverse(t->lchild);<
54、/p><p> printf("%c",t->data);</p><p> inordertraverse(t->rchild);</p><p><b> }</b></p><p><b> }</b></p><p> void
55、postordertraverse(bitree t)</p><p><b> {</b></p><p><b> if(t)</b></p><p><b> {</b></p><p> postordertraverse(t->lchild);</
56、p><p> postordertraverse(t->rchild);</p><p> printf("%c",t->data);</p><p><b> }</b></p><p><b> }</b></p><p> int
57、height(bitree t)</p><p><b> {</b></p><p><b> int m,n;</b></p><p> if(t==NULL) return 0;</p><p><b> else </b></p><p>
58、;<b> {</b></p><p> m=height(t->lchild);</p><p> n=height(t->rchild);</p><p> return (m>n)?m+1:n+1;</p><p><b> }</b></p><
59、;p><b> }</b></p><p> int leafcount(bitree t)</p><p><b> {</b></p><p> if(!t) return 0; //空數(shù)無葉子</p><p> else if(!t->lchild&&
60、!t->rchild) return 1;</p><p> else return leafcount(t->lchild)+leafcount(t->rchild);</p><p><b> }</b></p><p> void main()</p><p><b> {&l
61、t;/b></p><p><b> bitree t;</b></p><p><b> int w,v;</b></p><p> printf("請輸入建樹字符序列:");</p><p> t=createbitree(t);</p><
62、p> printf("先續(xù)遍歷的結(jié)果是:");</p><p> preordertraverse(t);</p><p> printf("\n");</p><p> printf("中續(xù)遍歷的結(jié)果是:");</p><p> inordertraverse(t)
63、;</p><p> printf("\n");</p><p> printf("后續(xù)遍歷的結(jié)果是:");</p><p> postordertraverse(t);</p><p> printf("\n");</p><p> printf(
64、"二叉樹的深度是:");</p><p> w=height(t);</p><p> printf("%d\n",w);</p><p> printf("二叉樹的葉子結(jié)點的數(shù)目為:");</p><p> v=leafcount(t);</p><p&
65、gt; printf("%d",v);</p><p> printf("\n");</p><p><b> }</b></p><p><b> 調(diào)試分析及測試</b></p><p> 4.1 遇到的問題及解決方法</p><
66、;p> (1). 二叉樹是另一種樹形結(jié)構(gòu),作為一種數(shù)據(jù)結(jié)構(gòu)其在計算機中的存儲結(jié)構(gòu)有兩種:順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。編寫代碼之前首先要確定采用的存儲方式。經(jīng)分析及查找參考資料決定采用鏈式存儲結(jié)構(gòu),這種存儲結(jié)構(gòu)不浪費空間并且插入、刪除方便。</p><p> (2).本程序演示程序以用戶與計算機對話的方式進行,即在計算機終端上顯示提示信息后,由用戶在鍵盤上輸入相應動作的序號和相應的輸入數(shù)據(jù)。在運行程序的過
67、程中出現(xiàn)錯誤,出現(xiàn)了以下界面:</p><p> 后經(jīng)仔細分析及查看代碼,發(fā)現(xiàn)scanf("%c",&ch)語句中少了一個‘&’,經(jīng)改正后,再次運行,得到結(jié)果。</p><p> 4.2 算法的時空分析</p><p> 遍歷二叉樹的基本操作是訪問結(jié)點,則不論按哪一種次序進行遍歷,對含n個結(jié)點的二叉樹,時間復雜度均為O(n)
68、。所需輔助空間為遍歷過程中棧的最大容量,即樹的深度,在最差情況下為n,則空間復雜度也為O(n)。</p><p> 4.3 程序模塊構(gòu)架</p><p> 本程序模塊劃分比較合理,易觀察且操作方便。整體可以分成七個模塊,分別為建立二叉樹、前序遍歷、中序遍歷、后序遍歷、求葉子結(jié)點的個數(shù)、求二叉樹的深度、主函數(shù)。</p><p><b> 4.4 算法的
69、改進</b></p><p> 這道題可以用非遞歸也可以用遞歸的方法來編寫前序遍歷、中序遍歷、后序遍歷、求葉子結(jié)點的個數(shù)、求二叉樹深度的算法,這里我用了后者,遞歸算法簡單方便。</p><p> 4.5 程序使用說明</p><p> (1) 本程序的運行環(huán)境為WindowsXP操作系統(tǒng)</p><p> ?。?) 用戶界面
70、為Microsoft Visual C++ 6.0</p><p> ?。?) 進入界面后,首先進行代碼的輸入,然后通過編譯、組建、執(zhí)行,得到運行結(jié)果,并進行分析查看運行結(jié)果是否正確,進而確定是否要調(diào)試程序</p><p><b> 4.6 測試結(jié)果</b></p><p><b> 4.7 其他程序</b></
71、p><p> ?。?) 遍歷二叉樹的另一種遞歸算法(以先序遍歷為例)</p><p> #include <stdio.h></p><p> #include <malloc.h></p><p> #include <process.h></p><p> #define
72、ok 1</p><p> #define error 0</p><p> #define overflow -1</p><p> typedef char status;</p><p> typedef char TElemtype;</p><p> typedef st
73、ruct BiTNode</p><p><b> {</b></p><p> TElemtype data;</p><p> struct BiTNode *lchild,*rchild;</p><p> }BiTNode,*BiTree;</p><p> sta
74、tus CreateBiTree(BiTree &T)</p><p> { //按先序次序輸入二叉樹中結(jié)點的值(一個字符),'#'字符表示空樹,</p><p> //構(gòu)造二叉鏈表表示的二叉樹T</p><p><b> char ch;</b></p><p> scanf(&qu
75、ot;%c",&ch);</p><p> if (ch=='#') T=NULL;</p><p><b> else </b></p><p><b> {</b></p><p> if(!(T=(BiTNode *)malloc(sizeof(BiT
76、Node)))) </p><p> exit (overflow);</p><p> T->data=ch; //生成根結(jié)點</p><p> CreateBiTree(T->lchild); //構(gòu)造左子數(shù)</p><p> CreateBiTree(T->rchi
77、ld); //構(gòu)造右子數(shù)</p><p><b> }</b></p><p> return ok;</p><p><b> }</b></p><p> status PreorderTraverse(BiTree T,status(*visit)(TElemtype e))&l
78、t;/p><p> { //采用二叉鏈表存儲結(jié)構(gòu),visit是對數(shù)據(jù)元素操作的應用函數(shù),</p><p> //先序遍歷二叉樹T的遞歸算法,對每個數(shù)據(jù)元素調(diào)用函數(shù)visit</p><p><b> if (T)</b></p><p><b> {</b></p><p
79、> if(visit(T->data))</p><p> if(PreorderTraverse(T->lchild,visit))</p><p> if(PreorderTraverse(T->rchild,visit)) return ok;</p><p> return error;</p><p>
80、;<b> }</b></p><p> else return ok;</p><p><b> }</b></p><p> status printelement(TElemtype e)</p><p><b> {</b></p><p
81、> printf("%c",e);</p><p> return ok;</p><p><b> }</b></p><p> void main ()</p><p><b> { </b></p><p><b> Bi
82、Tree T;</b></p><p> CreateBiTree(T);</p><p> PreorderTraverse(T,printelement);</p><p><b> }</b></p><p><b> 運行結(jié)果為</b></p><p&
83、gt; ?。?) 求二叉樹中以元素值為x的結(jié)點為根的子樹的深度</p><p> #include <stdio.h></p><p> #include <malloc.h></p><p> #include <process.h></p><p> #define ok 1</p>
84、;<p> #define error 0</p><p> #define overflow -1</p><p> typedef char status;</p><p> typedef char telemtype;</p><p> typedef struct bitnode</p>
85、<p><b> {</b></p><p> telemtype data;</p><p> struct bitnode *lchild,*rchild;</p><p> }bitnode,*bitree;</p><p> status createbitree(bitree &am
86、p;t)</p><p><b> {</b></p><p><b> char ch;</b></p><p> scanf("%c",&ch);</p><p> if(ch=='#') t=NULL;</p><p&g
87、t;<b> else</b></p><p><b> {</b></p><p> if(!(t=(bitnode *)malloc(sizeof(bitnode)))) exit(overflow);</p><p> t->data=ch;</p><p> createb
88、itree(t->lchild);</p><p> createbitree(t->rchild);</p><p><b> }</b></p><p> return ok;</p><p><b> }</b></p><p> int getd
89、epth(bitree t)</p><p><b> {</b></p><p><b> int m,n;</b></p><p><b> if(t)</b></p><p><b> {</b></p><p>
90、m=getdepth(t->lchild);</p><p> n=getdepth(t->rchild);</p><p> return m>=n?m+1:n+1;</p><p><b> }</b></p><p> else return 0;</p><p>
91、<b> }</b></p><p> int depthx(bitree t,char x)</p><p><b> {</b></p><p><b> int m,n;</b></p><p><b> if(t)</b></p&g
92、t;<p><b> {</b></p><p> if(t->data==x) return getdepth(t);</p><p><b> else</b></p><p><b> {</b></p><p> m=depthx(t-&g
93、t;lchild,x);</p><p> n=depthx(t->rchild,x);</p><p> return m>=n?m:n;</p><p><b> }</b></p><p><b> }</b></p><p> else retu
94、rn 0;</p><p><b> }</b></p><p> void main()</p><p><b> {</b></p><p><b> bitree t;</b></p><p><b> int w,v;<
95、/b></p><p><b> char x;</b></p><p> printf("請輸入以建立二叉樹:");</p><p> createbitree(t);</p><p> printf("二叉樹的深度是:");</p><p>
96、; w=getdepth(t);</p><p> printf("%d\n",w);</p><p> scanf("%c",&x);</p><p> printf("請輸入x:");</p><p> scanf("%c",&x);
97、</p><p> v=depthx(t,x);</p><p> printf("二叉樹中以元素值為x的結(jié)點為根的子樹的深度是:");</p><p> printf("%d\n",v);</p><p><b> }</b></p><p>&l
98、t;b> 運行結(jié)果為</b></p><p> ?。?) 求二叉樹的葉子節(jié)點個#include <stdio.h></p><p> #include <malloc.h></p><p> #include <process.h></p><p> #define ok 1&l
99、t;/p><p> #define error 0</p><p> #define overflow -1</p><p> typedef char status;</p><p> typedef char telemtype;</p><p> typedef struct bitnode<
100、;/p><p><b> {</b></p><p> telemtype data;</p><p> struct bitnode *lchild,*rchild;</p><p> }bitnode,*bitree;</p><p> status createbitree(bit
101、ree &t)</p><p><b> {</b></p><p><b> char ch;</b></p><p> scanf("%c",&ch);</p><p> if(ch=='#') t=NULL;</p>
102、<p><b> else</b></p><p><b> {</b></p><p> if(!(t=(bitnode *)malloc(sizeof(bitnode)))) exit(overflow);</p><p> t->data=ch;</p><p>
103、createbitree(t->lchild);</p><p> createbitree(t->rchild);</p><p><b> }</b></p><p> return ok;</p><p><b> }</b></p><p> s
104、tatus POLeafNodeNum(int& i,bitree& t)</p><p><b> {</b></p><p><b> if(t)</b></p><p><b> {</b></p><p> if(!t->lchild &a
105、mp;& !t->rchild) i++;</p><p> POLeafNodeNum(i,t->lchild);</p><p> POLeafNodeNum(i,t->rchild);</p><p><b> }</b></p><p><b> return i;&l
106、t;/b></p><p><b> }</b></p><p> void main()</p><p><b> {</b></p><p><b> bitree t;</b></p><p> int i=0,w;</p&g
107、t;<p> printf("請讀入字符建立二叉鏈表:\n");</p><p> createbitree(t); </p><p> printf("二叉樹的葉子結(jié)點的數(shù)目為:");</p><p> w=POLeafNodeNum(i,t);</p><p> printf
108、("%d",w);</p><p> printf("\n");</p><p><b> }</b></p><p><b> 運行結(jié)果為</b></p><p><b> 五、課程設計總結(jié)</b></p><
109、;p> 本程序基本上實現(xiàn)了前序遍歷,中序遍歷,后序遍歷,葉子結(jié)點個數(shù)的求出,二叉樹深度的求出等基本操作。 </p><p> 在本次課程設計的學習過程中,我在其中的最大的收獲,就是得到了許多的經(jīng)驗以及軟件設計的一些新的思路。 </p><p> 邁著時間的步伐,這次的課程設計也即將結(jié)束,但這個學期數(shù)據(jù)結(jié)構(gòu)的學習還是具有相當大的意義,特別是這次的課程設計,它從一個程度上改變了我的
110、編程思想,如何將一個程序快速而又準備的進行編寫,進行編譯,都成為了我思考的重點。同時通過這一個學期的學習,我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學習中去。在這個階段,我也明白了,好的思想,不能提留于字面上的認知,還需要平時多練多寫一些相關(guān)的程序,并且通過修改,加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度,這才是關(guān)鍵。</p><p> 但在這次的課設中也遇了一些問題。做二叉樹之前,必須先構(gòu)思
111、出怎樣建立和想要實現(xiàn)那些功能。然后分塊去建立各自的模型。由于做好了這些工作,我的課程設計進行的還比較順利。但是,也出現(xiàn)一些很基礎很低級的錯誤,后來經(jīng)過自己的仔細分析,終于圓滿完成。這說明我的程序設計基礎還不是太扎實,還需要多上機實現(xiàn),不能陷入只看不做的誤區(qū)。</p><p> 通過這次的課程設計,我從中得到了許多經(jīng)驗和軟件設計的一些新思路。從二叉樹問題設計以及分析中,我理解到了數(shù)據(jù)結(jié)構(gòu)對于軟件設計的重要性。它的
112、使用,可以改變軟件的運行周期,思路從繁化簡,并且都能夠通過其相關(guān)引導,將本身以前編程思想進行擴充,發(fā)展。這也是在這次課程設計中我所掌握得到的。</p><p> 二叉樹的基本操作是多種多樣的,由于水平有限,故不能做太大規(guī)模的設計。雖然程序規(guī)模不大,程序也都較基礎,但我依然為此付出了努力,仍免不了各種錯誤的出現(xiàn)。編程過程需要很大的毅力和耐心,而且要有良好的思維和扎實的專業(yè)基礎知識,所以我需要不斷努力的學習,發(fā)現(xiàn)自
113、身不足之處并努力改正它,逐步提高自身的能力,不斷取得進步。通過實踐,我認識到知識運用的重要性,并且努力加深對基礎知識的理解,從中了解自己需要學習的東西并學會自學。作為一名計算機專業(yè)的學生,今后我會加緊學習,為將來打下堅實的基礎。</p><p><b> 參考文獻</b></p><p> 嚴蔚敏,吳偉民,數(shù)據(jù)結(jié)構(gòu)(C語言版).北京:清華大學出版社,2007<
114、;/p><p> 嚴蔚敏,吳偉民,數(shù)據(jù)結(jié)構(gòu)題集(C語言版).北京:清華大學出版社,2007</p><p> 高一凡,《數(shù)據(jù)結(jié)構(gòu)》算法實現(xiàn)及解析.西安:西安電子科技大學出版社,2005 </p><p> 譚浩強,C程序設計(第四版).北京:清華大學出版社,2010</p><p><b> 附錄 </b>&l
115、t;/p><p><b> 致謝</b></p><p> 在這次課程設計的撰寫過程中,我得到了許多人的幫助。</p><p> 首先我要感謝我的老師在課程設計上給予我的指導、提供給我的支持和幫助,本次課程設計是在王淑禮老師的悉心指導下完成的,老師淵博的知識,嚴謹?shù)闹螌W態(tài)度,一絲不茍的工作作風,平易近人的性格都是我學習的楷模。在課程設計的研究
116、及整理期間,,我遇到了不少問題,主要包括程序和課程設計的撰寫上的,老師給了我很大的支持和鼓勵,才使得論文得以順利的完成,這是我能順利完成這次報告的主要原因,更重要的是老師幫我解決了許多技術(shù)上的難題,讓我能把系統(tǒng)做得更加完善。在此期間,我不僅學到了許多新的知識,而且也開闊了視野,提高了自己的設計能力。</p><p> 其次,我要感謝幫助過我的同學,他們也為我解決了不少我不太明白的設計商的難題。在作課程設計期間,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二叉樹的基本操作課程設計
- 二叉樹課程設計
- 數(shù)據(jù)結(jié)構(gòu)課程設計-二叉樹的基本操作
- 遍歷二叉樹課程設計
- 課程設計 排序二叉樹
- 平衡二叉樹匹配課程設計
- 平衡二叉樹匹配課程設計
- 數(shù)據(jù)結(jié)構(gòu)課程設計---二叉樹的操作
- 課程設計---判斷完全二叉樹
- 課程設計---二叉樹的查找
- 數(shù)據(jù)結(jié)構(gòu)與算法課程設計--線索二叉樹的基本操作
- 數(shù)據(jù)結(jié)構(gòu)課程設計--二叉樹的相關(guān)操作
- 課程設計---完全二叉樹的判斷
- 二叉樹數(shù)據(jù)結(jié)構(gòu)課程設計
- 二叉樹論文 二叉樹的應用
- ds課程設計報告--平衡二叉樹
- 《數(shù)據(jù)結(jié)構(gòu)遍歷二叉樹》課程設計
- 《數(shù)據(jù)結(jié)構(gòu)》課程設計--二叉排序樹調(diào)整為平衡二叉樹
- 數(shù)據(jù)結(jié)構(gòu)課程設計---計算二叉樹高度
- 數(shù)據(jù)結(jié)構(gòu)課程設計----二叉樹的應用
評論
0/150
提交評論