创建家族树的树

Question

我正在寻找一个很好的算法来计算两个人的最低共同祖先，而不是最初的整体树。

如果我有孩子，我可以拨打电话获取父。所以如果我有两个孩子，我需要每个人都打电话，直到他们有一个共同的祖先。在这一点上，我应该有两个列表，我可以将它们构建成一棵树。

什么样的算法，将有利于本？

Answer 1

如果有确定是否一个特定的节点可以“原则上”是另一个特定节点的父亲的一些基本信息，它会允许你确定共同祖先（如果有的话）快速/有效。这就是我关于“年龄”的问题 - 请参阅评论 - 是关于。 年龄属性显然会给你这种类型的信息。

假设，从你的答案，那有没有可用的这样的信息，有两个明显的方法：

A.同时扫描树向上（的getParent，等等），构造每个初始孩子的祖先列表，同时检查与每一个新的祖先是否发生在另一个孩子的祖先列表中。一般来说，没有理由认为共同的祖先与两个孩子距离（“几乎”）相等，所以你建立相应祖先列表的任何顺序都等于给你共同的祖先在尽可能少的步骤。

这种方法的缺点是，你有运行在相互列举了大量的时间来寻找新的候选人发生的风险。这可能很慢。

B.一种替代方法是简单地建立所述两个ancestorlists独立直至力竭。这可能是相对较快的，因为在每一步都不会因为检查“其他”列表的内容而中断。

然后，当你已经完成了两个列表，你要么有一个共同的祖先与否，只要通过验证彼此的顶级项目。 如果否，您就完成了（没有结果）。如果是的话，你可以同步回到列表中，并检查他们分开的位置，再次避免列表搜索。从一般的观点来看，我更喜欢方法B.有时方法A会产生更快的结果，但是在不好的情况下，它可能会变得单调乏味，这对方法B来说不会发生。我假设，当然，任何祖先列表都不能是循环的，即一个节点不能成为它自己的祖先。作为一个最后的注意事项：毕竟，如果你确实有一个“命令”节点的属性，那么你应该同时构建这两个列表，因为你总是处理这个列表目前有一个顶层节点，它不可能是其他列表的顶级节点的父节点。这允许您仅检查当前的顶级节点（而不是列表中的任何其他成员）。