版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、課程設(shè)計(jì)唯一的確定一棵二叉樹設(shè)計(jì)時(shí)間:2011 年 4 月 18樹、圖及其應(yīng)用題目:唯一的確定一棵二叉樹實(shí)習(xí)時(shí)間:2011.4.15一、需求分析:1. 如果給出了遍歷二叉樹的前序序列和中序序列,則可以構(gòu)造出唯一的一棵二叉樹。 試編寫實(shí)現(xiàn)上述功能的程序。已知一棵二叉樹的前序和中序序列,設(shè)計(jì)完成下列任務(wù)的一個(gè)算法:( 1)構(gòu)造一棵二叉樹;( 2)證明構(gòu)造正確(即分別以前序和中序遍歷該樹,將得到的結(jié)果與給出的序列進(jìn)行比較)。2. 測(cè)試數(shù)據(jù):前序序列為ABDEGCFH,中序序列為IJDBGEAHFIJ。 C二、設(shè)計(jì):設(shè)計(jì)思想( 1)存儲(chǔ)結(jié)構(gòu): 二叉樹 ,用兩個(gè)一維數(shù)組A 和 B 分別存放前序和中序序列
2、。( 2)主要算法基本思想:將前序和中序序列分別讀入數(shù)組A和 B。根據(jù)定義,前序序列中第一個(gè)元素一定是樹根,在中序序列中該元素之前的所有元素一定在左子樹中,其余元素則在右子樹中。所以, 首先從數(shù)組A中取出第一個(gè)元素A0 作根結(jié)點(diǎn),然后在數(shù)組B 中找到 A0 ,以它為界,在其前面的是左子樹中序序列,在其后面的是右子樹中序序列。若左子樹不為空,沿前序序列向后移動(dòng),找到左子樹根結(jié)點(diǎn),轉(zhuǎn)。左子樹構(gòu)造完畢后,若右子樹不為空,沿前序序列向后移動(dòng),找到右子樹根結(jié)點(diǎn),轉(zhuǎn)。前序序列中各元素取完則二叉樹構(gòu)造完畢。對(duì)二叉樹進(jìn)行前序和中序遍歷,并將結(jié)果分別與數(shù)組A和 B進(jìn)行比較,若相同,則證明二叉樹構(gòu)造正確。設(shè)計(jì)表示
3、( 1)函數(shù)調(diào)用關(guān)系圖: main InitiateCreateTree PrintBiTreePreOrder VisitInOrder Visit PostOrder( 2)函數(shù)接口規(guī)格說明:void Initiate(BiTNode *root)/ 初始化二叉樹的頭結(jié)點(diǎn)void Visit(char item)/ 訪問操作void PreOrder(BiTNode *T,void Visit(char item)/前序遍歷二叉樹void InOrder(BiTNode *T,void Visit(char item)/中序遍歷二叉樹void PostOrder(BiTNode *T,vo
4、id Visit(char item)/后序遍歷二叉樹void PrintBiTree(BiTNode *T,int n)/ 顯示二叉樹void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char pre,char in)/ 按要求創(chuàng)建二叉樹實(shí)現(xiàn)注釋( 1)根據(jù)前序遍歷和后序遍歷創(chuàng)建二叉樹,并后序遍歷該二叉樹。( 2)二叉樹逆轉(zhuǎn)90 度來顯示。詳細(xì)設(shè)計(jì)總體來說,本程序設(shè)計(jì)相對(duì)比較簡單,主要包括七個(gè)功能模塊:初始化函數(shù)、 前序遍歷二叉樹函數(shù)、中序遍歷二叉樹函數(shù)、后序遍歷二叉樹函數(shù)、顯示函數(shù)、創(chuàng)建二叉樹函數(shù)、主函數(shù)。下面
5、分別給予介紹:初始化函數(shù)void Initiate(BiTNode *root)*root=(BiTNode *)malloc(sizeof(BiTNode);(*root)->LeftChild=NULL;(*root)->RightChild=NULL;前序遍歷二叉樹函數(shù)void PreOrder(BiTNode *T,void Visit(char item) if(T!=NULL)Visit(T->data);PreOrder(T->LeftChild,Visit);PreOrder(T->RightChild,Visit);中序遍歷二叉樹函數(shù)void I
6、nOrder(BiTNode *T,void Visit(char item)if(T!=NULL)InOrder(T->LeftChild,Visit);Visit(T->data);InOrder(T->RightChild,Visit);后序遍歷二叉樹函數(shù)void PostOrder(BiTNode *T,void Visit(char item) if(T!=NULL)PostOrder(T->LeftChild,Visit);PostOrder(T->RightChild,Visit);Visit(T->data);顯示函數(shù)void PrintBi
7、Tree(BiTNode *T,int n)int i;if(T=NULL) return;PrintBiTree(T->RightChild,n+1);for(i=0;i<n;i+) printf(" ");if(n>=0)printf(" ");printf("%cnn",T->data);PrintBiTree(T->LeftChild,n+1);創(chuàng)建二叉樹函數(shù)void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char
8、pre,char in)int interval=0;/int same=in_f;if(prepre_f!=insame)while(prepre_f!=insame)/ 在中序序列中找到根節(jié)點(diǎn)same+;interval+;if(interval=0)&&(pre_f=pre_l) / 找到了葉節(jié)點(diǎn),也是遞歸出口T->data=prepre_f;T->LeftChild=NULL;T->RightChild=NULL;if(interval!=0)&&(interval<pre_l-pre_f) /同時(shí)存在左子樹和右子樹T->L
9、eftChild=(BiTNode *)malloc(sizeof(BiTNode);T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_f+interval,in_f,in_f+interval-1,p re,in);CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);if(interval!=0)&&
10、(interval=pre_l-pre_f)/只有左子樹T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_l,in_f,in_f+interval-1,pre,in); T->RightChild=NULL;if(interval=0)&&(pre_f!=pre_l)/ 只有右子樹T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=pr
11、epre_f;T->LeftChild=NULL;CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);主函數(shù)void main()BiTNode *T;int Pre_len,In_len;char PreMaxSize;/ 前序序列char InMaxSize;/ 中序序列printf(" 請(qǐng)輸入前序序列:n");scanf("%s",&Pre);Pre_len=strlen(Pre);printf(" 請(qǐng)輸入中序序列:
12、n");scanf("%s",&In);In_len=strlen(In);Initiate(&T);CreateTree(T,0,Pre_len-1,0,In_len-1,Pre,In);printf(" 二叉樹構(gòu)造成功!n");printf("逆時(shí)針旋轉(zhuǎn)90 度的二叉樹如下所示:n");PrintBiTree(T,0);printf("前序序列:n");PreOrder(T,Visit);printf("n中序序列:n");InOrder(T,Visit);prin
13、tf("n后序序列:n");PostOrder(T,Visit);printf("n");三、調(diào)試分析:本程序在設(shè)計(jì)過程中遇到一個(gè)難題,那就是如何正確顯示所構(gòu)造的二叉樹,試了幾種方法都不理想,最后想到讓二叉樹逆時(shí)針旋轉(zhuǎn)后再顯示,具備可行性,同時(shí)也使之更美觀。經(jīng)驗(yàn)和體會(huì)經(jīng)過第一次一元稀疏多項(xiàng)式加法的課程設(shè)計(jì),這次課程設(shè)計(jì)就顯得輕車熟路了,運(yùn)算的主要設(shè)計(jì)思路很容易想到,大體設(shè)計(jì)結(jié)構(gòu)在較短時(shí)間內(nèi)能夠完成,但當(dāng)設(shè)計(jì)到具體細(xì)節(jié)代碼時(shí)遇到了一些困難,主要困難是進(jìn)行結(jié)點(diǎn)操作時(shí),對(duì)指針考慮得不夠細(xì)致,調(diào)試時(shí)常出現(xiàn)指針指錯(cuò)的情況,沒有認(rèn)真理清條件層次,另一個(gè)困難是如何正確
14、顯示所構(gòu)造的二叉樹。雖然程序可能并不是最高效的,而且不夠健壯,但也符合題目的要求,總的來說本次課程設(shè)計(jì)還算圓滿。本次課程設(shè)計(jì)培養(yǎng)了我對(duì)實(shí)際問題的分析能力以及解決一些實(shí)際問題的能力, 鞏固了我的編程思想和寫程序的能力。課程設(shè)計(jì)是對(duì)我們的學(xué)習(xí)很有利的一個(gè)環(huán)節(jié), 在這個(gè)階段,我們學(xué)會(huì)把理論與實(shí)際的結(jié)合、懂得人與人溝通的重要性,通過這次課程設(shè)計(jì)中,我加深了對(duì)課本知識(shí)的理解。四、用戶手冊(cè):本 程 序 在 Vi sual C + 6. 0 下 運(yùn) 行 。先輸入前序遍歷序列,回車,再輸入中序遍歷序列,再回車,即可得出結(jié)果。五、運(yùn)行結(jié)果:六、源程序清單:#include <stdio.h>#inc
15、lude <Stdlib.h>#include <string.h>#define MaxSize 50 typedef struct Node char data;struct Node *LeftChild;struct Node *RightChild;BiTNode;void Initiate(BiTNode *root)*root=(BiTNode *)malloc(sizeof(BiTNode);(*root)->LeftChild=NULL;(*root)->RightChild=NULL;void Visit(char item)printf
16、("%c",item);void PreOrder(BiTNode *T,void Visit(char item)if(T!=NULL)Visit(T->data);PreOrder(T->LeftChild,Visit);PreOrder(T->RightChild,Visit);void InOrder(BiTNode *T,void Visit(char item)if(T!=NULL)InOrder(T->LeftChild,Visit);Visit(T->data);InOrder(T->RightChild,Visit);v
17、oid PostOrder(BiTNode *T,void Visit(char item)if(T!=NULL)PostOrder(T->LeftChild,Visit);PostOrder(T->RightChild,Visit);Visit(T->data);void PrintBiTree(BiTNode *T,int n)int i;if(T=NULL) return;PrintBiTree(T->RightChild,n+1);for(i=0;i<n;i+) printf(" ");if(n>=0) printf("
18、 ");printf("%cnn",T->data);PrintBiTree(T->LeftChild,n+1);void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char pre,char in)int interval=0;/int same=in_f;if(prepre_f!=insame) while(prepre_f!=insame)/ 在中序序列中找到根節(jié)點(diǎn)same+;interval+;if(interval=0)&&(pre_f=pre_l)
19、 / 找到了葉節(jié)點(diǎn),也是遞歸出口T->data=prepre_f;T->LeftChild=NULL;T->RightChild=NULL;if(interval!=0)&&(interval<pre_l-pre_f) /同時(shí)存在左子樹和右子樹T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pr
20、e_f+interval,in_f,in_f+interval-1,p re,in);CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);if(interval!=0)&&(interval=pre_l-pre_f)/只有左子樹T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_l,in_f,in_f+interval-1,pre,in);T->RightChild=NULL;if(interval=0)&&(pre_f!=pre_l)/ 只有右子樹T->RightChild=(BiTNode *)malloc(sizeof(BiT
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 初中模擬試卷:知識(shí)考查篇
- 2020年遼寧錦州中考滿分作文《喚醒那個(gè)盛夏》
- 縫制設(shè)備智能化改造考核試卷
- 體育用品店電商運(yùn)營與網(wǎng)絡(luò)營銷考核試卷
- 關(guān)于醫(yī)院藥品管理制度的全面修訂通知
- 銅壓延加工中的成本效益分析考核試卷
- 蜜餞制作與食品加工自動(dòng)化技術(shù)考核試卷
- 陶瓷產(chǎn)業(yè)的技術(shù)創(chuàng)新與專利戰(zhàn)略考核試卷
- 鄉(xiāng)村旅游消費(fèi)者需求趨勢(shì)分析
- 麻織品染色與印花技術(shù)考核試卷
- 2024年共青團(tuán)入團(tuán)積極分子考試題庫(附答案)
- 2069-3-3101-002WKB產(chǎn)品判定準(zhǔn)則-外發(fā)
- 拼音練習(xí)字帖(打印版)
- GB/T 6495.1-1996光伏器件第1部分:光伏電流-電壓特性的測(cè)量
- 完整版:美制螺紋尺寸對(duì)照表(牙數(shù)、牙高、螺距、小徑、中徑外徑、鉆孔)
- 第十二章土工合成材料ppt課件
- 滬教版二年級(jí)上冊(cè)《7的乘、除法》數(shù)學(xué)教案
- 舞蹈演員職稱評(píng)審個(gè)人總結(jié).doc
- 電氣設(shè)備安裝工程工程量計(jì)算經(jīng)典實(shí)例
- 急性腸系膜淋巴結(jié)炎臨床路徑標(biāo)準(zhǔn)住院流程
- 車輛租賃合同范本
評(píng)論
0/150
提交評(píng)論