二叉树染色问题

数据结构上机实验报告题目：二叉树染色问题学生姓名学生学号学院名称计算机学院专业计算机科学与技术时间2014.10.22I目录TOC\o"1-2"\h\u28542第一章需求分析 1310631.1原题表述 1257231.2问题解决方案 13957第二章概要设计 2302202.1抽象数据类型 2178302.2主要算法分析 2242992.3主要算法描述 31106第三章详细设计 4256443.1程序代码 410588第四章调试分析 7278404.1出现的问题及解决方法 726151第五章测试分析 8312105.1测试样例 8 计算机学院2013级数据结构上机实验报告PAGE8需求分析1.1原题表述一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”：例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示现在要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。1.2问题解决方案1.根据输入的二叉树序列构建二叉树，规定：当一个结点只有一个孩子时，令其为左孩子当n=0时表示叶结点；当n=1时表示左孩子当n=2时表示两个孩子2.为二叉树染色，以subroot为根结点，color表示当前颜色，modle表示当前结点左右染色的两种情况（例如，当前结点为绿色，其左右孩子的染色情况为左红右蓝或左蓝右红两种情况），递归左子树，右子树。3.中序遍历二叉树，记录绿色节点的数目，保存数据。4.比较数据，输出最大值，最小值。

第二章概要设计2.1抽象数据类型ADTBinaryTree{数据对象D:D是具有相同特性的数据元素的集合数据关系R:

若D≠Φ，则R={H}，H是如下二元关系；

（1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；

（2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr=Φ；

（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存在。操作结果：中序遍历二叉树Color(structnode*subroot,stringcolor,intmodle)初始条件：二叉树已存在操作结果：为二叉树着色}ADTBinaryTree2.2主要算法分析CreatTree(）的时间复杂度为O（n)InorderTraverse()的时间复杂度为O（n)Color()的时间复杂度为O（n)2.3主要算法描述

第三章详细设计3.1程序代码#include<iostream>#include<string>usingnamespacestd;structnode{stringcolor; structnode*lchild;structnode*rchild;};//二叉树的结点类型intcount=0;//用于记录绿色结点个数staticinti=0;//输入字符的下标conststringnodecolor[3]={"red","blue","green"};//用字符串数组存储节点的三种颜色/*根据输入的二叉树序列构建二叉树，规定：当一个结点只有一个孩子时，令其为左孩子当n=0时表示叶结点；当n=1时表示左孩子当n=2时表示两个孩子*/structnode*CreatTree(stringstr){structnode*p;if(i>=str.length())returnNULL;intn=int(str[i++]-48);p=newstructnode();p->color=char(i+48);if(n==0){p->lchild=NULL;p->rchild=NULL;returnp;}else{if(n==1){p->lchild=CreatTree(str);p->rchild=NULL;}if(n==2){p->lchild=CreatTree(str);p->rchild=CreatTree(str);}}returnp;}//中序遍历二叉树，统计绿色结点的个数voidInorderTraverse(structnode*root){if(root){InorderTraverse(root->lchild);if(root->color=="green")count++;InorderTraverse(root->rchild);}}/*为二叉树染色，以subroot为根结点，color表示当前颜色，modle表示当前结点左右染色的两种情况（例如，当前结点为绿色，其左右孩子的染色情况为左红右蓝或左蓝右红两种情况），递归左子树，右子树*/voidColor(structnode*subroot,stringcolor,intmodle){stringstr[2];inttemp=0;if(subroot==NULL)return;subroot->color=color;for(inti=0;i<3;i++)if(nodecolor[i]!=color)str[temp++]=nodecolor[i];if(modle==0){Color(subroot->lchild,str[0],modle);Color(subroot->rchild,str[1],modle);}else{Color(subroot->rchild,str[0],modle);Color(subroot->lchild,str[1],modle);}}intmain(){ stringorder;cin>>order;intmax=-1,min=1000000;structnode*p=CreatTree(order);for(intj=0;j<2;j++)//两种情况 {for(inti=0;i<3;i++)//三种颜色 {Color(p,nodecolor[i],j);InorderTraverse(p);if(max<count)max=count;if(min>count)min=count;count=0;}}cout<<max<<""<<min<<endl;return0;}