二叉樹(shù)染色問(wèn)題

1、數(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í) 間 2014.10.22 目 錄 第一章 需求分析11.1 原題表述11.2 問(wèn)題解決方案1 第二章 概要設(shè)計(jì)22.1 抽象數(shù)據(jù)類型22.2 主要算法分析22.3 主要算法描述3 第三章 詳細(xì)設(shè)計(jì)43.1 程序代碼4 第四章 調(diào)試分析74.1 出現(xiàn)的問(wèn)題及解決方法7 第五章 測(cè)試分析85.1 測(cè)試樣例8 I計(jì)算機(jī)學(xué)院2013級(jí)數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告第1章 需求分析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 問(wèn)題解決方案1.根據(jù)輸入的二叉樹(shù)序列構(gòu)建二叉樹(shù)，規(guī)定：當(dāng)一個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)，令其為左孩子當(dāng)n = 0時(shí)表示葉結(jié)點(diǎn)；當(dāng)n = 1時(shí)表示左孩子當(dāng)n = 2時(shí)表示兩個(gè)孩子2.為二叉樹(shù)染色，以subroot為根結(jié)點(diǎn)，color表示當(dāng)前顏色，modle表示當(dāng)前結(jié)點(diǎn)左右染色的兩種情況（例如，當(dāng)前結(jié)

3、點(diǎn)為綠色，其左右孩子的染色情況為 左紅右藍(lán) 或 左藍(lán)右紅 兩種情況），遞歸左子樹(shù)，右子樹(shù)。3.中序遍歷二叉樹(shù)，記錄綠色節(jié)點(diǎn)的數(shù)目，保存數(shù)據(jù)。4.比較數(shù)據(jù)，輸出最大值，最小值。第二章 概要設(shè)計(jì)2.1 抽象數(shù)據(jù)類型ADT BinaryTree數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R:  若D，則R=H，H是如下二元關(guān)系；      （1）在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；  （2）若D-root，則存在D-root=D1,Dr，且D1Dr =；      （

4、3）若D1，則D1中存在惟一的元素x1，<root,x1>H，且存在D1上的關(guān)系H1 H；若Dr，則Dr中存在惟一的元素xr，<root,xr>H，且存在上的關(guān)系Hr H；H=<root,x1>,<root,xr>,H1,Hr；      （4）(D1,H1)是一棵符合本定義的二叉樹(shù)，稱為根的左子樹(shù)；(Dr,Hr)是一棵符合本定義的二叉樹(shù)，稱為根的右子樹(shù)。 基本操作：CreatTree()操作結(jié)果：構(gòu)造二叉樹(shù)。InorderTraverse(T)初始條件：二叉樹(shù)T存在。操作結(jié)果：中序遍歷二叉樹(shù)Co

5、lor(struct node *subroot,string color,int modle)初始條件：二叉樹(shù)已存在操作結(jié)果：為二叉樹(shù)著色ADT BinaryTree2.2 主要算法分析CreatTree(）的時(shí)間復(fù)雜度為O（n)InorderTraverse()的時(shí)間復(fù)雜度為O（n)Color()的時(shí)間復(fù)雜度為O（n)2.3 主要算法描述 第三章 詳細(xì)設(shè)計(jì)3.1 程序代碼#include<iostream>#include<string>using namespace std; struct node string color;struct node *lchild

6、; struct node *rchild;/二叉樹(shù)的結(jié)點(diǎn)類型 int count = 0; /用于記錄綠色結(jié)點(diǎn)個(gè)數(shù) static int i = 0; /輸入字符的下標(biāo) const string nodecolor3="red","blue","green" /用字符串?dāng)?shù)組存儲(chǔ)節(jié)點(diǎn)的三種顏色 /*根據(jù)輸入的二叉樹(shù)序列構(gòu)建二叉樹(shù)，規(guī)定：當(dāng)一個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)，令其為左孩子當(dāng)n = 0時(shí)表示葉結(jié)點(diǎn)；當(dāng)n = 1時(shí)表示左孩子當(dāng)n = 2時(shí)表示兩個(gè)孩子 */ struct node *CreatTree(string str) struc

7、t node *p; if(i >= str.length() return NULL; int n = int(stri+-48); p=new struct node(); p->color = char(i+48); if(n = 0) p->lchild = NULL; p->rchild = NULL; return p; else if(n = 1) p->lchild = CreatTree(str); p->rchild = NULL; if(n = 2) p->lchild = CreatTree(str); p->rchild

8、 = CreatTree(str); return p;/中序遍歷二叉樹(shù)，統(tǒng)計(jì)綠色結(jié)點(diǎn)的個(gè)數(shù) void InorderTraverse(struct node* root) if(root) InorderTraverse(root->lchild); if(root->color = "green") count+; InorderTraverse(root->rchild); /*為二叉樹(shù)染色，以subroot為根結(jié)點(diǎn)，color表示當(dāng)前顏色，modle表示當(dāng)前結(jié)點(diǎn)左右染色的兩種情況（例如，當(dāng)前結(jié)點(diǎn)為綠色，其左右孩子的染色情況為 左紅右藍(lán) 或 左藍(lán)右紅

9、 兩種情況），遞歸左子樹(shù)，右子樹(shù) */void Color(struct node *subroot, string color, int modle) string str2; int temp = 0; if(subroot = NULL)return; subroot->color = color; for(int i = 0; i < 3; i+) if(nodecolori != color) strtemp+ = nodecolori; if(modle=0) Color(subroot->lchild, str0, modle); Color(subroot-&

10、gt;rchild, str1, modle); else Color(subroot->rchild, str0, modle); Color(subroot->lchild, str1, modle); int main()string order; cin >> order; int max = -1, min = 1000000; struct node *p = CreatTree(order); for(int j = 0; j < 2; j+) /兩種情況 for(int i = 0; i < 3; i+) /三種顏色 Color(p, nodecolori, j); InorderTraverse(p); if(max < count) max = count; if(min > count) min = count; count = 0; cout << max << " " << min << endl; return