迭代时如何知道我在树的末尾？

Question

我正在为树结构（左子指针、右子指针、父指针）编写（中序）迭代器，但我卡住了，因为我想不出停止迭代的方法已经访问了所有节点。如何检查我当前所在的节点是否是树的最后一个节点？

编辑

这里的树结构应该是二叉树，我需要中序遍历来实现节点的词法顺序"keys"我已经完成了递归版本-我正在尝试做迭代版本，因为很多其他函数遍历树，我不太确定如何编写足够通用的递归版本来支持所有用途。

如果我最初的问题不准确，我很抱歉，如果您认为合适，请投反对票。

Answer 1

一种方法是在搜索树之前计算节点总数，比如N。然后你可以使用size_t counter来计算它，即将counter的引用传递给递归调用树搜索，并在每个最终节点执行 ++counter。

Answer 2

如果你是递归的，这是算法固有的，你不需要手动检查，按照下面的伪代码：

def processTree(node):
    if node == null: return
    processTree(node.left)
    print(node.value)
    processTree(node.right)

processTree(rootNode)

考虑处理最后一个节点的点，在下面的树中说 7：

    __1__
   /     \
  2       3
 / \     / \
4   5   6   7

到那时，您将已经处理完左侧的所有内容和所有父项，因此您只需爬上树并退出即可。