Java泛型树遍历

Question

我需要解决Java中的一个问题。我有一棵需要遍历的树。以下是它的结构：

        1
     /     \
   1 2 3  1 2 3      
 /   |  \    \
123 123 123  same for those three nodes

现在需要遍历的方式是从根节点开始，沿着最深左侧节点（这里是1）和它的最左侧叶子节点（1）进行遍历。之后应该从根节点重新开始追踪所有数字，这一次到达同一最深左侧节点的下一个叶子节点...以此类推，也就是从顶部开始，每次一个接一个地到达该节点的所有剩余叶子节点。在追踪完所有最左侧节点的叶子节点之后，应按照惯例继续进行（从顶部开始），现在移动到下一个未邀请的节点（这里是2）...对于整棵树都是如此。因此，前6个迹线将是：

111 112 113 121 122 123 ...以此类推

需要跟踪和记录上述遍历到的所有数字，并按照上述方式进行。有谁能提供算法帮助实现它吗？谢谢。

- foofighter

Answer 1

你需要的是一种树遍历算法。

void traverse(Node root, String path) {
    path += root.getValue();
    for (Node child : root.getChildren())
        traverse(child, path);

    // end of current traversal
    if (root.getChildren().isEmpty())
        System.out.print(path + " ");
}

- Garrett Hall

Answer 2

您所描述的是深度优先搜索。您应该知道，这不是最适合此工作的算法，还有更好的算法，例如Dijkstra算法。

根据您要做什么，甚至可以采用更专业的策略，例如Alpha-Beta剪枝或其他启发式游戏搜索。

如果您决定使用深度优先搜索并希望返回从根节点到该节点的路径，则可以在找到目标节点后使用以下内容。假设node是您的目标节点...

List<Node> path = new ArrayList<Node>();
path.add(node);
while(node.parent != null){
  path.add(node.parent);
  node = node.parent;
}
return path; //returns a path from {goal,...,root}

- Aidanc

---

@unbeli 是的，你说得对..这和搜索没有任何关系..到目前为止还没有人提出任何想法.. - foofighter