资源描述：
《数据结构上机实验报告(二叉树染色问题)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构上机实验报告题目：二叉树染色问题学生姓名：学生学号：学院名称：计算机学院专业：计算机科学与技术时间：目录第一章，需求分析31.1原题描述31.2详细问题的解决方案31.2.1解决方案要求31.2.2各个环节功能要求3第二章，概要设计52.1抽象数据类型52.2主要算法描述52.3算法分析7第三章，详细设计83.1程序代码8第四章，调试分析10第五章，测试分析11第六章，未来展望与思考12第一章需求分析1.1原题描述一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称Z为“二叉树序列S”:[0表示该树没有子节点S表示该树有一个子节点
2、，S】为其子树的二叉树序列匕乩圣表示该树有两个子节点，S闲分别表示其两个子树的二叉树序列例如，下图所表示的二叉树町以用二叉树序列S=21200110來表示现在要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并冃,一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一•棵二义树的二义树序列，请求出这棵树屮最多和最少有多少个点能够被染成绿色。1.2详细问题的解决方案1.2.1解决方案要求输入参数：输入数据由多组数据组成。每组数据仅有一行，不超过10000个字符，表示一•个二叉树序列。输出参数：对于
3、每组输入数据，输出仅一行包含两个整数，依次表示最多和最少有多少个点能够被染成绿色。1.2.2参考样例SampleInput1122002010SampleOutput521.2.3各个环节功能要求表1-2.1环节功能函数功能注意条件及限制规则CreatBitreeO先序建立一叉树字符2字符T字符©三种情况：，2,有左右了树；1，有左子树右空；0,左右子树为空PreOrder()先序遍历二叉树以T是否为空遍历二义树补充」［汶：由于只有三种颜色，可以用数字2,1,0分别表示，先序建立二叉树，将二叉树每个结点与其左孩子强行交义赋值2与1（有右孩子的则赋予与结点和
4、左孩子不同的值），即为按优先顺序2,1,0给节点赋值。并运用递归算法建立子树，最后计算结点数字个数最多的那一项，与最小的那一项，即为这棵子树中最多和最少有多少个点染成绿色。第二章概要设计2.1抽象数据类型ADTBinaryTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R：若D=,则R二，称BinaryTree为空二叉树；若D二，则R={H},H是如下关系：(1)在D中存在唯一•的称为根的数据元素root,它在关系H下无前驱；(2)若D-{root},则存在D-{root}={Dl,Dr},且DinDr=；(3)若D1,则D1中存在惟一的元
5、素XI,eH,且存在D1上的关系HlcH；若Dr,则Dr中存在惟一的元素Xr,eH,且存在Dr上的关系HrcH;H={,,Hl,Hr};(4)(DI,{Hl})是一棵符合木定义的二叉树，称为根的左了树，(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。基木操作P：TniBiTree(&T)；操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件:二叉树T存在。操作结果：销毁二叉树。CreateBiTree(&T)初始条件：二义树存在。操作结果：先序建立二叉树P
6、reOrder(&T)初始条件：二叉树存在。操作结果：先序遍历T,并计算不同数值的节点个数。}ADTBinaryTree；2.2主要算法描述结束开始给二叉树节点染色2.3算法分析T(n)=O(n)因为当输入都为'2,时,为最坏情况的运行时间,即T(n)=2T(n/2)所以町以通过猜答案的方法计算出T(n)=O(n)o第三章详细设计3.1程序代码#include〈iostream>usingnamespacestd;staticintb二3，c二3;staticinta[3];//定义为静态变量typedefintTreeData;typedefstruct
7、node{TreeDatadata;structnode*1child,*rchild;}BinTreeNode;typedefBinTreeNode*BinTree;voidCreatBitree(BinTree&T){//先序建立二叉树chara;cin>>a;if(!(T=(BinTreeNode*)malloc(sizeof(node))))//建立根结点return;//用数字2,1,0分别表示三种不同颜色if(b!=c){//令b,c表示左孩子和根的数值if((b==0&&c==2)
8、
9、(c==0&&b==2))//右孩子的赋值取决于左孩子与根
10、的值T>data=l;elseif((b==l&&c==0)
11、
12、(
