3

我有以下代码来遍历一棵树（预购）：

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

我想要一步一步的遍历。类似 an 的东西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）迭代的解决方案？

问候，穆罕默德

4

3 回答 3

2

您发布的算法背后的想法是将方法堆栈用作隐式数据结构。每当您输入 traverse 时，所有节点都会隐式推送到函数堆栈上，然后当您遍历它们时，它们会被弹出。

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

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

于 2012-05-24T09:47:28.407 回答
0

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

于 2015-09-17T06:36:13.397 回答
-1

您可以在此处找到使用迭代器逐步遍历树的代码

希望这会帮助你。

于 2012-05-24T05:56:36.630 回答