數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告(二叉樹(shù)染色問(wèn)題)

1、計(jì)算機(jī)學(xué)院2013級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告題目：二叉樹(shù)染色問(wèn)題 學(xué)生姓名：學(xué)生學(xué)號(hào)：學(xué)院名稱：計(jì)算機(jī)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)時(shí)間：目 錄第一章，需求分析 31.1 原題描述31.2 詳細(xì)問(wèn)題的解決方案31.2.1 解決方案要求3 1.2.2 各個(gè)環(huán)節(jié)功能要求3第二章，概要設(shè)計(jì) 52.1 抽象數(shù)據(jù)類型52.2 主要算法描述52.3 算法分析7第三章，詳細(xì)設(shè)計(jì) 8 3.1 程序代碼8第四章，調(diào)試分析 10第五章，測(cè)試分析 11第六章，未來(lái)展望與思考 12第一章 需求分析1.1 原題描述一棵二叉樹(shù)可以按照如下規(guī)則表示成一個(gè)由0、1、2組成的字符序列，我們稱之為“二叉樹(shù)序列S”：例如，下圖

2、所表示的二叉樹(shù)可以用二叉樹(shù)序列S=21200110來(lái)表示現(xiàn)在要對(duì)一棵二叉樹(shù)的節(jié)點(diǎn)進(jìn)行染色。每個(gè)節(jié)點(diǎn)可以被染成紅色、綠色或藍(lán)色。并且，一個(gè)節(jié)點(diǎn)與其子節(jié)點(diǎn)的顏色必須不同，如果該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，那么這兩個(gè)子節(jié)點(diǎn)的顏色也必須不相同。給定一棵二叉樹(shù)的二叉樹(shù)序列，請(qǐng)求出這棵樹(shù)中最多和最少有多少個(gè)點(diǎn)能夠被染成綠色。1.2詳細(xì)問(wèn)題的解決方案1.2.1 解決方案要求輸入?yún)?shù):輸入數(shù)據(jù)由多組數(shù)據(jù)組成。每組數(shù)據(jù)僅有一行，不超過(guò)10000個(gè)字符，表示一個(gè)二叉樹(shù)序列。輸出參數(shù)：對(duì)于每組輸入數(shù)據(jù)，輸出僅一行包含兩個(gè)整數(shù)，依次表示最多和最少有多少個(gè)點(diǎn)能夠被染成綠色。1.2.2 參考樣例Sample Input112200

3、2010 Sample Output5 21.2.3 各個(gè)環(huán)節(jié)功能要求表1-2.1 環(huán)節(jié)功能 函數(shù)功能注意條件及限制規(guī)則CreatBitree()先序建立二叉樹(shù)字符2字符1字符0三種情況：,2，有左右子樹(shù)；1，有左子樹(shù)右空；0，左右子樹(shù)為空PreOrder()先序遍歷二叉樹(shù)以T是否為空遍歷二叉樹(shù)補(bǔ)充正文：由于只有三種顏色，可以用數(shù)字2,1,0分別表示，先序建立二叉樹(shù)，將二叉樹(shù)每個(gè)結(jié)點(diǎn)與其左孩子強(qiáng)行交叉賦值2與1（有右孩子的則賦予與結(jié)點(diǎn)和左孩子不同的值），即為按優(yōu)先順序2,1,0給節(jié)點(diǎn)賦值。并運(yùn)用遞歸算法建立子樹(shù)，最后計(jì)算結(jié)點(diǎn)數(shù)字個(gè)數(shù)最多的那一項(xiàng)，與最小的那一項(xiàng)，即為這棵子樹(shù)中最多和最少有多少個(gè)

4、點(diǎn)染成綠色。 第二章 概要設(shè)計(jì)2.1 抽象數(shù)據(jù)類型ADT BinaryTree 數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R：若D=，則R=，稱BinaryTree為空二叉樹(shù)；若D=, 則R=H,H是如下關(guān)系： （1）在D中存在唯一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無(wú)前驅(qū)； （2）若D-root，則存在D-root=D1，Dr,且D1Dr=； （3）若D1，則D1中存在惟一的元素X1，<root,X1>H,且存在D1上的關(guān)系H1H；若Dr,則Dr中存在惟一的元素Xr,<root,X1>H,且存在Dr上的關(guān)系HrH;H=<root,X1>,

5、<root,Xr>，H1，Hr; （4）（D1，H1）是一棵符合本定義的二叉樹(shù)，稱為根的左子樹(shù)，（Dr,Hr）是一棵符合本定義的二叉樹(shù)，稱為根的右子樹(shù)?；静僮鱌： IniBiTree(&T)； 操作結(jié)果：構(gòu)造空二叉樹(shù)T。 DestroyBiTree(&T); 初始條件:二叉樹(shù)T存在。 操作結(jié)果：銷毀二叉樹(shù)。CreateBiTree(&T) 初始條件：二叉樹(shù)存在。 操作結(jié)果：先序建立二叉樹(shù)PreOrder（&T） 初始條件：二叉樹(shù)存在。 操作結(jié)果：先序遍歷T，并計(jì)算不同數(shù)值的節(jié)點(diǎn)個(gè)數(shù)。 ADT BinaryTree；2.2主要算法描述2.3算法分析T

6、(n)=O(n)因?yàn)楫?dāng)輸入都為2時(shí)，為最壞情況的運(yùn)行時(shí)間，即T(n)=2T(n/2)所以可以通過(guò)猜答案的方法計(jì)算出T(n)=O(n)。第三章 詳細(xì)設(shè)計(jì)3.1 程序代碼#include<iostream>using namespace std;static int b=3,c=3;static int a3;/定義為靜態(tài)變量 typedef int TreeData;typedef struct nodeTreeData data;struct node *lchild,*rchild;BinTreeNode;typedef BinTreeNode *BinTree;void Cre

7、atBitree(BinTree &T)/先序建立二叉樹(shù) char a; cin>>a; if(!(T=(BinTreeNode*)malloc(sizeof(node)/建立根結(jié)點(diǎn) return; /用數(shù)字2,1,0分別表示三種不同顏色 if(b!=c)/令b,c表示左孩子和根的數(shù)值 if(b=0&&c=2)|(c=0&&b=2)/右孩子的賦值取決于左孩子與根的值 T->data=1; else if(b=1&&c=0)|(c=1&&b=0) T->data=2; else T->data=

8、0; else /由于是先序建立強(qiáng)行將2和1交叉賦值給根和左孩子 if(b=2) T->data=1; else T->data=2; b=c=T->data;if(a='2')/當(dāng)輸入值為2時(shí)，遞歸建立兩個(gè)孩子 CreatBitree(T->lchild);b=T->lchild->data;/b賦值左孩子的值 c=T->data;/c賦值根的值 CreatBitree(T->rchild);else if(a='1')/當(dāng)輸入值為1時(shí)，遞歸建立一個(gè)左孩子 CreatBitree(T->lchild); T

9、->rchild=NULL;else/輸入為0時(shí)無(wú)孩子 T->lchild=NULL; T->rchild=NULL; void PreOrder(BinTree T)/先序遍歷 if(T!=NULL)aT->data+;/分別計(jì)算節(jié)點(diǎn)值為0,1,2的個(gè)數(shù) PreOrder(T->lchild);PreOrder(T->rchild);int main() BinTree T; CreatBitree(T); PreOrder(T); int min=a0; int max=a0; for(int i=0;i<3;i+)/查找數(shù)組中的最大值與最小值 i

10、f(ai<min) min=ai; else max=ai; cout<<max<<" "<<min<<endl;system ("pause");return 0;第四章 調(diào)試分析Bug 名稱不是具有顏色最多和顏色最少節(jié)點(diǎn)個(gè)數(shù)的二叉樹(shù)Bug描述數(shù)字0,1,2的最多最少個(gè)數(shù)不符合題目要求的5,2Bug原因用了rand()函數(shù)隨意給節(jié)點(diǎn)賦值，出現(xiàn)最優(yōu)的二叉樹(shù)幾率小Bug解決方案強(qiáng)制性按2,1,0優(yōu)先順序給節(jié)點(diǎn)賦值if(b!=c)/令b,c表示左孩子和自己的數(shù)值 if(b=0&&c=2)|

11、(c=0&&b=2) T->data=1; else if(b=1&&c=0)|(c=1&&b=0) T->data=2; else T->data=0; else if(b=2) T->data=1; else T->data=2; b=c=T->data;Bug總結(jié)要按照題意尋求最優(yōu)方案第五章 測(cè)試分析測(cè)試編號(hào)1 測(cè)試對(duì)象CreatBitree()函數(shù)（構(gòu)建染色后的二叉樹(shù)）測(cè)試輸入?yún)?shù)1122002010測(cè)試步驟1.調(diào)用CreatBitree()函數(shù)2.調(diào)用preorder()函數(shù)3.輸出先序遍歷后的二叉樹(shù)測(cè)試預(yù)期結(jié)果2121200212測(cè)試輸出結(jié)果測(cè)試分析預(yù)期結(jié)果與實(shí)際結(jié)果符合第六章 未來(lái)展望與思考6.1 思考與展望只有三種顏色給節(jié)點(diǎn)染色，可以用從簡(jiǎn)單的if語(yǔ)句解決，但是大于三種的顏色去染色該用什么樣的方法能夠讓程序按照自己所要求的顏色順序去給節(jié)點(diǎn)染色6.2 感想這道題非常讓我有成就感，舍友都覺(jué)