合并多棵深度为一的树

Question

我有多个子树，由一个根元素和多个 children 组成。子树的根可以是另一个 children，子树的 children 可以是另一个根。

最终可能会有多个完全分离的树。

示例：

root1
  |-child11
  |-root3

root2
  |-child21
  |-root1
  |-child23

root3
  |-child31

结果应为：

root2
  |-child21
  |
  |-root1
  |   |-child11
  |   |-root3
  |       |-child31
  |
  |-child23

有什么好的算法可以解决吗？我只找到了二叉树的解决方案。

Answer 1

你可以在每个节点中保留一个：

• 散列table（或链表+散列table，如果顺序很重要）对于children

• 指向parent（或None）的指针

此外，保留一个散列 table 将节点 ID 映射到节点列表。

---

虽然后面的hashtable中有一个长度大于1的列表，求哪棵树应该合并到哪棵树中。

Answer 2

将节点结构定义为具有一个父节点和一组子节点。

保留所有唯一节点的集合。

当您处理所有小树时，填充为每个父节点设置的子节点，并将每个子节点指向其父节点。 （一路上将每个新的看不见的节点添加到您的唯一集合中。）

最后遍历 if uniques 集合。任何没有父节点的节点都是重建树的根。