请教二叉树的比较算法

perljoker

是这样的，现在我这里有两棵建立好的二叉树，同时也能够解析开（指的是，各结点间的关联）
两棵树有相同的地方，也有差异，简单的一种情况为：
    A            A
  |    |         |    |
C      D      C   |  |
                  B  D
这是比较简单的情况了（当然，一切从简单入手）
我如何才能对其进行比较，最终应该是能够达到合并，而画树，有清晰直观的效果
假设右边树可以标记为A' C' B' D'
到时候合并到左边，预期效果如下：
    AA'
  |       |
CC'     |   |
      B'    DD'
也不知道这种思路行不行，感觉上很痛苦
大家有什么其他思路没
或者实现这种方法，觉得容易的算法

我在找关系的时候，必须层层向上寻找同样的父亲产生关联，数据的结构感觉也很很复杂


更新内容：
现在我把实际上，预期能够比较的两棵样品树贴上来
如果各位高人，谁在空闲的时候，不妨帮我想想办法，如何实现合并和比较
十分感谢了



[ 本帖最后由 perljoker 于 2008-1-4 13:14 编辑 ]

Lonki

1. 
   
2. 考虑到你的数据处理, 可以用key为路茎的hash来保存下面的树:
   
3.        A
   
4.    |       |
   
5.    C    |     |
   
6.         B     D
   
7. 
   
8. A   => 'A'
   
9. AL  => 'C'
   
10. ARL => 'B'
    
11. ARR => 'D'
    
12. 
    
13. 或者给你现有的树的每个节点增加一个这样的field, 那么合并就很简单了, 格式化输出也很容易.
    

复制代码

perljoker

原帖由 Lonki 于 2007-12-26 10:31 发表

考虑到你的数据处理, 可以用key为路茎的hash来保存下面的树:
       A
   |       |
   C    |     |
        B     D

A   => 'A'
AL  => 'C'
ARL => 'B'
ARR => 'D'

或者给你现有的树的每个节点 ...

谢谢Lonki，但是我觉得无法实现合并啊
如我给的例子
左边 AR=D，右边 ARR=D
如果要合并，这个需要被认为是同一个东西，就是都是D
（这里还存在一个树的再排序……原树BD可能位置还不同……，这个另外说）

而且如上，AR是空的，也就是需要其他东西来识别，这是个问题

Lonki

补充下: 所有节点都要记录. 假定根节点以外的非叶子节点用'#'记:
       A
   |       |
   C    |     |
        B     D

A   => 'A'
AL  => 'C'
AR  => '#'
ARL => 'B'
ARR => 'D'

将2个hash的item都添加到新hash, 遇到相同key时:
若任意一方为#, 则为#, 否则字符串合并

perljoker

这样确实能处理一者父结点是另一个子结点的问题
如果出现不同结点，我需要根据一定规则多开一个叉
用这种方法前，我得去给树重新排下序

继续……

放驴娃

有现成的模块。

Lonki

原帖由 perljoker 于 2007-12-26 16:32 发表
这样确实能处理一者父结点是另一个子结点的问题
如果出现不同结点，我需要根据一定规则多开一个叉
用这种方法前，我得去给树重新排下序

继续……

举个例子呢?

perljoker

原帖由 Lonki 于 2007-12-26 18:01 发表


举个例子呢?

发现排序更恐怖，我这树太不规矩了

是这样的，假如通过#覆盖下面叶结点，是该用在该叶结点可能出现在另一棵树的子结点里面才可以
否则就会丢失信息，是这样理解的吧
假如C是tree_one的LL特有，D是tree_two的LL特有，这时候需要一定规则提高深度的吧

实际上的树则是，乱序（就我们看来乱序，建树的时候方法比较复杂），而且几乎无法对应
比如这边LL是C，那边LL可能是D，或者父结点，左右次序无法对应，结点差异很大

现在的想法是评分制度，首先将所有叶子全部存贮一次，并且相同的名字（如左树的D和右树的D）划分小组
两棵树的某一个结点如果相对应，再次划分小组存储（方法是，查看子结点是否对应，比如这边AB，那边是否A'B'，假如是根结点，那就好多层比较了……）
如此层层向上，直到最后只剩下一个小组（过程感觉就很恐怖，存储提取方式，让我也觉得难下手）

Lonki

# 迷惑, 之前的理解是仅仅按照层次合并. # # 对于如下左右2树: #          A                     A' #      |       |             |       | #    |       |             |   |   |   | #    C       B             D'  E'  B'  F' # # 我之前的理解是合并为下面的树: #          AA' #     |          | #  |     |    |     | # CD'    E'  BB'    F' # # 你的合并结果应该是什么?

perljoker

只有相同的才可以合并，比如BB'，合并以后看作一个B也一样
C的位置在这里就很难说了
相当于要从一个表里面去查他的优先度（这里就是指分叉的优先度）
然后，决定在哪里，比如在B'F'上面分叉，或者和B分叉，或者在D'E'上分叉，或者与D'或者E'分叉
根据表里面先后顺序决定