數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告(二叉樹染色問題)

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

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

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

4、點(diǎn)染成綠色。 第二章 概要設(shè)計2.1 抽象數(shù)據(jù)類型ADT BinaryTree 數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R：若D=，則R=，稱BinaryTree為空二叉樹；若D=, 則R=H,H是如下關(guān)系： （1）在D中存在唯一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無前驅(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）是一棵符合本定義的二叉樹，稱為根的左子樹，（Dr,Hr）是一棵符合本定義的二叉樹，稱為根的右子樹?；静僮鱌： IniBiTree(&T)； 操作結(jié)果：構(gòu)造空二叉樹T。 DestroyBiTree(&T); 初始條件:二叉樹T存在。 操作結(jié)果：銷毀二叉樹。CreateBiTree(&T) 初始條件：二叉樹存在。 操作結(jié)果：先序建立二叉樹PreOrder（&T） 初始條件：二叉樹存在。 操作結(jié)果：先序遍歷T，并計算不同數(shù)值的節(jié)點(diǎn)個數(shù)。 ADT BinaryTree；2.2主要算法描述2.3算法分析T

6、(n)=O(n)因為當(dāng)輸入都為2時，為最壞情況的運(yùn)行時間，即T(n)=2T(n/2)所以可以通過猜答案的方法計算出T(n)=O(n)。第三章 詳細(xì)設(shè)計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)/先序建立二叉樹 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時，遞歸建立兩個孩子 CreatBitree(T->lchild);b=T->lchild->data;/b賦值左孩子的值 c=T->data;/c賦值根的值 CreatBitree(T->rchild);else if(a='1')/當(dāng)輸入值為1時，遞歸建立一個左孩子 CreatBitree(T->lchild); T

9、->rchild=NULL;else/輸入為0時無孩子 T->lchild=NULL; T->rchild=NULL; void PreOrder(BinTree T)/先序遍歷 if(T!=NULL)aT->data+;/分別計算節(jié)點(diǎn)值為0,1,2的個數(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)個數(shù)的二叉樹Bug描述數(shù)字0,1,2的最多最少個數(shù)不符合題目要求的5,2Bug原因用了rand()函數(shù)隨意給節(jié)點(diǎn)賦值，出現(xiàn)最優(yōu)的二叉樹幾率小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)方案第五章 測試分析測試編號1 測試對象CreatBitree()函數(shù)（構(gòu)建染色后的二叉樹）測試輸入?yún)?shù)1122002010測試步驟1.調(diào)用CreatBitree()函數(shù)2.調(diào)用preorder()函數(shù)3.輸出先序遍歷后的二叉樹測試預(yù)期結(jié)果2121200212測試輸出結(jié)果測試分析預(yù)期結(jié)果與實際結(jié)果符合第六章 未來展望與思考6.1 思考與展望只有三種顏色給節(jié)點(diǎn)染色，可以用從簡單的if語句解決，但是大于三種的顏色去染色該用什么樣的方法能夠讓程序按照自己所要求的顏色順序去給節(jié)點(diǎn)染色6.2 感想這道題非常讓我有成就感，舍友都覺