java - 树中的后置迭代器

我正在尝试为订单创建Iterator实现，但目前情况不佳。我能够获得有序和预购的实现，但似乎无法获得后购。如果你们能为我指出正确的方向并给我一些提示，那就太好了。

这是我的有序课程：

public class InOrderIterator<T> implements Iterator<T> {

    private final Deque<BinaryTreeNode<T>> stack;
    private BinaryTreeNode<T> current;

    public InOrderIterator(BinaryTreeNode<T> root){
        stack = new LinkedList<BinaryTreeNode<T>>();
        this.current = root;
    }

    @Override
    public boolean hasNext() {
        return (!stack.isEmpty() || current != null);
    }

    @Override
    public T next() {
        while (current != null) {
            stack.push(current);
            if (current.hasLeftChild())
                current = current.getLeftChild();
            else
                current = null;
        }

        current = stack.pop();
        BinaryTreeNode<T> node = current;
        if (current.hasRightChild())
            current = current.getRightChild();
        else
            current = null;

        return node.getData();
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}

以下是订购前，订购中和订购后的说明：

预购


访问根。
遍历左子树。
遍历右子树。


为了


遍历左子树。
访问根。
遍历右子树。


后订单


遍历左子树。
遍历右子树。
访问根。


http://en.wikipedia.org/wiki/Tree_traversal#Types

最佳答案

我用谷歌搜索了一个二叉树后置迭代器实现，但是找不到一个好的。所以我用两个堆栈实现了我的。

public class BinaryTreePostorderIterator implements Iterator<Integer> {
private TreeNode root;
private Stack<TreeNode> nodes;
private Stack<Boolean> expanded;
public BinaryTreePostorderIterator(TreeNode root) {
    this.root = root;
    nodes = new Stack<>();
    expanded = new Stack<>();
    if (root != null) {
        nodes.push(root);
        expanded.push(false);
    }
}
@Override
public Integer next() {
    if (!hasNext()) {
        throw new NoSuchElementException("End reached");
    }
    expanded.pop();
    return nodes.pop().val;
}

@Override
public boolean hasNext() {
    if (nodes.isEmpty()) {
        return false;
    }
    while (!expanded.peek()) {
        expanded.pop();
        expanded.push(true);
        TreeNode node = nodes.peek();
        if (node.right != null) {
            nodes.push(node.right);
            expanded.push(false);
        }
        if (node.left != null) {
            nodes.push(node.left);
            expanded.push(false);
        }
    }
    return true;
}

public static void main(String[] args) {
    TreeNode root = new TreeNode(5);
    root.left = new TreeNode(3);
    root.left.right = new TreeNode(4);
    root.left.left = new TreeNode(2);
    root.right = new TreeNode(7);
    root.right.right = new TreeNode(8);
    root.right.left = new TreeNode(6);

    BinaryTreePostorderIterator pi = new BinaryTreePostorderIterator(root);
    while (pi.hasNext()) {
        System.out.println(pi.next());
    }
}

}

关于java - 树中的后置迭代器，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23178926/