《二叉树染色问题》由会员分享，可在线阅读，更多相关《二叉树染色问题（10页珍藏版）》请在金锄头文库上搜索。
1、天洋乂蔘数据结构上机实验报告题目：二叉树染色问题学生姓名 学生学号学院名称计算机学院专 业计算机科学与技术时 间 2014.10.22第一章需求分析11.1原题表述11.2问题解决方案1第二章概要设计22.1抽象数据类型22. 2主要算法分析22. 3主要算法描述2第三章详细设计43. 1程序代码4第四章调试分析74. 1出现的问题及解决方法 7第五章测试分析85. 1测试样例8第一章需求分析1.1原题表述一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为二叉树序列S：0表示该树没有子节点g = *&表示该树有_个子节点,&为其子树的二叉树序列2昭表示该树有两个子节点，
2、山和&分别鬆示其两个子树的二叉树序列例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示现在要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并 且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节 点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有 多少个点能够被染成绿色。12问题解决方案1根据输入的二叉树序列构建二叉树，规定：当一个结点只有一个孩子时，令其为左孩子当n = 0时表示叶结点；当n = 1时表示左孩子当n二2时表示两个孩子2. 为二叉树染色，以subroot为根结点，color表示当前颜色，modl
3、e表示当前结点左 右染色的两种情况（例如，当前结点为绿色，其左右孩子的染色情况为左红右蓝或左蓝 右红两种情况），递归左子树，右子树。3. 中序遍历二叉树，记录绿色节点的数目，保存数据。4. 比较数据，输出最人值，最小值。第二章概要设计2.1抽象数据类型ADT BinaryTreel数据对彖D:D是具有相同特性的数据元素的集合数据关系R：若DH4 则R=H, H是如下二元关系;(1) 在D中存在惟一的称为根的数据元素root,它在关系H下无前驱：(2) 若 DrootH,则存在 D-root二DI, Dr,且 DI ODr 二;(3) 若D1H,则D1中存在惟一的元素xl, eH,且存在D1上的
4、 关系Hl H：若则Dr中存在惟一的元素xr, EH,且存在上 的关系 Hr H： H=, , Hl, Hr；(4) (DI, Hl)是一棵符合本定义的二叉树，称为根的左子树：(Dr, Hr)是一 棵符合本定义的二叉树，称为根的右子树。基本操作：CreatTreeO操作结果：构造二叉树。InorderTraverse(T)初始条件：二叉树T存在。操作结果：中序遍历二叉树Color (struet node *subroot,string color, int modle)初始条件：二叉树已存在操作结果：为二叉树着色；ADT BinaryTree2. 2主要算法分析CreatTree 0的时间复
5、杂度为0 (n)InorderTraverse ()的时间复杂度为0 (n)Color ()的时间复杂度为0 (n)2. 3主要算法描述第三章详细设计3.1程序代码#includeiostream#includeusing namespace std;struct nodestring color;struet node *lchild;struct node *rchild;/二叉树的结点类型int count = 0; /用于记录绿色结点个数static int i = 0; /输入字符的卜标const string nodecolor3二red, blue, green ; /用字符串数
6、组存储节点的三 种颜色/*根据输入的二叉树序列构建二叉树，规定：当一个结点只有一个孩子时，令其为左孩子当n二0时表示叶结点；当n二1时表示左孩子当n二2时表示两个孩子*/struct node *CreatTree(string str)struct node *p;if(i = str. length0) return NULL;int n = int(stri+-48);p二new struet node();pcolor = char(i+48);if(n = 0)p-lchild = NULL;p-rchild = NULL;return p:elseif(n = 1)p-lchild
7、 = CreatTre己(str);p-rchild = NULL;if(n = 2)p-lchild = CreatTre己(str);prchild = CreatTre己(str);return p;/中序遍历二叉树，统计绿色结点的个数void InorderTraverse(struet node* root)if(root)InorderTraverse (rooflchild);if(rootcolor = green)count+;InorderTraverse (roofrchild);/*为二叉树染色，以subroot为根结点，color表示当前颜色，modle表示 当前结点
8、左右染色的两种情况(例如，当前结点为绿色，其左右孩子的 染色情况为左红右蓝或左蓝右红两种情况)，递归左子树，右子树 */void Color (struct node *subroot, string color, int modle)string str2;int temp = 0:if(subroot = NULL)return;subrootcolor = color;for(int i = 0; i lchild, str0, modle);Color(subroot-rchild, str1, modle);elseColor(subroot-rchild, str0, modle)
9、; Color(subroot-lchild, str1, modle);int mainOstring order;cin order;int max = 1, min = 1000000;struct node *p = CreatTree(order);for(int j = 0; j 2; j+) 两种情况for(int i = 0; i 3; i+) /三种颜色 Color(p, nodecolorEi, j);InorderTraver se (p); if(max count) min = count;count = 0;cout max X X min endl; return
10、 0;第四章调试分析4.1出现的问题及解决方法1没有考虑到当前结点左右染色的两种情况（例如，当前结点为绿色，其左右孩子 的 染色情况为左红右蓝 或左蓝右红两种情况）导致结果不正确：图4-1更改后结果正确：图42第五章测试分析5.1测试样例测试样例一: C:UsersZgcDesktop301321611L四艇薛栢祥一第四次实验作业实验一叭-212001103 2Process exited with return value 0 Press any key to continue .图5-1测试样例二:F C:UsersZgcDesktop301321611四艇薛栢祥一第四次实验作业实验一叭-口Process exited with return value 0 ?ress any key to continue .图5-2测试样例三:XY C:UsersZgcDesktop3013216111_四艇薛栢祥一第四次实验作业实验一叭-11220020105 2Process exited with return value 0 Press any key to continue .图5-3
