随笔-8  评论-5  文章-0  trackbacks-0
哎,郁闷的是自己的方法行不通,现在还不知道为什么。
 
我是根据0,1输入建造两颗树,然后对两个树比较。
  1. 建造过程中,对每个节点拥有的子节点排序,排序的根据是每个子节点的子节点个数。
  2. 在比较两棵树时,我递规地比较他们的子树能否相同,也就是从上到下递规的遍历两颗树。
    1. 对于每个节点,我将他的字节点分组,也是根据该子节点拥有的字节点树,由于先前已经对字节点排序过了,所以分组也很容易。只要两边的组里面出现可以相同的匹配,就算该组是相同的。再接下去比较下一组。
    2. 所谓组之间地相同匹配,我的想法是,对于第一组的任一节点,从第二组中找相同的节点(以及他们的孩子),如果找到了,就做标记,并继续为第一组的下一个节点找,如果找不到,就说明不可能有相同匹配。

后来是看了Lee.Mars的算法,大概思想如下:

  1. 输入序列是对一颗树的遍历生成的,该题目即是树的同构判断。
  2. 因为遍历的规则未确定,所以生成的序列不同。
  3. 制定一种遍历规则,对输入的序列规则化,判断最终的序列是否相同。

规则化的方法如下:

  1. 将序列分解为几个子序列,代表不同的子树。
  2. 对子序列递规地规则化。
  3. 对规则化后地子序列排序,并合成后返回。
posted on 2005-08-03 00:29 pumpkin 阅读(716) 评论(0)  编辑 收藏 引用
只有注册用户登录后才能发表评论。