资源描述：
《数据结构上机实验报告(二叉树染色问题).docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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组成的字符序列，我们称之为“二叉树序列S”：例如，下图所表
2、示的二叉树可以用二叉树序列S=来表示现在要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。1.2详细问题的解决方案1.2.1解决方案要求输入参数:输入数据由多组数据组成。每组数据仅有一行，不超过10000个字符，表示一个二叉树序列。输出参数：对于每组输入数据，输出仅一行包含两个整数，依次表示最多和最少有多少个点能够被染成绿色。1.2.2
3、参考样例SampleInputSampleOutput521.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抽象数据类型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，∈H,且存在D1
5、上的关系H1⊂H；若Dr,则Dr中存在惟一的元素Xr,∈H,且存在Dr上的关系Hr⊂H;H={,，H1，Hr};（4）（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr,{Hr}）是一棵符合本定义的二叉树，称为根的右子树。基本操作P：IniBiTree(&T)；操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件:二叉树T存在。操作结果：销毁二叉树。CreateBiTree(&T)初始条件：二叉树存在。操作结果：先序建立二叉树PreOrde
6、r（&T）初始条件：二叉树存在。操作结果：先序遍历T，并计算不同数值的节点个数。}ADTBinaryTree；2.2主要算法描述2.3算法分析T(n)=O(n)因为当输入都为’2’时，为最坏情况的运行时间，即T(n)=2T(n/2)所以可以通过猜答案的方法计算出T(n)=O(n)。第三章详细设计3.1程序代码#includeusingnamespacestd;staticintb=3,c=3;staticinta[3];//定义为静态变量typedefintTreeData;typedefstructnod
7、e{TreeDatadata;structnode*lchild,*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=1;elseif((b==1&&c==0)
11、
12、(c==1&&b==0))T->data=2;elseT->data=0;}else{//由于是先序建立强行将2和1交叉赋值给根和左孩子if(b==2)T->data=1;elseT->
