recursion - 没有递归的复合模式迭代器

Question

有没有人写过或考虑过在不使用递归的情况下为复合（树）结构编写迭代器？如果是这样，你能分享你的想法吗？谢谢

编辑：我正在考虑使用 Java 语言。

Answer 1

在没有递归的情况下遍历一棵树很简单。假设一棵二叉树，每个节点大概有三个对其他节点的引用。左孩子，右孩子和父母。因此，假设深度优先的从左到右的迭代顺序，while current.left-child != null, current = current.left-child如果没有左子，则在 while-lop（伪代码）中遵循左子引用，则尝试右子。如果也没有正确的孩子，则向上直到找到正确的孩子（while current.right-child == null, current = current.parent）

您还没有指定一种语言，但由于您想避免递归，我将假设它是某种命令式语言，然后上述应该是可能的。

简而言之，您的迭代器必须持有对当前节点的引用，以及有关其行进方式的一些信息。

Answer 2

您可能会从这个 SO 问题中得到一些启发： Post order traversal of binary tree without recursion 您所需要的只是将算法扩展到非二叉树。