亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標(biāo)題: 請(qǐng)教二叉樹(shù)的比較算法 [打印本頁(yè)]

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

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

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

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

作者: Lonki 時(shí)間: 2007-12-26 10:31

考慮到你的數(shù)據(jù)處理, 可以用key為路莖的hash來(lái)保存下面的樹(shù):
A
| |
C | |
B D
A => 'A'
AL => 'C'
ARL => 'B'
ARR => 'D'
或者給你現(xiàn)有的樹(shù)的每個(gè)節(jié)點(diǎn)增加一個(gè)這樣的field, 那么合并就很簡(jiǎn)單了, 格式化輸出也很容易.

復(fù)制代碼

作者: perljoker 時(shí)間: 2007-12-26 10:42

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

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

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

或者給你現(xiàn)有的樹(shù)的每個(gè)節(jié)點(diǎn) ...

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

而且如上，AR是空的，也就是需要其他東西來(lái)識(shí)別，這是個(gè)問(wèn)題

作者: Lonki 時(shí)間: 2007-12-26 11:20
補(bǔ)充下: 所有節(jié)點(diǎn)都要記錄. 假定根節(jié)點(diǎn)以外的非葉子節(jié)點(diǎn)用'#'記:
   A
|    |
C |    |
      B    D

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

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

作者: perljoker 時(shí)間: 2007-12-26 16:32
這樣確實(shí)能處理一者父結(jié)點(diǎn)是另一個(gè)子結(jié)點(diǎn)的問(wèn)題
如果出現(xiàn)不同結(jié)點(diǎn)，我需要根據(jù)一定規(guī)則多開(kāi)一個(gè)叉
用這種方法前，我得去給樹(shù)重新排下序

繼續(xù)……

作者: 放驢娃 時(shí)間: 2007-12-26 16:42
有現(xiàn)成的模塊。

作者: Lonki 時(shí)間: 2007-12-26 18:01

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

繼續(xù)……

舉個(gè)例子呢?

作者: perljoker 時(shí)間: 2007-12-27 16:46

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

舉個(gè)例子呢?

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

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

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

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

作者: Lonki 時(shí)間: 2007-12-27 18:00

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

作者: Lonki 時(shí)間: 2007-12-28 11:54
大概明白了

作者: perljoker 時(shí)間: 2008-01-04 13:17

還是很痛苦，覺(jué)得是個(gè)艱巨的任務(wù)，沒(méi)有發(fā)現(xiàn)可以在哪里參考的例子
我已經(jīng)把需求在一樓更新了，如果哪位高人，同學(xué)能夠幫我解決，那就十分感謝了
閑暇的時(shí)候，幫我想想也成，覺(jué)得挺挑戰(zhàn)的
先謝過(guò)了

歡迎光臨 Chinaunix (http://www.72891.cn/)