Предварительный / пост-порядок итеративного обхода n-арного дерева с использованием шаблона Iterator

Question

Я реализовал универсальное (n-арное) дерево в Java, как указано здесь и со ссылкой на источник, указанный в репозитории GitHub автора 1 .Я хочу реализовать предварительный и пост-порядок обхода n-арного дерева, используя Iterator в java.Таким образом, методы hasNext () будут возвращать true всякий раз, когда есть узел, а метод next () будет возвращать узел, который будет присутствовать следующим в обходе до / после заказа.

Я пытаюсьследуйте псевдокодам, приведенным в этом вопросе , но я не могу подключить его к следующему методу Итератора, который я написал ниже

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;
    }
}

Класс TreeNode:

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;
    }
}

Я знаю, что использование as-many для блоков при глубине дерева абсолютно неверно, но логика стека не была для меня интуитивно понятной.Если кто-то, пожалуйста, помогите мне, я буду очень признателен.

Спасибо, Чайтанья

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;

}