3

我有一个问题要在 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 ... 以此类推

所有被追踪的号码都需要按上述方式依次追踪和记录。任何人都可以帮助解决如何实现它的算法？谢谢。

4

2 回答 2

4

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

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 + " ");
}
于 2012-04-29T12:38:53.700 回答
1

您所描述的内容称为深度优先搜索。你应该知道这不是最有效的算法，还有更好的算法，比如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}
于 2012-04-29T12:15:29.843 回答