二叉搜索树后序迭代器

Question

I'm implementing an AVL Tree (a self-balancing Binary Search Tree) in PHP and have things working pretty normally. I have in-order, pre-order, and level-order iterators working, but I can't figure out how to do a post-order iterator for a BST. Google searches turn up how to do an iterative post-order traversal, but not an iterator.

So far my only success has been to use a post-order traversal to build an array and then return an array iterator. This is bad because it iterates the tree twice and adds more space complexity.

What is the general algorithm for building a post-order iterator?

The only reason the php tag is here is that iterators in PHP are different from the ones in Java or C++. It might affect your advice.

Also, if PHP had generators, this would be a breeze because the post-order traversal could simply yield values, turning it into an iterator . . .

Edit: here is the in-order iterator implementation. Maybe it can help you understand what I want from a post-order iterator:

class InOrderIterator implements Iterator {

    /**
     * @var ArrayStack
     */
    protected $stack;

    /**
     * @var BinaryNode
     */
    protected $root;

    /**
     * @var BinaryNode
     */
    protected $value;

    public function __construct(BinaryNode $root) {
        $this->stack = new ArrayStack;
        $this->root = $root;
    }

    /**
     * @link http://php.net/manual/en/iterator.current.php
     * @return mixed
     */
    public function current() {
        return $this->value->getValue();
    }

    /**
     * @link http://php.net/manual/en/iterator.next.php
     * @return void
     */
    public function next() {
        /**
         * @var BinaryNode $node
         */
        $node = $this->stack->pop();

        $right = $node->getRight();
        if ($right !== NULL) {
            // left-most branch of the right side
            for ($left = $right; $left !== NULL; $left = $left->getLeft()) {
                $this->stack->push($left);
            }
        }

        if ($this->stack->isEmpty()) {
            $this->value = NULL;
            return;
        }
        $this->value = $this->stack->peek();

    }

    /**
     * @link http://php.net/manual/en/iterator.key.php
     * @return NULL
     */
    public function key() {
        return NULL; //no keys in a tree . . .
    }

    /**
     * @link http://php.net/manual/en/iterator.valid.php
     * @return boolean
     */
    public function valid() {
        return $this->value !== NULL;
    }

    /**
     * @link http://php.net/manual/en/iterator.rewind.php
     * @return void
     */
    public function rewind() {
        $this->stack->clear();

        for ($current = $this->root; $current !== NULL; $current = $current->getLeft()) {
            $this->stack->push($current);
        }

        $this->value = $this->stack->peek();
    }
}

Answer 1

I was able to ALMOST convert an example of an iterative traversal in C++ into an iterator. Latest on github. Still need to figure out a few cases.

class PostOrderIterator implements Iterator {

    /**
     * @var ArrayStack
     */
    protected $stack;

    /**
     * @var BinaryNode
     */
    protected $root;

    /**
     * @var BinaryNode
     */
    protected $value;

    protected $current;

    public function __construct(BinaryNode $root) {
        $this->stack = new ArrayStack;
        $this->root = $root;
    }

    /**
     * @link http://php.net/manual/en/iterator.current.php
     * @return mixed
     */
    public function current() {
        return $this->current->getValue();
    }

    /**
     * @link http://php.net/manual/en/iterator.next.php
     * @return void
     */
    public function next() {
        /**
         * @var BinaryNode $node
         */
        if ($this->value !== NULL) {
            $right = $this->value->getRight();
            if ($right !== NULL) {
                $this->stack->push($right);
            }
            $this->stack->push($this->value);
            $this->value = $this->value->getLeft();
            $this->next();
            return;
        }

        if ($this->stack->isEmpty()) {
            $this->current = $this->value;
            $this->value = NULL;
            return;
        }

        $this->value = $this->stack->pop();

        $right = $this->value->getRight();
        if ($right !== NULL && !$this->stack->isEmpty() && ($right === $this->stack->peek())) {
            $this->stack->pop();
            $this->stack->push($this->value);
            $this->value = $this->value->getRight();
            $this->current = $this->value;
        } else {

            if ($this->current === $this->value) {
                $this->value = NULL;
                $this->next();
            } else {
                $this->current = $this->value;
                $this->value = NULL;
            }
        }

    }

    /**
     * @link http://php.net/manual/en/iterator.key.php
     * @return NULL
     */
    public function key() {
        return NULL; //no keys in a tree . . .
    }

    /**
     * @link http://php.net/manual/en/iterator.valid.php
     * @return boolean
     */
    public function valid() {
        return $this->current !== NULL;
    }

    /**
     * @link http://php.net/manual/en/iterator.rewind.php
     * @return void
     */
    public function rewind() {
        $this->stack->clear();

        $this->value = $this->root;
        $this->next();
    }
}

I'm not able to describe the algorithm or justify what it is doing, but hopefully over time it will make sense.