检查两棵树是否等价

Question

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

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

有人可以推荐一种方法吗？

- Sunder

---

树（人类，猿）和（猿，人类）是否等价？ - Ivaylo Strandjev

Answer 1

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

- Andrew Tomazos

Answer 2

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

- Ivaylo Strandjev

---

仅叶子节点被标记。 - Andrew Tomazos

Answer 3

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

- abhi