遍历树 - 分步

我有下面的代码遍历树（预购），但步骤：遍历树 - 分步

public void traverse(Node node) { 
    visit(node); 
    for (Node child : node.getChildren()) { 
     traverse(child); 
    } 
}

我想有一个一步一步的遍历。例如Iterator，这样可以成为另一个应用程序的客户端（调用者）可以控制遍历。（例如：在UI，我们有一个“下一步”按钮，点击这个按钮，我们要参观的下一个节点）

我目前的解决方案是这样的：

List<Node> nodes = new ArrayList<Node>(); 
collectNodes(root, nodes); 
Iterator<Node> it = nodes.iterator(); 
// do my job. 
... 

public void collectNodes(Node node, List<Node> nodes) { 
    nodes.add(node); 
    for (Node child : node.getChildren()) { 
     collectNodes(child, nodes); 
    } 
}

正如你所看到的在代码中，我正在访问所有节点（位于collectNodes中）以按预订格式收集并将其放入列表中。

我想知道是否有没有这种额外的（collectNodes）迭代的解决方案？

的问候，穆罕默德

来源

2012-05-24 mhshams

您发布的算法背后的想法是使用方法堆栈作为隐式数据结构。每当你进入遍历时，所有的节点都被隐式地推入到函数堆栈中，然后当你迭代它们时，它们被弹出。

现在为了使这个算法像迭代器一样可以挂起，你需要做的就是使这个隐式堆栈显式化。向你的班级添加一个堆栈，访问推送所有的孩子，然后始终使用堆栈中的顶级节点继续。您可以随时暂停此操作，同时将堆栈保持为可暂停和存储在任何地方的状态。

这个技巧实际上适用于任何种类的递归算法。

来源

2012-05-24 09:47:28 LiKao

-1

您可以一步找到使用迭代步骤树的遍历代码here

希望这会帮助你。

来源

2012-05-24 05:56:36

请将内容添加到答案本身。如果链接断开，仅链接答案就不好。 – Quentin

难道你不认为最后一行如果你的代码collectNodes(child)会给出错误，因为collectNodes()方法将接受两个参数。

来源

2015-09-17 06:36:13 Tapan

谢谢。它现在更新。 – mhshams

遍历树 - 分步

回答

相关问题