javascript - 如何从叶节点的一组路径片段构建树

Question

当唯一的输入数据是叶节点的路径决策(随机顺序)时，我正在寻找一种算法来构建可能的自上而下的树结构。

如果叶节点已经通过该节点，则路径决策用 [nodeID]+ 标记，如果叶节点没有通过该节点，则路径决策用 [nodeID]- 标记。输入示例:

上面示例输入的一个可能的树结构是:

输出应该是节点列表和节点各自的父节点，如下所示:

如您所见，每个叶节点的可能位置并不限于一个，因为输入数据不是完整路径。示例中的 Leaf1 可以是节点 D 或节点 I 的子节点。

您可以从任意数量的叶节点获取路径数据，但每个叶节点只有一行路径数据。可能有些叶子你根本得不到任何数据，你也不知道树中总共有多少叶子。路径数据中提到的所有节点都应该出现在输出表中，只有计算出的根节点不应该分配任何父节点。

我想必须以某种方式结合每个叶子路径的事实，比如从 Leaf1 中你知道:A 和 E 不能平行，从 Leaf2 中你知道 A 和 I 不能平行，等等在...

首选javascript，但也欢迎其他语言或伪代码!

Answer 1

既然没有人回答，我会给出一些部分的想法。

你开始于:

1: [A+, E+, H-]
2: [B-, A+, I+, D-]
3: [K+, G+, E+, C-]
4: [H+, A-, G-]

首先，搜索仅以 + 出现的节点。 Root 。扫描这个，我们可以为节点 E、I 和 K 做那个。所以我们的答案开始于:

E
E I
I K

我们的路径数据被简化为:

1: [A+, H-]
2: [B-, A+, D-]
3: [G+, C-]
4: [H+, A-, G-]

现在我们有一个分区操作。为此，我们制作了一个图表，其中 2 个节点连接在一起，前提是它们与 + 一起出现。然后我们通过连接的组件分离节点，并将叶子分成分区，其中有一个 + (任何没有分区的叶子都可以在树中的那里成为叶子然后删除)。删除任何 - 由这种分离处理。在我们的例子中，这是一个完全断开连接的图，它将每个节点放入自己的分区并将路径数据分为 3 组(注意，我们丢失了所有 - 由分区解释的规则):

1: [A+]
2: [A+]

3: [G+]

4: [H+]

现在我们解决每个问题，得出最终解决方案:

E
E I
I K
K A
K B
K C
K D
K G
K H

我相信这种方法只会在没有树的情况下无法取得进展。如果要找到一棵树，它会找到一棵。