二叉树结点染色问题-实验报告

《二叉树结点染色问题-实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、设计题目:学生姓名:专业:班级:学号:指导教师:完成日期:课程设计报告二叉树结点染色问题计算机科学与技术2015-7-7(-)需求和规格说明一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列SS0表示该树没有子节点S彳表示该树有一个子节点，2为其子树的二叉树序列2隔表示该树有两个子节点，S闲］戲分别表示其两个子树的二叉树序列例如，下图所表示的二叉树可以用二叉树序列S=21200110來表示。任务是耍对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节

2、点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树屮最多和最少冇多少个点能够被染成绿色。(二)设计分析过程：这是一道二叉树的染色问题，求染成绿色的最大最小情况，从本质上看，这是一道动态规划问题。为了方便直观起见，代码开始时用先enumColor!nocolor=0,green二1,red二2,blue二3｝；定义了不同的颜色。举个简单的例子，如下图所示:1号点为二叉树根节点2号点为左子树根节点3号点为右子树根节点将整个二叉树划分成三

3、个部分：根节点、左子树、右子树。由于有约朿条件，所以这三个部分存在着互相限制作用如下：1.二叉树的根节点与左子树的根节点颜色不同；2.二叉树的根节点与右了树的根节点颜色不同；3.左子树根节点与右子树根节点颜色不同。显然，上述的三个限制表示的是标号为1、2、3三个点之间的互相关系。除此以外，左子树屮的点与右子树屮的点没有任何直接的限制关系！也就是说，如果我们事先确定了上述二叉树中标号为1、2、3的三个点的颜色，那么接下来，对左了树染色和对右了树染色将变成两个互不干扰的子问题，左子树最值与右子树最值不影响，可以分

4、开求解。【互不干扰，可以分开求解】如此一来，通过将三点染色，我们就可以把二叉树分成左右两个子树,整个问题被分解成两个较小规模的子问题。算法设计:如图二所示，将二叉树划分成三部分，给标号为1、2、3三个点先染色后，将依次处理左子树，右子树。再递归处理：当3号点为蓝色时,右子树如何染色。假设1号点为红色，2号点为绿色，3号点颜色为蓝色。先递归处3里：当2号点为绿色时，左子树如何染色。图二在求解时，冇以下2个问题：(1)染色的任意性标号为1、2、3的三个点的颜色并不一定固定依次是红、绿、蓝。我们需要对所有染色情况进

5、行枚举，并对每个染色情况进行左、右子树的分别处理。同样，当根节点只有一个了节点时，我们也要枚举此时的染色方案。(2)根节点的颜色已确定由于2号点已经染色，所以，在递归处理左子树吋，问题就转化成“根节点颜色已确定，求满足约束条件的最多(最小)染色方案”。这个转化后的了问题与原问题略有差异：原问题中根节点可以任意染色，而转化后的子问题屮根节点的颜色是固定的。为了便于递归调用相同的处理操作，我们必须保证所有问题的条件与求解口标的统一！于是，有必要将原问题稍做修改：事先求出整个二叉树根节点为红色、绿色或蓝色情况下问题

6、的解(这就与子问题是同一类型T),然后取这三个解中的最大(或最小)值，即得到原问题的解。分析至此，我们已经得岀了解决问题的大致方法：将原问题转化成“根节点颜色确定，求染色最值方案”；枚举根节点的左节点与右节点(如果存在)的颜色，同时满足约束条件；对每种染色方案，递归处理求左、右两子树。给二叉树上所有节点标号，从1〜N；用son记录二叉树的构造关系，Son(i,0)和Son(i,1)分别表示编号是i的节点，其左右两个了节点的编号(如果不存在，则用-1表示)。例如在上图中,我们冇Son(1,0)=2,Son(l,

7、l)=3o用F(i,j)表示一个子问题一个子问题可以由两个参数来描述：根节点编号i,根节点颜色j。F(i,j)表示：以编号是i、颜色是j的节点为根节点的子树，在满足约朿条件的情况下染色，绿色节点最多(最少)有多少个。按照先前所设计的算法，可以大致得出如下式：i==-1F(ij)=F(son(i,0),j1)+F(son(i,1),j2)i<>-1jogreenF(son(i,0)j1)+F(son(i,1),j2+1i<>-1j==green根据我们的分析，算法会有重复操作，多次计算F(i,j)的值。那么,我

8、们不妨造一个表将F(i,j)保存起來，这样就能有效避免重复计算了。结构体名成员类别类型成员名描述node屈性intChildNum存储当前结点拥冇的孩子值，Colorcolor存储当前结点的颜色类名成员类别类型成员名描述employee屈性intlengths的长度node的动态数tree存储tree的结点方法TREE()构建treevoidPreorder(inti)以第i结点为根结点进行先序遍历