节点搜索的图形遍历

Question

在下面的图中，子部分是递归遍历的。每个孩子都必须报告其直系父母。问题是子项[3]必须在同一行中同时报告其直接父级（即子项[2]和子项[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]

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

Answer 1

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

1. 维护一组访问过的节点，并检查当前节点是否在该集中。 如果没有，请处理它并将其添加到集合中;否则跳过。

   优点：一般方法

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

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

   优点：更少的额外内存

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

如果父链接选项不可用，则可以在额外的映射中维护子项到父项的关系：在处理节点时，从子项映射到父项集。 完成（构建映射）的初始处理后，您可以迭代映射并列出每个节点及其父节点。

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

缺点是，在对图形结构进行一系列修改后，每次想要处理图形时，您都必须重新构建地图（除非 - 请参阅注释以获取启示）

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