java - 使用 Iterator 模式对 n 叉树进行前序/后序迭代遍历

Question

我已经在给定的 Java 中实现了一个通用(n 元)树 here并引用 GitHub 上给出的来源作者资料库1 .我想在java中使用迭代器实现n叉树的前序和后序遍历。因此，只要存在节点，方法 hasNext() 就会返回 true，而方法 next() 将返回在前/后顺序遍历中下一个出现的节点。

我正在尝试遵循此 question 中给出的伪代码但我无法将它插入我在下面编写的 Iterator 的下一个方法中

public class DepthFirstIterator<T> implements Iterator<TreeNode<T>> {

    private Stack<TreeNode<T>> dfsStack;
    private Tree<T> tree;
    private TreeNode<T> start;

    public DepthFirstIterator(Tree<T> tree) {
        this.tree = tree;
        this.dfsStack = new Stack<TreeNode<T>>();
        if (!this.tree.isEmpty())
            this.dfsStack.push(this.tree.getRoot());
    }

    public DepthFirstIterator(Tree<T> tree, TreeNode<T> startNode) {
        this.tree = tree;
        this.dfsStack = new Stack<TreeNode<T>>();
        if (startNode != null)
            this.dfsStack.push(startNode);
    }

    public boolean hasNext() {
        return (!this.dfsStack.isEmpty());
    }

    public TreeNode<T> next() {
                // Iterative code to obtain pre/post-order traversal
    }

    public void remove() {
     // Do nothing
    } 

树类:

public class Tree<T> {

    private TreeNode<T> root;

    public TreeNode<T> getRoot() {
        return this.root;
    }

    public void setRoot(TreeNode<T> element) {
        this.root = element;
    }

    public boolean isEmpty() {
        return (this.root == null);
    }

    public int size() {
        if (isEmpty())
            return 0;
        else
            return getNumberOfNodes(root) + 1;
    }

    private int getNumberOfNodes(TreeNode<T> node) {
        int num = 0;
        Stack<TreeNode<T>> nodeStack = new Stack<TreeNode<T>>();
        nodeStack.push(node);
        while (!nodeStack.isEmpty()) {
            TreeNode<T> top = nodeStack.pop();
            for (TreeNode<T> child : top.getChildren()) {
                num++;
                nodeStack.push(child);
            }
        }
        return num;
    }
}

树节点类:

public class TreeNode<T> {

    private T data;
    private List<TreeNode<T>> children;
    private TreeNode<T> parent;

    public TreeNode() {
        super();
        children = new ArrayList<TreeNode<T>>();
        parent = null;
    }

    public TreeNode(T data) {
        this();
        setData(data);
    }

    public void setData(T data) {
        this.data = data;
    }

    public T getData() {
        return this.data;
    }

    public List<TreeNode<T>> getChildren() {
        return children;
    }

    public void setChildren(List<TreeNode<T>> children) {
        for (TreeNode<T> child : children)
            child.parent = this;
        this.children = children;
    }

    public void addChild(TreeNode<T> child) {
        child.parent = this;
        children.add(child);
    }

    public void insertChildAt(int index, TreeNode<T> child)
            throws IndexOutOfBoundsException {
        child.parent = this;
        children.add(index, child);
    }

    public TreeNode<T> getChildAt(int index) throws IndexOutOfBoundsException {
        return children.get(index);
    }

    public void removeChildAt(int index) throws IndexOutOfBoundsException {
        children.remove(index);
    }

    public void removeChildren() {
        children.clear();
    }

    public int getNumberOfChildren() {
        return children.size();
    }

    public String toString() {
        return getData().toString();
    }

    public boolean hasChildren() {
        return (getChildren().size() > 0);
    }

    public TreeNode<T> getParent() {
        return this.parent;
    }
}

我知道随着树的深度而使用尽可能多的 block 是完全错误的，但堆栈逻辑对我来说并不直观。如果有人可以指导我，我将不胜感激。

谢谢，柴坦尼亚

Answer 1

Stack<Treenode<T>> preorder;

/*在构造函数中:*/

preorder.push(tree.getRoot());

//预购下一个

public TreeNode<T> next() {
Treenode<t> ret = preorder.pop();

for (int i = ret.getChildren().size()-1 ; i>=0; i--) {
            preorder.push(ret.getChildAt(i));

        }
return ret;

}