-1

我必须algorithm为我的项目写一个。以下是问题

一种树状结构，仅公开一个功能，即**getAllChildNodes**返回特定节点的所有子节点。现在我得到了一个 Nodes 数组，我只需要保留其中最顶层的父节点。

示例：假设有 3 棵树

Tree 1 : P1 has two children C11 & C12

Tree 2 : P2 has 1 children C21, and C21 has 2 child C22, C23

Tree 3 : P3 has 2 Children C31 and C32

Now if given an array say { C11, C21, C22 , P1, P3, C32}
 The expected result is { C21, P1 , P3 }

如果我需要更多信息，请告诉我。

更多信息：我首先获取数组第一个元素的所有子元素，然后与数组的其余元素进行比较，并且与每个元素类似。但这有更多的复杂性.. 即 n*n*getAllChildNodes。我在这里寻求更好的建议

4

3 回答 3

0

你可以很容易地做到这一点。首先创建一个方法isPresent(node)来检查您输入的节点是否存在于数组中。然后输入给定的每个节点以查找其父节点。

if(isPresent(x->parent)) push(x->parent);

对整个列表继续此操作。现在recursively检查是否current list有任何parents present. 一旦你开始做，你就会得到它。如果有任何父母只是pop()那些元素。希望这可以帮助 ：）

于 2013-06-26T05:22:22.367 回答
0

选择数组的第 i 个元素并将其所有子元素添加到 hashmap（使用给定函数）。对 i 1 到 n 执行此操作（完全通过）

从 1 到 n 循环 i 并且对于每次迭代，检查元素是否存在于 hashmap 中。

如果存在，将其从数组中删除，

否则继续

注意检查元素是否属于hashmap的顺序是O(1)，加法的顺序是O(1)，平均。所以算法是 O(n*getAllChlidNodes) 平均

于 2013-06-26T05:16:37.170 回答
0

如果您可以首先获得像 getParentNode(childNode) 这样的函数，或者创建子映射/多重映射作为键，父作为值作为预处理步骤，那么问题将变得非常容易。

如果你有 getParentNode(childNode) 那么只需遍历数组并将父母推入集合。

如果您将子图/多图作为键，将父图作为值作为预处理步骤，则应用adi提到的算法

于 2013-06-26T05:38:47.977 回答