3

在下图中，递归遍历子部件。每个孩子都必须报告其直系父母。问题是 child[3] 必须在同一行中同时报告其直接父级（即 child[2] 和 child[4]）。

traverse(Node node)
{
    if(node == null)
        return;

    for(Node child : node.getChilds()) {
        traverse(child);
    }
}

Parent 
|---child[1]
|       child[2]
|           child[3]
|---child[4]
        child[3]

现在我一次遍历一个节点，产生的输出是 -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2]
child[3]  child[4]

预期的输出是 -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2], child[4]

搜索节点并为图形生成预期输出的最佳方法是什么？任何帮助，将不胜感激。

4

1 回答 1

8

如果您有（或可以添加）返回到 parents 的链接，您可以在第一次遇到节点时列出所有 parent，然后在重复访问时跳过它。您有多个选项来跟踪节点是否已被访问：

  1. 维护一组访问节点并检查当前节点是否在集合中。如果不是，则对其进行处理并将其添加到集合中；否则跳过。

    优点：通用方法

    缺点：如果图表很大，可能需要大量内存来维护集合

  2. 给节点添加isVisited成员值（false默认设置为），遇到节点时检查：如果值为false，则处理节点并设置isVisited为true；否则跳过。

    优点：更少的额外内存

    缺点：侵入性，特定于任务，即使在不需要时也存在额外变量，对于需要同时进行多个此类“已经处理过”决策的任务不能很好地扩展

如果 parent-link 选项不可用，您可以在额外的 map 中维护 child-to-parent 关系：您在处理节点时从 child 映射到 parent 集。完成初始处理（构建地图）后，您将迭代地图并列出每个节点及其父节点。

与直接父链接相比的优势在于，在构建/修改图形时无需额外维护（除非您也想保持映射最新）

缺点是，在对图的结构进行一系列修改后，每次要处理图时都必须重新构建图（除非 -- 见注释）

注意：如果图中存在有向（父到子）圆，则通过遍历所有子图来遍历一般图可能会导致无限循环。我想这不是您的问题的情况，而只是为了涵盖所有基础：您可以在处理图表时维护一组“已访问”节点。可用选项的讨论与第一个（“链接回父级”）部分中的相同

于 2012-06-20T12:31:14.520 回答