3

PHP で AVL ツリー (自己均衡二分探索ツリー) を実装しており、かなり正常に動作しています。インオーダー、プリオーダー、およびレベルオーダーのイテレーターが機能していますが、BST のポストオーダー イテレーターを実行する方法がわかりません。Google 検索では、反復的なポストオーダー トラバーサルを行う方法が見つかりますが、イテレータは見つかりません。

これまでのところ、私の唯一の成功は、配列を構築し、配列イテレータを返すためにポストオーダー トラバーサルを使用することでした。これは、ツリーを 2 回反復し、スペースの複雑さが増すため、良くありません。

ポストオーダーイテレータを構築するための一般的なアルゴリズムは何ですか?

タグがここにある唯一の理由は、PHP の反復子が Java や C++ の反復子と異なるためです。あなたのアドバイスに影響するかもしれません。

また、PHP にジェネレーターがあれば、ポストオーダー トラバーサルは単純に値を生成し、それを 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();
    }
}
4

1 に答える 1

0

C++での反復トラバーサルの例をほとんどイテレーターに変換することができました。githubの最新情報。まだいくつかのケースを理解する必要があります。

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

アルゴリズムを説明したり、アルゴリズムが何をしているのかを正当化することはできませんが、時間の経過とともに意味がわかるようになることを願っています。

于 2012-08-03T20:33:56.683 に答える