将递归二叉树遍历转换为迭代 [英] Convert recursive binary tree traversal to iterative

问题描述

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

I was asked to write the iterative version, but I wrote the recursive version i.e.

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

我不是在找代码，我想要了解如何做到这一点。如果它只是最后一次递归调用，我会做的

I'm not looking for the code, I want to understand how this can be done. Had it been just the last recursive call, I would have done

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;

这就是我想到的，我是在正确的轨道上吗？

This is what I thought of, am I on the right track?

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

推荐答案

你看到的问题是你需要记住你正在迭代的最后一个地方。

在进行递归时，程序在内部使用堆栈来记住返回的位置。

但在进行迭代时却没有。

The problem you're seeing is that you need to "remember" the last place you were iterating at.
When doing recursion, the program internally uses "the stack" to remember where to go back to.
But when doing iteration, it doesn't.

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

Although... does that give you an idea?

这篇关于将递归二叉树遍历转换为迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！