我最近一直在编码一堆不同的二进制搜索树实现（AVL，splay，treap），并且很好奇是否有一种特别好的方法来编写迭代器以遍历这些结构。我现在使用的解决方案是让BST中的每个节点存储指向树中下一个和上一个元素的指针，这将迭代减少为标准的链表迭代。但是，我对这个答案并不满意。它通过两个指针（下一个和上一个）增加了每个节点的空间使用率，从某种意义上说，这只是作弊。
我知道一种构建二叉搜索树迭代器的方法，该迭代器使用O（h）辅助存储空间（其中h是树的高度），方法是使用堆栈来跟踪边界节点以供以后探索，但是我由于内存占用，我拒绝对此进行编码。我希望有某种方法可以构建仅使用恒定空间的迭代器。
我的问题是-有没有一种方法可以在具有以下属性的二进制搜索树上设计迭代器？
next()
hasNext()
为了简化起见，如果您假设树结构在迭代过程中没有改变形状（即没有插入，删除或旋转），那就很好了，但是如果有确实可以解决这个问题的解决方案，那真的很酷。
可能最简单的迭代器存储最后看到的密钥，然后在下一次迭代时，在树中搜索该密钥的最小上限。迭代为O（log n）。这具有非常简单的优点。如果密钥较小，则迭代器也较小。当然，它的缺点是迭代树的方法相对较慢。它也不适用于非唯一序列。
有些树正好使用您已经使用的实现，因为对于它们的特定用途来说，扫描非常快很重要。如果每个节点中的键数很大，那么存储同级指针的代价就不会太麻烦。大多数B树使用此方法。
许多搜索树实现都在每个节点上保留一个父指针，以简化其他操作。如果有，则可以使用指向最后看到的节点的简单指针作为迭代器的状态。在每次迭代中，您都在最后看到的节点的父节点中寻找下一个子节点。如果没有更多的兄弟姐妹，那么您将再上一层。
如果这些技术都不适合您，则可以使用存储在迭代器中的一堆节点。当正常遍历搜索树时，此功能与函数调用堆栈的功能相同，但是您无需将同级循环并在子级上进行递归，而是将子级推入堆栈并返回每个后续的同级。
