作者热门文章
- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
我正在用 PHP 实现一个 AVL 树(一个自平衡的二叉搜索树)并且一切正常。我有有序、预序和层序 迭代器 工作,但我无法弄清楚如何为 BST 执行后序迭代器。 Google 搜索显示了如何进行迭代后序遍历,但没有显示迭代器。
到目前为止,我唯一的成功是使用后序遍历来构建一个数组,然后返回一个数组迭代器。这很糟糕,因为它对树进行了两次迭代并增加了更多的空间复杂度。
构建后序迭代器的一般算法是什么?
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();
}
}
最佳答案
我几乎可以将 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();
}
}
我无法描述该算法或证明它在做什么,但希望随着时间的推移它会有意义。
关于php - 二叉搜索树后序迭代器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11801536/
序 大家好呀,我是summo,这次来写写我在上班空闲(摸鱼)的时候做的一个小网站的事。去年阿里云不是推出了个活动嘛,2核2G的云服务器一年只要99块钱,懂行的人应该知道这个价格在业界已经是非常良心了
我尝试根据给定的级别顺序(BFS 顺序)构造 BST。我知道这是可能的,但我不知道我该怎么写。问题是我必须使用 BFS 序列。所以,我不能在这里使用递归,我必须迭代地编写我的程序......我发现这有
我是一名优秀的程序员,十分优秀!