請教二叉樹的比較算法

perljoker

是這樣的，現(xiàn)在我這里有兩棵建立好的二叉樹，同時也能夠解析開（指的是，各結(jié)點間的關(guān)聯(lián)）
兩棵樹有相同的地方，也有差異，簡單的一種情況為：
    A            A
  |    |         |    |
C      D      C   |  |
                  B  D
這是比較簡單的情況了（當然，一切從簡單入手）
我如何才能對其進行比較，最終應(yīng)該是能夠達到合并，而畫樹，有清晰直觀的效果
假設(shè)右邊樹可以標記為A' C' B' D'
到時候合并到左邊，預(yù)期效果如下：
    AA'
  |       |
CC'     |   |
      B'    DD'
也不知道這種思路行不行，感覺上很痛苦
大家有什么其他思路沒
或者實現(xiàn)這種方法，覺得容易的算法

我在找關(guān)系的時候，必須層層向上尋找同樣的父親產(chǎn)生關(guān)聯(lián)，數(shù)據(jù)的結(jié)構(gòu)感覺也很很復雜


更新內(nèi)容：
現(xiàn)在我把實際上，預(yù)期能夠比較的兩棵樣品樹貼上來
如果各位高人，誰在空閑的時候，不妨幫我想想辦法，如何實現(xiàn)合并和比較
十分感謝了



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

Lonki

1. 
   
2. 考慮到你的數(shù)據(jù)處理, 可以用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. 或者給你現(xiàn)有的樹的每個節(jié)點增加一個這樣的field, 那么合并就很簡單了, 格式化輸出也很容易.
    

復制代碼

perljoker

原帖由 Lonki 于 2007-12-26 10:31 發(fā)表

考慮到你的數(shù)據(jù)處理, 可以用key為路莖的hash來保存下面的樹:
       A
   |       |
   C    |     |
        B     D

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

或者給你現(xiàn)有的樹的每個節(jié)點 ...

謝謝Lonki，但是我覺得無法實現(xiàn)合并啊
如我給的例子
左邊 AR=D，右邊 ARR=D
如果要合并，這個需要被認為是同一個東西，就是都是D
（這里還存在一個樹的再排序……原樹BD可能位置還不同……，這個另外說）

而且如上，AR是空的，也就是需要其他東西來識別，這是個問題

Lonki

補充下: 所有節(jié)點都要記錄. 假定根節(jié)點以外的非葉子節(jié)點用'#'記:
       A
   |       |
   C    |     |
        B     D

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

將2個hash的item都添加到新hash, 遇到相同key時:
若任意一方為#, 則為#, 否則字符串合并

perljoker

這樣確實能處理一者父結(jié)點是另一個子結(jié)點的問題
如果出現(xiàn)不同結(jié)點，我需要根據(jù)一定規(guī)則多開一個叉
用這種方法前，我得去給樹重新排下序

繼續(xù)……

放驢娃

有現(xiàn)成的模塊。

Lonki

原帖由 perljoker 于 2007-12-26 16:32 發(fā)表
這樣確實能處理一者父結(jié)點是另一個子結(jié)點的問題
如果出現(xiàn)不同結(jié)點，我需要根據(jù)一定規(guī)則多開一個叉
用這種方法前，我得去給樹重新排下序

繼續(xù)……

舉個例子呢?

perljoker

原帖由 Lonki 于 2007-12-26 18:01 發(fā)表


舉個例子呢?

發(fā)現(xiàn)排序更恐怖，我這樹太不規(guī)矩了

是這樣的，假如通過#覆蓋下面葉結(jié)點，是該用在該葉結(jié)點可能出現(xiàn)在另一棵樹的子結(jié)點里面才可以
否則就會丟失信息，是這樣理解的吧
假如C是tree_one的LL特有，D是tree_two的LL特有，這時候需要一定規(guī)則提高深度的吧

實際上的樹則是，亂序（就我們看來亂序，建樹的時候方法比較復雜），而且?guī)缀鯚o法對應(yīng)
比如這邊LL是C，那邊LL可能是D，或者父結(jié)點，左右次序無法對應(yīng)，結(jié)點差異很大

現(xiàn)在的想法是評分制度，首先將所有葉子全部存貯一次，并且相同的名字（如左樹的D和右樹的D）劃分小組
兩棵樹的某一個結(jié)點如果相對應(yīng)，再次劃分小組存儲（方法是，查看子結(jié)點是否對應(yīng)，比如這邊AB，那邊是否A'B'，假如是根結(jié)點，那就好多層比較了……）
如此層層向上，直到最后只剩下一個小組（過程感覺就很恐怖，存儲提取方式，讓我也覺得難下手）

Lonki

# 迷惑, 之前的理解是僅僅按照層次合并. # # 對于如下左右2樹: #          A                     A' #      |       |             |       | #    |       |             |   |   |   | #    C       B             D'  E'  B'  F' # # 我之前的理解是合并為下面的樹: #          AA' #     |          | #  |     |    |     | # CD'    E'  BB'    F' # # 你的合并結(jié)果應(yīng)該是什么?

perljoker

只有相同的才可以合并，比如BB'，合并以后看作一個B也一樣
C的位置在這里就很難說了
相當于要從一個表里面去查他的優(yōu)先度（這里就是指分叉的優(yōu)先度）
然后，決定在哪里，比如在B'F'上面分叉，或者和B分叉，或者在D'E'上分叉，或者與D'或者E'分叉
根據(jù)表里面先后順序決定