檢查兩棵樹是否相同

以下是同一棵樹（系統發育）的三個等價表示。我試圖找出一個算法來檢查兩個樹的表示是否相等。如果節點之間的父子關係相似，則將樹定義爲等價。檢查兩棵樹是否相同

(Whale,(Seal,((Mouse,Rat),((((Carp,Loach),Frog),Chicken),Human))),Cow); 
(Whale,(Seal,((Rat,Mouse),(Human,((Frog,(Loach,Carp)),Chicken)))),Cow); 
((Seal,((Rat,Mouse),(Human,((Frog,(Loach,Carp)),Chicken)))), Cow, Whale);

任何人都可以提出一種方法嗎？

來源

2012-04-21 Sunder

是樹（人類，猿）和（猿，人）equivelent？ – 2012-04-21 11:09:53

是的，他們是... – Sunder 2012-04-21 11:13:02

一種方法是按照詞彙順序（或任何嚴格的弱順序）對孩子進行閱讀和比較。

來源

2012-04-21 11:05:06

其實任何排序都會.. – 2012-04-21 11:05:36

這是一個聰明的方式.. – Sunder 2012-04-21 11:13:21

您可以爲兩棵樹寫兩次 - 一次爲（a，b），一次爲（b，a）。例如爲（鼠標，鼠標）生成兩個字符串：「鼠標：鼠標」和「鼠標：鼠標」，然後編寫所有這些字符串，按字典順序排序並比較兩個列表。如果它們是相同的，那麼樹木是相似的。這與Andrew Tomazos的解決方案不同，因爲它會說一棵樹類似於它本身從底部到頂部穿過，即它支持邊緣反轉。

來源

2012-04-21 11:08:33

只有葉節點被標記。 – 2012-08-20 00:47:04

同時檢查trees.If的序和後序遍歷它們是相同那麼這兩個樹都是相同

來源

2012-04-22 13:49:28 abhi

檢查兩棵樹是否相同

回答

相關問題