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

计算机学院2013级数据结构实验1数据结构上机实验报告题目：二叉树染色问题学生姓名：学生学号：学院名称：计算机学院专业：计算机科学与技术时间：计算机学院2013级数据结构实验2目录第一章，需求分析31.1原题描述31.2详细问题的解决方案31.2.1解决方案要求31.2.2各个环节功能要求3第二章，概要设计52.1抽象数据类型52.2主要算法描述52.3算法分析7第三章，详细设计83.1程序代码8第四章，调试分析10第五章，测试分析11第六章，未来展望与思考12计算机学院2013级数据结构实验3第一章需求分析1.1原题描述一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”：例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示现在要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。1.2详细问题的解决方案1.2.1解决方案要求输入参数:输入数据由多组数据组成。每组数据仅有一行，不超过10000个字符，表示一个二叉树序列。输出参数：对于每组输入数据，输出仅一行包含两个整数，依次表示最多和最少有多少个点能够被染成绿色。1.2.2参考样例SampleInput1122002010SampleOutput521.2.3各个环节功能要求计算机学院2013级数据结构实验4表1-2.1环节功能函数功能注意条件及限制规则CreatBitree()先序建立二叉树字符’2’字符’1’字符’0’三种情况：,2，有左右子树；1，有左子树右空；0，左右子树为空PreOrder()先序遍历二叉树以T是否为空遍历二叉树补充正文：由于只有三种颜色，可以用数字2,1,0分别表示，先序建立二叉树，将二叉树每个结点与其左孩子强行交叉赋值2与1（有右孩子的则赋予与结点和左孩子不同的值），即为按优先顺序2,1,0给节点赋值。并运用递归算法建立子树，最后计算结点数字个数最多的那一项，与最小的那一项，即为这棵子树中最多和最少有多少个点染成绿色。计算机学院2013级数据结构实验5第二章概要设计2.1抽象数据类型ADTBinaryTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R：若D=，则R=，称BinaryTree为空二叉树；若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,X1∈H,且存在Dr上的关系Hr⊂H;H={root,X1,root,Xr，H1，Hr};（4）（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr,{Hr}）是一棵符合本定义的二叉树，称为根的右子树。基本操作P：IniBiTree(&T)；操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件:二叉树T存在。操作结果：销毁二叉树。CreateBiTree(&T)初始条件：二叉树存在。操作结果：先序建立二叉树PreOrder（&T）初始条件：二叉树存在。操作结果：先序遍历T，并计算不同数值的节点个数。}ADTBinaryTree；2.2主要算法描述计算机学院2013级数据结构实验6计算机学院2013级数据结构实验72.3算法分析T(n)=O(n)因为当输入都为’2’时，为最坏情况的运行时间，即T(n)=2T(n/2)所以可以通过猜答案的方法计算出T(n)=O(n)。计算机学院2013级数据结构实验8第三章详细设计3.1程序代码#includeiostreamusingnamespacestd;staticintb=3,c=3;staticinta[3];//定义为静态变量typedefintTreeData;typedefstructnode{TreeDatadata;structnode*lchild,*rchild;}BinTreeNode;typedefBinTreeNode*BinTree;voidCreatBitree(BinTree&T){//先序建立二叉树chara;cina;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;elseif((b==1&&c==0)||(c==1&&b==0))T-data=2;elseT-data=0;}else{//由于是先序建立强行将2和1交叉赋值给根和左孩子if(b==2)T-data=1;elseT-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);}elseif(a=='1'){//当输入值为1时，递归建立一个左孩子CreatBitree(T-lchild);T-rchild=NULL;计算机学院2013级数据结构实验9}else{//输入为0时无孩子T-lchild=NULL;T-rchild=NULL;}}voidPreOrder(BinTreeT){//先序遍历if(T!=NULL){a[T-data]++;//分别计算节点值为0,1,2的个数PreOrder(T-lchild);PreOrder(T-rchild);}}intmain(){BinTreeT;CreatBitree(T);PreOrder(T);intmin=a[0];intmax=a[0];for(inti=0;i3;i++){//查找数组中的最大值与最小值if(a[i]min)min=a[i];elsemax=a[i];}coutmaxminendl;system(pause);return0;}计算机学院2013级数据结构实验10第四章调试分析Bug名称不是具有颜色最多和颜色最少节点个数的二叉树Bug描述数字0,1,2的最多最少个数不符合题目要求的5,2Bug原因用了rand()函数随意给节点赋值，出现最优的二叉树几率小Bug解决方案强制性按2,1,0优先顺序给节点赋值if(b!=c){//令b,c表示左孩子和自己的数值if((b==0&&c==2)||(c==0&&b==2))T-data=1;elseif((b==1&&c==0)||(c==1&&b==0))T-data=2;elseT-data=0;}else{if(b==2)T-data=1;elseT-data=2;}b=c=T-data;Bug总结要按照题意寻求最优方案计算机学院2013级数据结构实验11第五章测试分析测试编号1测试对象CreatBitree()函数（构建染色后的二叉树）测试输入参数1122002010测试步骤1.调用CreatBitree()函数2.调用preorder()函数3.输出先序遍历后的二叉树测试预期结果2121200212测试输出结果测试分析预期结果与实际结果符合计算机学院2013级数据结构实验12第六章未来展望与思考6.1思考与展望只有三种颜色给节点染色，可以用从简单的if语句解决，但是大于三种的颜色去染色该用什么样的方法能够让程序按照自己所要求的颜色顺序去给节点染色6.2感想这道题非常让我有成就感，舍友都觉得很难的题让我想出来了，也让我收获很多。有时可以将问题中的物体等价成数字或者字符，用数字和字符去表示物体，更加有利于我们去解决问题。此题中，我把颜色用数字表示并且作为data赋值给节点。这样做我就可以把计算颜色最多最少的个数转化成计算数字最多最少的个数。还有在不停递归调用时对于静态变量的使用，才能比较节点值给左孩子赋值，比较节点与左孩子的值再给右孩子赋值。