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

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

Answer 1

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

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