algorithm - 从列表以及isDescendant和isAscendant函数构建树

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

[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.

如前所述，这些函数是总计的，因此对于任何参数都有答案。

最佳答案

可以使用拓扑排序，并以逐层方式进行排序，这意味着：
找到所有没有祖先的节点；
将它们全部添加到下一层；
移除所有这些节点；
重复此操作，直到没有节点剩余。