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

Question

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

是否有不使用堆栈或队列的有效方法来实现迭代器？

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

Answer 1

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

无论这条路径如何内存(内部节点列表，或者方向列表，如左-左-左-左，可能以位表示形式紧凑存储)，该存储的理论大小是 O( H)。

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

现在，一旦对树的大小进行了一些限制，谈论空间(或时间)复杂性当然就不再有意义了。例如，如果一棵树的高度永远不会超过 64，那么当前路径可以用 64 位无符号整数表示，可能还需要一些额外的小整数来表示该路径的当前大小。

由于可观测宇宙中的原子数量估计为 2²⁵⁰，您也可以使用它，并使用 256 位无符号整数(两个长整型)。无论如何，计算机内存永远无法存储那么高的完美树。