数据结构上机实验报告(二叉树染色问题)

1、计算机学院2013级数据结构实验数据结构上机实验报告题目：二叉树染色问题 学生姓名：学生学号：学院名称：计算机学院专业：计算机科学与技术时间：目 录第一章，需求分析 31.1 原题描述31.2 详细问题的解决方案31.2.1 解决方案要求3 1.2.2 各个环节功能要求3第二章，概要设计 52.1 抽象数据类型52.2 主要算法描述52.3 算法分析7第三章，详细设计 8 3.1 程序代码8第四章，调试分析 10第五章，测试分析 11第六章，未来展望与思考 12第一章 需求分析1.1 原题描述一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”：例如，下图

2、所表示的二叉树可以用二叉树序列S=21200110来表示现在要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。1.2详细问题的解决方案1.2.1 解决方案要求输入参数:输入数据由多组数据组成。每组数据仅有一行，不超过10000个字符，表示一个二叉树序列。输出参数：对于每组输入数据，输出仅一行包含两个整数，依次表示最多和最少有多少个点能够被染成绿色。1.2.2 参考样例Sample Input112200

3、2010 Sample Output5 21.2.3 各个环节功能要求表1-2.1 环节功能 函数功能注意条件及限制规则CreatBitree()先序建立二叉树字符2字符1字符0三种情况：,2，有左右子树；1，有左子树右空；0，左右子树为空PreOrder()先序遍历二叉树以T是否为空遍历二叉树补充正文：由于只有三种颜色，可以用数字2,1,0分别表示，先序建立二叉树，将二叉树每个结点与其左孩子强行交叉赋值2与1（有右孩子的则赋予与结点和左孩子不同的值），即为按优先顺序2,1,0给节点赋值。并运用递归算法建立子树，最后计算结点数字个数最多的那一项，与最小的那一项，即为这棵子树中最多和最少有多少个

4、点染成绿色。 第二章 概要设计2.1 抽象数据类型ADT BinaryTree 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R：若D=，则R=，称BinaryTree为空二叉树；若D=, 则R=H,H是如下关系： （1）在D中存在唯一的称为根的数据元素root,它在关系H下无前驱； （2）若D-root，则存在D-root=D1，Dr,且D1Dr=； （3）若D1，则D1中存在惟一的元素X1，<root,X1>H,且存在D1上的关系H1H；若Dr,则Dr中存在惟一的元素Xr,<root,X1>H,且存在Dr上的关系HrH;H=<root,X1>,

5、<root,Xr>，H1，Hr; （4）（D1，H1）是一棵符合本定义的二叉树，称为根的左子树，（Dr,Hr）是一棵符合本定义的二叉树，称为根的右子树。基本操作P： IniBiTree(&T)； 操作结果：构造空二叉树T。 DestroyBiTree(&T); 初始条件:二叉树T存在。 操作结果：销毁二叉树。CreateBiTree(&T) 初始条件：二叉树存在。 操作结果：先序建立二叉树PreOrder（&T） 初始条件：二叉树存在。 操作结果：先序遍历T，并计算不同数值的节点个数。 ADT BinaryTree；2.2主要算法描述2.3算法分析T

6、(n)=O(n)因为当输入都为2时，为最坏情况的运行时间，即T(n)=2T(n/2)所以可以通过猜答案的方法计算出T(n)=O(n)。第三章 详细设计3.1 程序代码#include<iostream>using namespace std;static int b=3,c=3;static int a3;/定义为静态变量 typedef int TreeData;typedef struct nodeTreeData data;struct node *lchild,*rchild;BinTreeNode;typedef BinTreeNode *BinTree;void Cre

7、atBitree(BinTree &T)/先序建立二叉树 char a; cin>>a; if(!(T=(BinTreeNode*)malloc(sizeof(node)/建立根结点 return; /用数字2,1,0分别表示三种不同颜色 if(b!=c)/令b,c表示左孩子和根的数值 if(b=0&&c=2)|(c=0&&b=2)/右孩子的赋值取决于左孩子与根的值 T->data=1; else if(b=1&&c=0)|(c=1&&b=0) T->data=2; else T->data=

8、0; else /由于是先序建立强行将2和1交叉赋值给根和左孩子 if(b=2) T->data=1; else T->data=2; b=c=T->data;if(a='2')/当输入值为2时，递归建立两个孩子 CreatBitree(T->lchild);b=T->lchild->data;/b赋值左孩子的值 c=T->data;/c赋值根的值 CreatBitree(T->rchild);else if(a='1')/当输入值为1时，递归建立一个左孩子 CreatBitree(T->lchild); T

9、->rchild=NULL;else/输入为0时无孩子 T->lchild=NULL; T->rchild=NULL; void PreOrder(BinTree T)/先序遍历 if(T!=NULL)aT->data+;/分别计算节点值为0,1,2的个数 PreOrder(T->lchild);PreOrder(T->rchild);int main() BinTree T; CreatBitree(T); PreOrder(T); int min=a0; int max=a0; for(int i=0;i<3;i+)/查找数组中的最大值与最小值 i

10、f(ai<min) min=ai; else max=ai; cout<<max<<" "<<min<<endl;system ("pause");return 0;第四章 调试分析Bug 名称不是具有颜色最多和颜色最少节点个数的二叉树Bug描述数字0,1,2的最多最少个数不符合题目要求的5,2Bug原因用了rand()函数随意给节点赋值，出现最优的二叉树几率小Bug解决方案强制性按2,1,0优先顺序给节点赋值if(b!=c)/令b,c表示左孩子和自己的数值 if(b=0&&c=2)|

11、(c=0&&b=2) T->data=1; else if(b=1&&c=0)|(c=1&&b=0) T->data=2; else T->data=0; else if(b=2) T->data=1; else T->data=2; b=c=T->data;Bug总结要按照题意寻求最优方案第五章 测试分析测试编号1 测试对象CreatBitree()函数（构建染色后的二叉树）测试输入参数1122002010测试步骤1.调用CreatBitree()函数2.调用preorder()函数3.输出先序遍历后的二叉树测试预期结果2121200212测试输出结果测试分析预期结果与实际结果符合第六章 未来展望与思考6.1 思考与展望只有三种颜色给节点染色，可以用从简单的if语句解决，但是大于三种的颜色去染色该用什么样的方法能够让程序按照自己所要求的颜色顺序去给节点染色6.2 感想这道题非常让我有成就感，舍友都觉