二進制搜索樹後階次迭代器

Question

我在PHP中實現了一個AVL樹（一個自平衡的二進制搜索樹），並且事情工作非常正常。我有順序，預訂和級別順序迭代器工作，但我不知道如何做一個BST的後序迭代器。谷歌搜索提出瞭如何進行迭代後序遍歷，但不是迭代器。

到目前爲止，我的唯一成功是使用後序遍歷來構建數組，然後返回數組迭代器。這很糟糕，因爲它會重複執行兩次樹並增加更多空間複雜度。

什麼是構建後序迭代器的一般算法？

php標籤在這裏的唯一原因是PHP中的迭代器與Java或C++中的迭代器不同。這可能會影響你的建議。另外，如果PHP有生成器，這將是一件輕而易舉的事情，因爲後序遍歷可以簡單地產生值，將它變成一個迭代器。 。 。

編輯：這裏是按順序迭代器的實現。也許它可以幫助你理解我從後序迭代想：

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

我幾乎能夠轉換成C++迭代遍歷的例子爲迭代器。 Latest on 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(); 
    } 
} 

我無法描述算法或證明它正在做什麼，但希望隨着時間的推移它會有意義。