非递归访问二叉树

递归算法非常的简单。先访问跟节点，然后访问左节点，再访问右节点。如果不用递归，那该怎么做呢？仔细看一下递归程序，就会发现，其实每次都是走树的左分支(left)，直到左子树为空，然后开始从递归的最深处返回，然后开始恢复递归现场，访问右子树。

其实过程很简单：一直往左走 root->left->left->left...->null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。有两个办法：
1.用栈记忆：在访问途中将依次遇到的节点保存下来。由于节点出现次序与恢复次序是反序的，因此是一个先进后出结构，需要用栈。

#include
#include
#include
using namespace std;
typedef int datatype;
typedef struct node
{
    datatype data;
    struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;

    void createbintree(bintree *t)
    {
    //输入二叉树的先序遍历序列，创建二叉链表
        int ch;
        //ch=getchar();
        scanf("%d",&ch);
        if(ch==-1)
            *t=NULL;//如果读入空格字符，创建空树，T是指向指针的指针,*t就相当于一个bintree指针，专门指向bintnode；
        else
        {
            (*t)=(bintnode*)malloc(sizeof(bintnode));
            (*t)->data=ch;
            createbintree(&(*t)->lchild);//根据先序遍历，继续创建左子树，让客户端继续输入
            createbintree(&(*t)->rchild);//创建完左子树，继续创建右子树
        } //递归调用，自动返回
    }
    void preorder(bintree t)
    {
        if(t)
        {
            printf("%d ",t->data);//先访问根结点，再遍历左子树，跟着右子树
            preorder(t->lchild);
            preorder(t->rchild);
        }

    }

    void non_preorder(bintree t)
    {
        stackst;
        while(t!=NULL || !st.empty())
        {
            if(t!=NULL)
            {
                printf("%d ",t->data);//先访问根结点
                st.push(t);
                t=t->lchild;//只要左子树不空，一直遍历
            }
            else
            {
                t=st.top();//左子树访问完了，准备访问父结点的右子树
                st.pop();
                t=t->rchild;//访问右子树
            }
        }

    }
    //我的版本，也不错
    void nonpreorder(bintree t)
    {
        stackst;
        if(t)
            st.push(t);
        while(!st.empty())
        {
            bintree bt=st.top();
            printf("%d ",bt->data);//父结点先访问
            st.pop();
            bintree lbt=bt->lchild;
            bintree rbt=bt->rchild;
            if(rbt)
                st.push(rbt);//右子树进栈
            while(lbt)//先序遍历左子树
            {
                printf("%d ",lbt->data);
                rbt=lbt->rchild;
                if(rbt)
                    st.push(rbt);//右子树进栈
                lbt=lbt->lchild;
            }
        }
    }

int main()
{

/*
这里的输入要严格按照正确的顺序才能结束.这里要用到二叉树的一个性质,
就是说对于有n个节点的二叉树,就有n+1个空域,在这里即为如果你输入了n个
元素,那么一定要有n+1个#才会结束迭代过程.
*/
    bintree t=NULL;
    createbintree(&t);//这样才能改变T，指向指针的指针
    printf("前序遍历:       ");
    preorder(t);
    printf("\n非递归前序遍历: ");
    nonpreorder(t);
    printf("\n非递归前序遍历: ");
    non_preorder(t);
    printf("\n");
    getchar();
    return 0;
}

/*
1 2 4 8 -1 -1 9 -1 -1 5 10 -1 -1 11 -1 -1 3 6 -1 -1 7 -1 -1
前序遍历:       1 2 4 8 9 5 10 11 3 6 7
非递归前序遍历: 1 2 4 8 9 5 10 11 3 6 7
非递归前序遍历: 1 2 4 8 9 5 10 11 3 6 7
Press any key to continue
*/

先序是先访问，再入栈；而中序则是先入栈，弹栈后再访问。

#include
#include
#include
using namespace std;
typedef int datatype;
typedef struct node
{
    datatype data;
    struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;

    void createbintree(bintree *t)
    {
    //输入二叉树的先序遍历序列，创建二叉链表
        int ch;
        //ch=getchar();
        scanf("%d",&ch);
        if(ch==-1)
            *t=NULL;//如果读入空格字符，创建空树，T是指向指针的指针,*t就相当于一个bintree指针，专门指向bintnode；
        else
        {
            (*t)=(bintnode*)malloc(sizeof(bintnode));
            (*t)->data=ch;
            createbintree(&(*t)->lchild);//根据先序遍历，继续创建左子树，让客户端继续输入
            createbintree(&(*t)->rchild);//创建完左子树，继续创建右子树
        } //递归调用，自动返回
    }


    void non_inorder(bintree t)
    {
        stackst;
        while(t!=NULL || !st.empty())//只要没有访问到尽头和栈里还有结点
        {
            if(t!=NULL)
            {
                //printf("%d ",t->data);第一次没有访问，而是保存根结点
                st.push(t);
                t=t->lchild;//最后栈顶保持的肯定是最后一个左子树的结点
            }
            else
            {
                t=st.top();//指向最后一个左子树结点
                printf("%d ",t->data);//访问左子树,
                st.pop();//相当于中间访问根结点
                t=t->rchild;//通过下一次循环实现右子树遍历
            }
        }

    }

    void inorder(bintree t)
    {
        if(t)
        {
            inorder(t->lchild);
            printf("%d ",t->data);//
            inorder(t->rchild);
        }
    }
int main()
{

/*
这里的输入要严格按照正确的顺序才能结束.这里要用到二叉树的一个性质,
就是说对于有n个节点的二叉树,就有n+1个空域,在这里即为如果你输入了n个
元素,那么一定要有n+1个#才会结束迭代过程.
*/
    bintree t=NULL;
    createbintree(&t);//这样才能改变T，指向指针的指针
    printf("\n非递归中序遍历: ");
    inorder(t);
    printf("\n非递归中序遍历: ");
    non_inorder(t);
    printf("\n");
    getchar();
    return 0;
}

/*
1 2 4 8 -1 -1 9 -1 -1 5 10 -1 -1 11 -1 -1 3 6 -1 -1 7 -1 -1

非递归中序遍历: 8 4 9 2 10 5 11 1 6 3 7
非递归中序遍历: 8 4 9 2 10 5 11 1 6 3 7

Press any key to continue
*/

3.后序遍历---加多个标志位

从直觉上来说，后序遍历对比中序遍历难度要增大很多。因为中序遍历节点序列有一点的连续性，而后续遍历则感觉有一定的跳跃性。先左，再右，最后才中间节点；访问左子树后，需要跳转到右子树，右子树访问完毕了再回溯至根节点并访问之。这种序列的不连续造成实现前面先序与中序类似的第1个与第3个版本比较困难。但是按照第2个思想，直接来模拟递归还是非常容易的。如下：

1. // 后序遍历伪代码：非递归版本，用栈实现
2. void PostOrder(TNode* root)
3. {
4.     Stack S;
5.     if( root != NULL )
6.     {
7.         S.push(root);
8.     }
9.     while ( !S.empty() )
10.     {
11.         TNode* node = S.pop(); 
12.         if ( node->bPushed )
13.         {   // 如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了
14.             Visit(node);        
15.         }
16.         else
17.         {   // 左右子树尚未入栈，则依次将 右节点,左节点,根节点 入栈
18.             if ( node->right != NULL )
19.             {
20.                 node->right->bPushed = false; // 左右子树均设置为false
21.                 S.push(node->right);
22.             }
23.             if ( node->left != NULL )
24.             {
25.                 node->left->bPushed = false;
26.                 S.push(node->left);
27.             }
28.             node->bPushed = true;            // 根节点标志位为true
29.             S.push(node);
30.         }
31.     }
32. }