c++ - 我可以在没有堆栈的二进制搜索树中实现迭代器吗？

Question

假设我有二叉搜索树。每个节点都有两个指向子节点的指针，而没有指向父节点的指针。

有没有在不使用堆栈或队列的情况下实现迭代器的有效方法？

高效是指能够找到O(1)复杂度的下一个元素。

Answer 1

想象一个高度为h的完美树的情况。当迭代器位于第一个节点(最左边的叶子)时，它将需要记住它是通过哪个内部节点到达此节点的，因为在接下来的步骤之一中，它将需要在这些节点(及其节点)中产生值。右子树)。由于没有父节点指针，因此此信息不容易获得，必须存储在某个位置。

不管该路径如何存储(内部节点列表或方向列表，如left-left-left-left-left，都可能以位表示形式紧凑存储)，该存储的理论大小为O(h)。

如以下注释中所述，仅存储方向将需要在迭代的每个步骤中从根部再次沿着路径走下去。或者，您可以记住上次访问的值，然后使用二进制搜索来找到下一个节点。如果树中的所有值都是唯一的，则实际值的内存大小将至少与紧凑路径表示(按位左-左-左...)具有相同的数量级，因此无论哪种方式(存储路径) ，或上次访问的值)的存储要求类似。

现在，只要对树的大小设置一定的限制，谈论空间(或时间)的复杂性就毫无意义了。例如，如果一棵树的高度永远不会超过64，那么当前路径可以用64位无符号整数表示，也许还有一些其他小整数表示该路径的当前大小。

由于可观测宇宙中的原子数估计为2250，因此您也可以使用它，并使用256位无符号整数(两个long)代替。计算机内存将永远无法以任何方式存储这种高度的完美树。