我最近一直在编写一堆不同的二叉搜索树实现（AVL、splay、treap），我很好奇是否有一种特别“好”的方式来编写迭代器来遍历这些结构。我现在使用的解决方案是让 BST 中的每个节点都存储指向树中下一个和上一个元素的指针，这将迭代减少到标准的链表迭代。但是，我对这个答案并不满意。它通过两个指针（下一个和上一个）增加了每个节点的空间使用量，在某种意义上它只是作弊。
我知道一种构建二叉搜索树迭代器的方法，该迭代器使用 O(h) 辅助存储空间（其中 h 是树的高度），通过使用堆栈来跟踪边界节点以便稍后探索，但我由于内存使用，我拒绝对此进行编码。我希望有某种方法可以构建一个只使用常量空间的迭代器。
我的问题是 - 有没有办法在具有以下属性的二叉搜索树上设计迭代器？
next()并且hasNext()查询在 O(1) 时间内运行。为了更容易，如果您假设树结构在迭代期间没有改变形状（即没有插入、删除或旋转），那很好，但如果有一个确实可以处理这个问题的解决方案，那就太酷了。
最简单的迭代器存储最后看到的键，然后在下一次迭代中，搜索树中该键的最小上限。迭代是 O(log n)。这具有非常简单的优点。如果键很小，那么迭代器也很小。当然，它的缺点是迭代树的方式相对较慢。它也不适用于非唯一序列。
有些树完全使用您已经使用的实现，因为扫描速度非常快对于它们的特定用途很重要。如果每个节点中的键的数量很大，那么存储兄弟指针的代价就不会太繁重。大多数 B 树都使用这种方法。
许多搜索树实现在每个节点上保留一个父指针以简化其他操作。如果你有，那么你可以使用一个简单的指向最后看到的节点的指针作为你的迭代器的状态。在每次迭代中，您都会在最后看到的节点的父节点中查找下一个子节点。如果没有更多兄弟姐妹，那么您将再上一层。
如果这些技术都不适合您，您可以使用存储在迭代器中的节点堆栈。这与正常遍历搜索树时的函数调用堆栈提供相同的功能，但不是遍历兄弟节点并递归子节点，而是将子节点压入堆栈并返回每个连续的兄弟节点。
正如 TokenMacGuy 提到的，您可以使用存储在迭代器中的堆栈。这是一个在 Java 中快速测试过的实现：
/**
* An iterator that iterates through a tree using in-order tree traversal
* allowing a sorted sequence.
*
*/
public class Iterator {
private Stack<Node> stack = new Stack<>();
private Node current;
private Iterator(Node argRoot) {
current = argRoot;
}
public Node next() {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
Node node = current;
current = current.right;
return node;
}
public boolean hasNext() {
return (!stack.isEmpty() || current != null);
}
public static Iterator iterator(Node root) {
return new Iterator(root);
}
}
其他变化是在构建时遍历树并将遍历保存到列表中。之后您可以使用列表迭代器。
好的，我知道这已经过时了，但不久前在微软的一次采访中我被问到这个问题，我决定稍微研究一下。我已经对此进行了测试，并且效果很好。
template <typename E>
class BSTIterator
{
BSTNode<E> * m_curNode;
std::stack<BSTNode<E>*> m_recurseIter;
public:
BSTIterator( BSTNode<E> * binTree )
{
BSTNode<E>* root = binTree;
while(root != NULL)
{
m_recurseIter.push(root);
root = root->GetLeft();
}
if(m_recurseIter.size() > 0)
{
m_curNode = m_recurseIter.top();
m_recurseIter.pop();
}
else
m_curNode = NULL;
}
BSTNode<E> & operator*() { return *m_curNode; }
bool operator==(const BSTIterator<E>& other)
{
return m_curNode == other.m_curNode;
}
bool operator!=(const BSTIterator<E>& other)
{
return !(*this == other);
}
BSTIterator<E> & operator++()
{
if(m_curNode->GetRight())
{
m_recurseIter.push(m_curNode->GetRight());
if(m_curNode->GetRight()->GetLeft())
m_recurseIter.push(m_curNode->GetRight()->GetLeft());
}
if( m_recurseIter.size() == 0)
{
m_curNode = NULL;
return *this;
}
m_curNode = m_recurseIter.top();
m_recurseIter.pop();
return *this;
}
BSTIterator<E> operator++ ( int )
{
BSTIterator<E> cpy = *this;
if(m_curNode->GetRight())
{
m_recurseIter.push(m_curNode->GetRight());
if(m_curNode->GetRight()->GetLeft())
m_recurseIter.push(m_curNode->GetRight()->GetLeft());
}
if( m_recurseIter.size() == 0)
{
m_curNode = NULL;
return *this;
}
m_curNode = m_recurseIter.top();
m_recurseIter.pop();
return cpy;
}
};
树遍历，来自维基百科：
所有示例实现都需要与树的高度成比例的调用堆栈空间。在平衡不良的树中，这可能是相当可观的。
我们可以通过在每个节点中维护父指针或通过线程化树来消除堆栈要求。在使用线程的情况下，这将大大改进中序遍历，尽管检索前序和后序遍历所需的父节点将比简单的基于堆栈的算法慢。
在文章中有一些用于 O(1) 状态迭代的伪代码，可以很容易地适应迭代器。
使用深度优先搜索技术怎么样。迭代器对象必须有一堆已经访问过的节点。
如果使用堆栈，则只能实现“额外内存使用 O(h)，h 是树的高度”。但是，如果您只想使用 O(1) 额外内存，则需要记录以下分析： - 如果当前节点有右孩子：找到右子树的最小值 - 当前节点没有右孩子，您需要从根开始寻找它，并不断更新它的最低祖先，也就是它最低的下一个节点
public class Solution {
//@param root: The root of binary tree.
TreeNode current;
TreeNode root;
TreeNode rightMost;
public Solution(TreeNode root) {
if(root==null) return;
this.root = root;
current = findMin(root);
rightMost = findMax(root);
}
//@return: True if there has next node, or false
public boolean hasNext() {
if(current!=null && rightMost!=null && current.val<=rightMost.val) return true;
else return false;
}
//O(1) memory.
public TreeNode next() {
//1. if current has right child: find min of right sub tree
TreeNode tep = current;
current = updateNext();
return tep;
}
public TreeNode updateNext(){
if(!hasNext()) return null;
if(current.right!=null) return findMin(current.right);
//2. current has no right child
//if cur < root , go left; otherwise, go right
int curVal = current.val;
TreeNode post = null;
TreeNode tepRoot = root;
while(tepRoot!=null){
if(curVal<tepRoot.val){
post = tepRoot;
tepRoot = tepRoot.left;
}else if(curVal>tepRoot.val){
tepRoot = tepRoot.right;
}else {
current = post;
break;
}
}
return post;
}
public TreeNode findMin(TreeNode node){
while(node.left!=null){
node = node.left;
}
return node;
}
public TreeNode findMax(TreeNode node){
while(node.right!=null){
node = node.right;
}
return node;
}
}
使用 O(1) 空间，这意味着我们不会使用 O(h) 堆栈。
开始：
有下一个（）？current.val <= endNode.val 检查树是否被完全遍历。
通过最左边查找最小值：我们总是可以查找最左边以找到下一个最小值。
一旦检查了最左边的最小值（命名它current）。Next min 将是 2 种情况：如果 current.right != null，我们可以继续寻找 current.right 最左边的孩子，作为 next min。或者，我们需要向后看父母。使用二叉搜索树查找当前的父节点。
注意：在对 parent 进行二分搜索时，请确保它满足 parent.left = current。
因为：如果 parent.right == current，则该父级必须之前已访问过。在二叉搜索树中，我们知道 parent.val < parent.right.val。我们需要跳过这种特殊情况，因为它会导致无限循环。
public class BSTIterator {
public TreeNode root;
public TreeNode current;
public TreeNode endNode;
//@param root: The root of binary tree.
public BSTIterator(TreeNode root) {
if (root == null) {
return;
}
this.root = root;
this.current = root;
this.endNode = root;
while (endNode != null && endNode.right != null) {
endNode = endNode.right;
}
while (current != null && current.left != null) {
current = current.left;
}
}
//@return: True if there has next node, or false
public boolean hasNext() {
return current != null && current.val <= endNode.val;
}
//@return: return next node
public TreeNode next() {
TreeNode rst = current;
//current node has right child
if (current.right != null) {
current = current.right;
while (current.left != null) {
current = current.left;
}
} else {//Current node does not have right child.
current = findParent();
}
return rst;
}
//Find current's parent, where parent.left == current.
public TreeNode findParent(){
TreeNode node = root;
TreeNode parent = null;
int val = current.val;
if (val == endNode.val) {
return null;
}
while (node != null) {
if (val < node.val) {
parent = node;
node = node.left;
} else if (val > node.val) {
node = node.right;
} else {//node.val == current.val
break;
}
}
return parent;
}
}
根据定义，next() 和 hasNext() 不可能在 O(1) 时间内运行。当您查看 BST 中的特定节点时，您不知道其他节点的高度和结构，因此您不能只是“跳转”到正确的下一个节点。
但是，空间复杂度可以降低到 O(1)（除了 BST 本身的内存）。这是我在 C 中的做法：
struct node{
int value;
struct node *left, *right, *parent;
int visited;
};
struct node* iter_next(struct node* node){
struct node* rightResult = NULL;
if(node==NULL)
return NULL;
while(node->left && !(node->left->visited))
node = node->left;
if(!(node->visited))
return node;
//move right
rightResult = iter_next(node->right);
if(rightResult)
return rightResult;
while(node && node->visited)
node = node->parent;
return node;
}
诀窍是同时拥有父链接和每个节点的已访问标志。在我看来，我们可以说这不是额外的空间使用，它只是节点结构的一部分。显然，必须调用 iter_next() 而不改变树结构的状态（当然），而且“已访问”标志不会改变值。
这是调用 iter_next() 并每次打印此树的值的测试器函数：
27
/ \
20 62
/ \ / \
15 25 40 71
\ /
16 21
int main(){
//right root subtree
struct node node40 = {40, NULL, NULL, NULL, 0};
struct node node71 = {71, NULL, NULL, NULL, 0};
struct node node62 = {62, &node40, &node71, NULL, 0};
//left root subtree
struct node node16 = {16, NULL, NULL, NULL, 0};
struct node node21 = {21, NULL, NULL, NULL, 0};
struct node node15 = {15, NULL, &node16, NULL, 0};
struct node node25 = {25, &node21, NULL, NULL, 0};
struct node node20 = {20, &node15, &node25, NULL, 0};
//root
struct node node27 = {27, &node20, &node62, NULL, 0};
//set parents
node16.parent = &node15;
node21.parent = &node25;
node15.parent = &node20;
node25.parent = &node20;
node20.parent = &node27;
node40.parent = &node62;
node71.parent = &node62;
node62.parent = &node27;
struct node *iter_node = &node27;
while((iter_node = iter_next(iter_node)) != NULL){
printf("%d ", iter_node->value);
iter_node->visited = 1;
}
printf("\n");
return 1;
}
它将按排序顺序打印值：
15 16 20 21 25 27 40 62 71