4

我被要求写迭代版本，但我写的是递归版本，即

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;
}
4

4 回答 4

4

您看到的问题是您需要“记住”您最后一次迭代的地方。
进行递归时，程序在内部使用“堆栈”来记住要返回的位置。
但是在进行迭代时，它不会。

虽然……这给你一个想法吗？

于 2011-09-25T19:42:25.500 回答
0

我想不出一种非常优雅的方式来迭代地做这件事。

一种可能性可能是使用“标记算法”，您从所有节点开始“未标记”和“标记”节点，因为它们被处理。标记可以添加到对象模型中或保存在单独的实体中。

伪代码：

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
于 2011-09-25T19:55:54.450 回答
0

我认为这是理所当然的，从父节点向下迭代到左节点不是问题。问题是知道从一个节点上升到父节点时要做什么：你应该选择正确的子节点还是应该再上升一个父节点？

以下技巧将帮助您：

在向上之前记住当前节点。然后往上走。现在可以比较一下： 有没有在左边节点： 那么取右边节点。否则再上一个父节点。

为此，您只需要一个参考/指针。

于 2011-09-25T20:38:28.147 回答
0

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

于 2017-11-13T19:46:54.883 回答