




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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.没有考虑到当前结点左右染色的两种情况(例如,当前结点为绿色,其左右孩子 的染色情况为 左红右蓝 或 左蓝右红
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- PLC控制系统的自动化送料装车系统设计
- 公共教育餐厅管理办法
- 高速公路行业的经济价值分析
- 团队合作薪酬管理办法
- 数字时代青少年网络素养教育:文明上网提升机制的探索
- 粳稻花期性状的遗传量化与聚合效应分析
- 基于《旅游景区质量等级的划分》的4A景区评审体系优化研究
- 拜占庭艺术的魅力与传承
- 民族成人登记管理办法
- 江苏牛羊屠宰管理办法
- PLC基础知识课件下载
- 2025年中级消防设施操作员(监控类)资格理论必背考试题库(附答案)
- 2023秸秆类生物质能源原料储存规范第1部分:存放
- DB11 T 212-2009 园林绿化工程施工及验收规范
- 感染性腹泻患者护理常规
- 2023年1月国家开放大学汉语言文学本科《古代诗歌散文专题》期末纸质考试试题及答案
- 2025年房东租房合同模板电子版
- 2025年中国智能城市轨道交通行业市场发展监测及投资战略咨询报告
- 车辆检测机构整改报告模板
- DB37-T 2040-2023 金属矿山尾矿干排安全技术规范
- 二零二五年度户外烧烤场地租赁及食品安全保障服务协议3篇
评论
0/150
提交评论