4

以下是同一棵树（系统发育）的三个等效表示。我试图找出一种算法来检查两个树表示是否等效。如果节点之间的父子关系相似，则树被定义为等效的。

(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);

任何人都可以提出一种方法吗？

4

3 回答 3

8

一种方法是按字典顺序（或任何严格的弱排序）让孩子们走路并进行比较。

于 2012-04-21T11:05:06.593 回答
0

您可以将每条边写两次 - 一次作为 (a,b) 和一次作为 (b,a) 用于两棵树。例如，为 (Mouse, Rat) 生成两个字符串：“Mouse : Rat”和“Rat : Mouse”，然后编写所有这些字符串，按字典顺序对它们进行排序并比较两个列表。如果它们相同，则树是相似的。这与 Andrew Tomazos 的解决方案不同，因为它会说一棵树类似于自下而上遍历的树，即它支持边缘反转。

于 2012-04-21T11:08:33.030 回答
0

检查两棵树的中序和后序遍历。如果它们相同，则这两棵树相同

于 2012-04-22T13:49:28.753 回答