java - 遍历一棵树 - 但一步一步

Question

我有以下代码来遍历树(预购):

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

我想要一步一步的遍历。类似于 Iterator 的东西，以便可以是另一个应用程序的客户端(调用者)可以控制遍历。 (例如:在 UI 中我们有一个“Next”按钮，通过点击这个按钮，我们必须访问下一个节点)

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

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) 迭代是否有任何解决方案？

问候，穆罕默德

Answer 1

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

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

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