二叉树后序迭代器
二叉树后序迭代器
提问于 2012-08-03 18:45:08
我正在PHP中实现一个AVL树(一个自平衡的二进制搜索树)，并且正常工作。我有顺序迭代器，预顺序迭代器和水平顺序迭代器，但是我不知道如何为BST做一个后续迭代器。谷歌搜索提供了如何进行迭代的后序遍历，而不是迭代器。
到目前为止，我唯一的成功是使用后期遍历来构建数组，然后返回数组迭代器。这是不好的，因为它迭代树两次，并增加了更多的空间复杂性。
构建后序迭代器的一般算法是什么？
/质询/标记/php标记出现在这里的唯一原因是PHP中的迭代器与C++或Java中的迭代器不同。可能会影响你的建议。
另外，如果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();
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2012-08-03 20:33:56
我几乎能够将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();
}
}我无法描述算法或证明它正在做什么，但希望随着时间的推移，它将是有意义的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11801536
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号