java - 递归迭代程序

Question

这个问题已经有答案了:

Non-recursive depth first search algorithm [closed] (18 个回答)

已关闭 4 年前。

我试图将递归程序转换为非递归程序。该程序的目的是遍历数据结构。

请查看以下数据结构

class Node {
}

class LeafNode extends Node {
    private int leafNodeValue;

    public LeafNode (int leafNodeValue) {
        this.leafNodeValue= leafNodeValue;
    }

   public int getLeafNodeValue() {
      return leafNodeValue;
   }
   public void setLeafNodeValue(int leafNodeValue ) {
     this.leafNodeValue = leafNodeValue;
   }
}

class NonLeafNode extends Node {
    private List<Node> nodeList = new ArrayList<>();

    public List<Node> getNodeList() {
       return nodeList ;
    }
    public void setNodeList(List<Node> nodeList) {
       this.nodeList = nodeList;
    }
}

这是我的递归节点遍历类，我无法以非递归方式重写它。

递归遍历类

public class RecursiveTraversal {
    public static void main (String[] args ) {
        NonLeafNode node1 = new NonLeafNode();

        NonLeafNode node2 = new NonLeafNode();
        node2.getNodeList().add(new LeafNode(1));

        NonLeafNode node3 = new NonLeafNode();
        node3.getNodeList().add(new LeafNode(2));

        node2.getNodeList().add(node3);

        NonLeafNode node4 = new NonLeafNode();
        node4.getNodeList().add(new LeafNode(3));

        node1.getNodeList().add(node2);
        node1.getNodeList().add(node4);
        node1.getNodeList().add(new LeafNode(4));

        for (Node nodeItem : node1.getNodeList())
            traverse(nodeItem);
    }

    public static void traverse (Node node) {
        if (node instanceof LeafNode)
            System.out.println(" Leaf Node " + ((LeafNode) node).getLeafNodeValue());
        else if (node instanceof NonLeafNode)
            for (Node nodeItem: ((NonLeafNode) node).getNodeList())
                traverse(nodeItem);
    }
}

程序的输出应该是1,2,3,4。

有人可以帮我编写上述程序的迭代版本吗？

Answer 1

要使其迭代，只需使用 while 循环或 for 循环。

所以类似:

while(getLeafNode() != null) {
  // etc
}

另外:

prvate int leafNodeValue;

可能应该是私有(private)的而不是私有(private)的？