从列表和 isDescendant 和 isAscendant 函数构建树

Question

给定元素列表，构建树列表的最明智方法是什么：

[a1, a2, a3, ..., an]

和两个总函数：

isAscendant(ai, aj) : boolean
isDescendant(ai, aj) : boolean

请注意，如果 isAscendant(a5, a33) = true，这并不意味着 a33 是 a5 的直系子代，它可能是孙子或曾孙等

例如这个树列表：

       a9               a5
      /  \             / | \
[    a4  a7     ,   a6  a2  a8    ]
    /  \
   a1  a3

应该根据 [a1,...a9] 构建，例如：

isDescendant(a9,a5) = isDescendant(a9,a5) = false = isAscendant(a9,a5) = isAscendant(a9,a5)
isAscendant(a9,a3) = true
isAscendant(a4,a1) = true
isAscendant(a4,a5) = false

... etc.

如前所述，这些函数是完整的，因此对于任何参数总有一个答案 ai, aj。

Answer 1

您可以使用拓扑排序，并以逐层方式进行，这意味着：

查找所有没有祖先的节点；
全部添加到下一层；
删除所有这些节点；
重复直到没有节点离开。

从列表和 isDescendant 和 isAscendant 函数构建树

Building a tree from a list and isDescendant and isAscendant functions

algorithm

tree