二叉樹染色問題

1、數(shù)據(jù)結(jié)構(gòu)上機實驗報告 題目：二叉樹染色問題 學生姓名 學生學號 學院名稱 計算機學院 專 業(yè) 計算機科學與技術(shù) 時 間 2014.10.22 目 錄 第一章 需求分析11.1 原題表述11.2 問題解決方案1 第二章 概要設(shè)計22.1 抽象數(shù)據(jù)類型22.2 主要算法分析22.3 主要算法描述3 第三章 詳細設(shè)計43.1 程序代碼4 第四章 調(diào)試分析74.1 出現(xiàn)的問題及解決方法7 第五章 測試分析85.1 測試樣例8 I計算機學院2013級數(shù)據(jù)結(jié)構(gòu)上機實驗報告第1章 需求分析1.1 原題表述一棵二叉樹可以按照如下規(guī)則表示成一個由0、1、2組成的字符序列，我們稱之為“二叉樹序列S”：例如，下圖所

2、表示的二叉樹可以用二叉樹序列S=21200110來表示現(xiàn)在要對一棵二叉樹的節(jié)點進行染色。每個節(jié)點可以被染成紅色、綠色或藍色。并且，一個節(jié)點與其子節(jié)點的顏色必須不同，如果該節(jié)點有兩個子節(jié)點，那么這兩個子節(jié)點的顏色也必須不相同。給定一棵二叉樹的二叉樹序列，請求出這棵樹中最多和最少有多少個點能夠被染成綠色。1.2 問題解決方案1.根據(jù)輸入的二叉樹序列構(gòu)建二叉樹，規(guī)定：當一個結(jié)點只有一個孩子時，令其為左孩子當n = 0時表示葉結(jié)點；當n = 1時表示左孩子當n = 2時表示兩個孩子2.為二叉樹染色，以subroot為根結(jié)點，color表示當前顏色，modle表示當前結(jié)點左右染色的兩種情況（例如，當前結(jié)

3、點為綠色，其左右孩子的染色情況為 左紅右藍 或 左藍右紅 兩種情況），遞歸左子樹，右子樹。3.中序遍歷二叉樹，記錄綠色節(jié)點的數(shù)目，保存數(shù)據(jù)。4.比較數(shù)據(jù)，輸出最大值，最小值。第二章 概要設(shè)計2.1 抽象數(shù)據(jù)類型ADT BinaryTree數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R:  若D，則R=H，H是如下二元關(guān)系；      （1）在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(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)是一棵符合本定義的二叉樹，稱為根的左子樹；(Dr,Hr)是一棵符合本定義的二叉樹，稱為根的右子樹。 基本操作：CreatTree()操作結(jié)果：構(gòu)造二叉樹。InorderTraverse(T)初始條件：二叉樹T存在。操作結(jié)果：中序遍歷二叉樹Co

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

6、; struct node *rchild;/二叉樹的結(jié)點類型 int count = 0; /用于記錄綠色結(jié)點個數(shù) static int i = 0; /輸入字符的下標 const string nodecolor3="red","blue","green" /用字符串數(shù)組存儲節(jié)點的三種顏色 /*根據(jù)輸入的二叉樹序列構(gòu)建二叉樹，規(guī)定：當一個結(jié)點只有一個孩子時，令其為左孩子當n = 0時表示葉結(jié)點；當n = 1時表示左孩子當n = 2時表示兩個孩子 */ 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;/中序遍歷二叉樹，統(tǒng)計綠色結(jié)點的個數(shù) void InorderTraverse(struct node* root) if(root) InorderTraverse(root->lchild); if(root->color = "green") count+; InorderTraverse(root->rchild); /*為二叉樹染色，以subroot為根結(jié)點，color表示當前顏色，modle表示當前結(jié)點左右染色的兩種情況（例如，當前結(jié)點為綠色，其左右孩子的染色情況為 左紅右藍 或 左藍右紅

9、 兩種情況），遞歸左子樹，右子樹 */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