java - 如何通过仅保留所有树共有的节点来合并多棵树

Question

所以我在执行某些代码期间生成了两到三棵树。这棵树的每个节点都具有此属性，它至少有 0 个子节点，最多有 8 个子节点。所以我猜你能够得到这种完整树的图片，它在第 0 层有一个根节点。在第 1 级有 8 个节点，在第 2 级有 64 个节点，依此类推。父节点的每个子节点都从 0 到 7 编号，我将其作为字节整数类型存储在 java 中，顺便说一句，我是在 java 中制作的。

现在我需要将我生成的这两棵树合并到三棵树，并且我在级别上完全忽略给定节点的子节点。如果在级别 1 的三棵树的级别上，如果树 1 有 4,5,6，树 2 有 5,6,7，树 3 有 2,5,6，我的结果树应该有 5,6对所有三棵树都是通用的。我不关心树 1 的第 5 个节点是否有 4 个子节点，而树 2 中该级别的同一个第 5 个节点是否有 3 个子节点。如果一个节点在一个级别上被标记为 5，则它被认为与不同树中同一级别上标记为 5 的节点相同，而不管它有多少个 child ，或者 child 是否相同。

因此，为了直观地说明我在第二段中提到的内容，以确保没有歧义，我还附上了这三个图表。前两个合并为第三棵树。

拜托，我有足够的时间来做这个，这是出于个人目的，我想在这里学习一些东西，所以请不要推荐任何图书馆。

我正在考虑的解决方案包括为每棵树创建一个队列，并对这三棵树进行级别顺序遍历，并将我遇到的节点添加到队列中。在我开始添加给定节点的子节点之前，我看到了这三个队列的共同点!我在结果树中设置了公共(public)部分节点。但我想知道是否有比这更有效的解决方案。

Answer 1

假设在这两种情况下树和子树的相对顺序相同，您可以使用简单的递归算法将树合并在一起:

• 将一棵空树和任何一棵树合并在一起会产生空树。
• 将具有不同根的树合并在一起产生空树。
• 将具有相同根 r 和子节点 c₁ 的两棵树合并在一起，...，c_n 和 d₁，.. ., d_n 是通过产生一棵新树来完成的>i 和 d_i 具有相同的根值。

希望这对您有所帮助!