学步园

假设给定一颗树节点的结构：
struct node {
    int data;
    struct node *left;
    struct node *right;
}
typedef strcut node *tree

叫你写出递归遍历树结构的代码，其实很简单
中序遍历如下：

void traverse(tree T, (*visit)(int))
{
    if (!T)
    {
        traverse(T->left,visit);
        (*visit)(T->data);
        traverse(T->right,visit);
    }
}

如果非要叫你写非递归遍历的话，那就要费点脑子了
想一下，写这个非递归遍历最重要的是理解递归过程中发生了什么，并尝试用迭代的方式去模拟整个过程。

#include<stack>
using namespace std;

void inorder_traverse(tree T, void (*visit)(int))
{
    tree p = T;
    stack<node*> S;
    while (p || !S.empty())
    {
        while(P)
        {
            S.push(p);
            p = p->left;
        }
        p = S.pop();
        (*visit)(p->data);
        p = p->right;
    }
}

为什么非要写个非递归呢？

原来我以为是非递归可以避免递归调用带来的时空消耗，但始终觉得这个理由很牵强。

今天找到了个更具有说服力的原因。树形结构一般可以用来实现容器类，于是我们需要生成一个迭代器以遍历整个容器，

所以我们必须使用非递归的算法，在每次调用next之后返回一个元素，同时使指针指向下一个元素。