二叉树染色问题

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