递归遍历vs迭代树遍历

Question

所以我在研究树遍历算法。例如，在K-d树遍历中，我们的目标是遍历节点直至叶子。这与其说是一个树搜索，不如说是一个根到叶的遍历。

在这种情况下，递归解决方案就足够了。但是，在C等语言中，递归调用函数需要将值推送到堆栈上，并在堆栈帧之间跳跃等。标准的递归方法类似于：

void traverse(Node* ptr){
    if(ptr.left == null && ptr.right == null) return;
    if(ptr.val >= threshold) traverse(ptr.right);
    else if(ptr.val < threshold) traverse(ptr.left);
}
traverse(root);

因此，考虑到二叉树有一个明确的上界（我相信这也可以扩展到其他树类型），以迭代方式执行此遍历是否更有效：

Node* ptr = root;
for(int i = 0; i < tree.maxHeight; i++) {
    if (ptr.left == null && ptr.right == null) break;
    if (ptr.val >= threshold) ptr = ptr.right;
    else if (ptr.val < threshold) ptr = ptr.left
}

二叉树的最大高度是它的节点数，而平衡树的最大高度是log（n）。因此，我想知道迭代解决方案是否有任何缺点，或者它是否确实比普通递归更快。这里面有什么我遗漏的概念吗？

Answer 1

您的代码与其说是树遍历，不如说是树搜索。如果您只想从根到叶，那么迭代解决方案会更简单、更快，并且会使用更少的内存，因为您不必处理堆栈帧。

如果您想要对树进行完全遍历：也就是说，在访问每个节点时进行顺序遍历，那么您要么编写递归算法，要么实现自己的堆栈，在其中显式地推送和弹出节点。实现自己堆栈的迭代方法可能会更快，但无法避免O（logn）（在平衡二叉树中）或可能的O（n）（在退化树中）内存使用。实现显式堆栈将使用更少的内存，原因很简单，因为它只需要包含树节点指针，而完整堆栈框架包含的内存要多得多。