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

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

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

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

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

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

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