二叉树染色问题(共11页)

1、数据结构(sh j ji u)上机实验报告 题目(tm)：二叉树染色问题 学生(xu sheng)姓名 学生学号 学院名称 计算机学院 专 业 计算机科学与技术 时 间 2014.10.22 I目 录 TOC o 1-2 h u HYPERLINK l _Toc28542 第一章 需求(xqi)分析 PAGEREF _Toc28542 1 HYPERLINK l _Toc31063 1.1 原题表述(bio sh) PAGEREF _Toc31063 1 HYPERLINK l _Toc25723 1.2 问题(wnt)解决方案 PAGEREF _Toc25723 1 HYPERLINK l

2、_Toc3957 第二章 概要设计 PAGEREF _Toc3957 2 HYPERLINK l _Toc30220 2.1 抽象数据类型 PAGEREF _Toc30220 2 HYPERLINK l _Toc17830 2.2 主要算法分析 PAGEREF _Toc17830 2 HYPERLINK l _Toc24299 2.3 主要算法描述 PAGEREF _Toc24299 3 HYPERLINK l _Toc1106 第三章 详细设计 PAGEREF _Toc1106 4 HYPERLINK l _Toc25644 3.1 程序代码 PAGEREF _Toc25644 4 HYPE

3、RLINK l _Toc10588 第四章 调试分析 PAGEREF _Toc10588 7 HYPERLINK l _Toc27840 4.1 出现的问题及解决方法 PAGEREF _Toc27840 7 HYPERLINK l _Toc26151 第五章 测试分析 PAGEREF _Toc26151 8 HYPERLINK l _Toc31210 5.1 测试样例 PAGEREF _Toc31210 8 计算机学院2013级数据结构上机实验报告PAGE 12需求(xqi)分析1.1 原题表述(bio sh)一棵二叉树可以按照如下规则表示成一个(y )由0、1、2组成的字符序列，我们称之为“

4、二叉树序列S”：例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示现在要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。1.2 问题解决方案1.根据输入的二叉树序列构建二叉树，规定：当一个结点只有一个孩子时，令其为左孩子当n = 0时表示叶结点；当n = 1时表示左孩子当n = 2时表示两个孩子2.为二叉树染色，以subroot为根结点，color表示当前颜色，modle表示当前结点左右

5、染色的两种情况（例如，当前结点为绿色，其左右孩子的染色情况为 左红右蓝 或 左蓝右红 两种情况），递归左子树，右子树。3.中序遍历二叉树，记录绿色节点的数目，保存数据。4.比较数据，输出最大值，最小值。第二章 概要设计2.1 抽象数据类型ADT BinaryTree数据对象D:D是具有(jyu)相同特性的数据元素的集合数据(shj)关系R: 若D，则R=H，H是如下(rxi)二元关系； （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； （2）若D-root，则存在D-root=D1,Dr，且D1Dr =； （3）若D1，则D1中存在惟一的元素x1，H，且存在D1上的关系H1

6、 H；若Dr，则Dr中存在惟一的元素xr，H，且存在上的关系Hr H；H=,H1,Hr； （4）(D1,H1)是一棵符合本定义的二叉树，称为根的左子树；(Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。基本操作：CreatTree()操作结果：构造二叉树。InorderTraverse(T)初始条件：二叉树T存在。操作结果：中序遍历二叉树Color(struct node *subroot,string color,int modle)初始条件：二叉树已存在操作结果：为二叉树着色ADT BinaryTree2.2 主要算法分析CreatTree(）的时间复杂度为O（n)InorderTr

7、averse()的时间复杂度为O（n)Color()的时间复杂度为O（n)2.3 主要算法(sun f)描述 第三章 详细(xingx)设计3.1 程序代码#include#includeusing namespace std; struct node string color;struct node *lchild; struct node *rchild;/二叉树的结点(ji din)类型 int count = 0; /用于记录绿色(l s)结点个数 static int i = 0; /输入(shr)字符的下标 const string nodecolor3=red,blue,gree

8、n; /用字符串数组存储节点的三种颜色 /*根据输入的二叉树序列构建二叉树，规定：当一个结点只有一个孩子时，令其为左孩子当n = 0时表示叶结点；当n = 1时表示左孩子当n = 2时表示两个孩子 */ struct node *CreatTree(string str) struct node *p; if(i = str.length() return NULL; int n = int(stri+-48); p=new struct node(); p-color = char(i+48); if(n = 0) p-lchild = NULL; p-rchild = NULL; retu

9、rn p; else if(n = 1) p-lchild = CreatTree(str); p-rchild = NULL; if(n = 2) p-lchild = CreatTree(str); p-rchild = CreatTree(str); return p;/中序遍历二叉树，统计绿色(l s)结点的个数 void InorderTraverse(struct node* root) if(root) InorderTraverse(root-lchild); if(root-color = green) count+; InorderTraverse(root-rchild)

10、; /*为二叉树染色(rns)，以subroot为根结点，color表示当前颜色，modle表示当前(dngqin)结点左右染色的两种情况（例如，当前结点为绿色，其左右孩子的染色情况为 左红右蓝 或 左蓝右红 两种情况），递归左子树，右子树 */void Color(struct node *subroot, string color, int modle) string str2; int temp = 0; if(subroot = NULL)return; subroot-color = color; for(int i = 0; i lchild, str0, modle); Colo

11、r(subroot-rchild, str1, modle); else Color(subroot-rchild, str0, modle); Color(subroot-lchild, str1, modle); int main()string order; cin order; int max = -1, min = 1000000; struct node *p = CreatTree(order); for(int j = 0; j 2; j+) /两种情况(qngkung) for(int i = 0; i 3; i+) /三种(sn zhn)颜色 Color(p, nodecolori, j); InorderTraverse(p); if(max count) min = count; count = 0; cout max min endl; return 0; 第四章 调试(dio sh)分析4.1 出现(chxin)的问题及解决方法1.没有考虑到当前结点左右染色的两种情况（例如，当前结点为绿色，其左右孩子 的染色情况为 左红右蓝 或 左蓝右红