将递归二叉树遍历转换为迭代方式

Question

我被要求写迭代版本，但我写了递归版本，即：

void inorderTraverse(BinaryTree root)
{
    if(root==NULL)
        printf("%d",root->id);
    else
    {
        inorderTraverse(root->left);
        printf("%d",root->id);
        inorderTraverse(root->right);
    }
}

我不是在寻找代码，而是想要理解这个如何完成。如果只是最后一次递归调用，我会做的。

void inorderTraverse(BinaryTree root)
{
    while(root!=NULL)
    {
        printf("%d",root->id);
        root=root->right;
    }
}

但是，当有两个递归调用时，我该如何转换成迭代程序？

以下是类型定义。

struct element{
    struct element* parent;
    int id;
    char* name;
    struct element* left;
    struct element* right;
};
typedef element* BinaryTree;

这是我的想法，我走在正确的道路上吗？

temp=root;
while(1)
{
    while(temp!=NULL)
    {
     push(s,temp);
     temp=temp->left;
     continue;
    }

    temp=pop(s);
    if(temp==NULL)
    return;
    printf("%d\t",temp->data);
    temp=temp->right;
}

- Kraken

---

你能展示一下 BinaryTree 接口吗？获取树节点的父节点是否可行？ - Arnout Engelen

可能是每个递归都可以转换为迭代吗？的重复问题，将递归算法转换为迭代算法的设计模式。 - outis

Answer 1

你看到的问题是你需要“记住”你最后一次迭代的位置。
在递归时，程序内部使用“堆栈”来记住要返回的位置。
但是在进行迭代时，它不会这样做。
虽然...这给了你一个想法吗？

- user541686

---

我知道这与将事物推入堆栈然后弹出它们有关，但我真的无法弄清楚，例如要推什么，何时弹出以及如何弹出。 - Kraken

@Karan：我不确定你的代码中为什么要有if(temp==NULL)--你从来没有推入过一个NULL，那么为什么要弹出一个NULL呢？或者这是用来表示空条件的信号吗？但除此之外，它看起来很好...你试过了吗？ - user541686

是的，那是用来检查空值的。但是，我没有得到期望的结果。中序遍历没有实现。 - Kraken

抱歉，它是正确的，我以为输出顺序错了。谢谢。 - Kraken

是的，我明白如何向上遍历树了。因为当我弹出节点时，它不再留在堆栈中（显然），下一次弹出节点时，它会让我向前迈进一步。所以我想，从递归到迭代的方法就是看看你的堆栈将如何运作，并相应地实现它，对吧？ - Kraken

Answer 2

我暂时想不到一种真正优雅的迭代方式。

一个可能的方法是使用“标记算法”，其中您从所有节点“未标记”开始，并在处理它们时“标记”节点。标记可以添加到对象模型中或保留在单独的实体中。

伪代码：

for (BinaryTree currentNode = leftmostNode(root); currentNode != null; currentNode = nextNode(currentNode)):
  print currentNode;
  currentNode.seen = true;

sub nextNode(BinaryTree node):
  if (!node.left.seen):
    return leftmostNode(node.left)
  else if (!node.seen)
    return node
  else if (!node.right.seen)
    return leftmostNode(node.right)
  else 
    return nextUnseenParent(node)

sub leftmostNode(BinaryTree node):
  while (node.left != null)
    node = node.left
  return node;

sub nextUnseenParent(BinaryTree node):
  while (node.parent.seen)
    node = node.parent
  return node.parent

- Arnout Engelen

---

我也是想要这样的东西， 但这算作迭代版本吗？ - Kraken

而且，我认为这不是一个中序遍历，事实上，你从根节点开始打印。 - Kraken

“迭代步骤”比通常的要复杂一些，但它只包含for循环、while循环和没有递归调用，所以我认为它应该被视为迭代。 - Arnout Engelen

Answer 3

我认为，从父节点向左节点迭代并不是问题。问题在于当从一个节点向上到父节点时应该怎么做：你应该取右子节点还是再向上一层父节点？

以下技巧将对您有所帮助：

在向上移动之前，请记住当前节点。然后向上移动。现在您可以进行比较：您是否已经在左节点中？那么请取右节点。否则，请再向上移动一层父节点。

您只需要一个引用/指针即可。

- A.H.

Answer 4

有一种通用的方法可以通过使用惰性迭代器将递归遍历转换为迭代器，该迭代器连接多个迭代器供应商（返回迭代器的lambda表达式）。请参见我的将递归遍历转换为迭代器。

- Dagang