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

课程设计报告 设计题目： 二叉树结点染色问题 学生姓名： 专 业： 计算机科学与技术 班 级： 学 号： 指导教师： 完成日期： 2015-7-7 （一） 需求和规格说明 一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”： 例如，下图所表示的二叉树可以用二叉树序列S表示。 任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。 设计 分析过程： 这是一道二叉树的染色问题，求染成绿色的最大最小情况，从本质上看，这是一道动态规划问题。为了方便直观起见，代码开始时用先 enum Color{ nocolor = 0, green = 1, red = 2, blue = 3 };定义了不同的颜色。 举个简单的例子，如下图所示： 将整个二叉树划分成三个部分：根节点、左子树、右子树。由于有约束条件，所以这三个部分存在着互相限制作用如下： ? 1. 二叉树的根节点与左子树的根节点颜色不同； ? 2.二叉树的根节点与右子树的根节点颜色不同； ? 3.左子树根节点与右子树根节点颜色不同。 显然，上述的三个限制表示的是标号为1、2、3三个点之间的互相关系。除此以外，左子树中的点与右子树中的点没有任何直接的限制关系！也就是说，如果我们事先确定了上述二叉树中标号为1、2、3的三个点的颜色，那么接下来，对左子树染色和对右子树染色将变成两个互不干扰的子问题，左子树最值与右子树最值不影响，可以分开求解。 【互不干扰，可以分开求解】 如此一来，通过将三点染色，我们就可以把二叉树分成左右两个子树，整个问题被分解成两个较小规模的子问题。 算法设计： 如图二所示，将二叉树划分成三部分，给标号为1、2、3三个点先染色后，将依次处理左子树，右子树。 在求解时，有以下2个问题： 染色的任意性 标号为1、2、3的三个点的颜色并不一定固定依次是红、绿、蓝。我们需要对所有染色情况进行枚举，并对每个染色情况进行左、右子树的分别处理。同样，当根节点只有一个子节点时，我们也要枚举此时的染色方案。 ? 根节点的颜色已确定 由于2号点已经染色，所以，在递归处理左子树时，问题就转化成“根节点颜色已确定，求满足约束条件的最多（最小）染色方案”。 这个转化后的子问题与原问题略有差异：原问题中根节点可以任意染色，而转化后的子问题中根节点的颜色是固定的。 为了便于递归调用相同的处理操作，我们必须保证所有问题的条件与求解目标的统一！于是，有必要将原问题稍做修改：事先求出整个二叉树根节点为红色、绿色或蓝色情况下问题的解（这就与子问题是同一类型了），然后取这三个解中的最大（或最小）值，即得到原问题的解。 分析至此，我们已经得出了解决问题的大致方法： ? 将原问题转化成“根节点颜色确定，求染色最值方案”； ? 枚举根节点的左节点与右节点（如果存在）的颜色，同时满足约束条件； ? 对每种染色方案，递归处理求左、右两子树。 给二叉树上所有节点标号，从1~N； ? 用son记录二叉树的构造关系， Son(i,0)和Son(i,1)分别表示编号是i的节点，其左右两个子节点的编号（如果不存在，则用-1表示）。例如在上图中，我们有Son(1,0)=2，Son(1,1)=3。 ? 用F(i,j)表示一个子问题 一个子问题可以由两个参数来描述：根节点编号i，根节点颜色j。 F(i , j)表示：以编号是i、颜色是j的节点为根节点的子树，在满足约束条件的情况下染色，绿色节点最多（最少）有多少个。 按照先前所设计的算法，可以大致得出如下式： 0 i == -1 F(i,j) = F(son(i,0), j1)+F (son(i,1),j2） i-1 jgreen F(son(i,0),j1)+ F(son(i,1),j2+1 i-1 j == green 根据我们的分析，算法会有重复操作，多次计算F(i,j)的值。那么，我们不妨造一个表将F(i,j)保存起来，这样就能有效避免重复计算了。