迭代二进制树,无需控制堆栈或动态分配

Question

在给定以下约束的情况下,是否有一种有效,实用的方法来迭代二叉树:

1. 您无法控制调用堆栈,因此可能无法使用递归.所有状态必须位于迭代器/范围对象内,而不是堆栈中.
2. 在算法的任何地方都不能使用堆分配.
3. 树可能是不可变的,因此您无法在其中存储迭代状态.
4. 你没有父指针.
5. 迭代器/范围结构不能太大,以至于传递给函数是完全不合理的.

编辑:

1. 这不是功课.我实际上正在尝试设计一个在第二个堆栈上构建二进制树的库,并对堆分配(或缺少堆分配)提供了很多保证.
2. 树木是平衡的.(它们是AVL树.)

Answer 1

它只能用于深度达到一定限度的树(因此也可以用于元素数量),因为它需要与树深度成比例的辅助存储器; 当你在一个项目上进行迭代时,你需要跟踪下一个要继续进行的项目,如果你处于最深的叶子之一,那么所需的"保持跟踪指针"的数量将是只比树的深度小1.例如,如果您可以接受限制为32的深度(因此不超过4,294,967,295个节点),则需要一个32个指针的辅助固定大小数组(加上其上的索引).

对于不完全退化的二进制树(因此有许多节点大致成比例2**depth,而不仅仅是depth;-),这个固定数量的辅助内存应该是可接受的 - 即,只需按log(N)指针顺序固定辅助内存迭代任何具有N节点的树.如果这是不可接受的,那么您的问题的答案"是否......？" 是没有 ;-).

Answer 2

如果保证树的值按其值排序,并且这些值严格上升(所有B> A,而不仅仅是B> = A),那么您可以使用无动态内存遍历无限大小的树.但是你确实会受到性能的影响.

要在值A之后找到下一个值,只需再次下降到树中,执行二进制(当然)搜索大于A的值.

我只是想到了这一点.如果有人能够证明我的想法是错误的,请继续!