java - 树中的后序迭代器

Question

我正在尝试为后订单创建一个 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();
    }

}

以下是订单前、订单中和订单后的描述:

预订

1. 访问根。
2. 遍历左子树。
3. 遍历右子树。

有序

1. 遍历左子树。
2. 访问根。
3. 遍历右子树。

后单

1. 遍历左子树。
2. 遍历右子树。
3. 访问根。

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

Answer 1

我在 google 上搜索了二叉树后序迭代器的实现，但找不到合适的。所以我使用两个堆栈实现了我的。

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