中序遍历的非递归算法

1..中序遍历的非递归算法算法思想 --->利用栈来代替递归遍历

1.初始时依次扫描根节点及根节点的左侧结点,并将一一入栈,如果结点不存在,结束入栈
2.(当结点不存在时),出栈一个结点,访问它(可以是输出结点的数据域的值)
3.扫描该结点的右孩子结点,并将其入栈
4.依次扫描该右孩子的所有左侧结点,并将一一入栈
5.反复该过程,直到栈为空为止.

 2.代码实现c/c++

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define MaxSize 50
using namespace std;
typedef char ElemType;
//树结点定义
typedef struct node{
    ElemType data;
    struct node* lchild,*rchild;
}BiTNode,*BiTree;
//栈结点定义
typedef BiTree DataType;
typedef struct node1{
    DataType data[MaxSize];  //存放栈中的数据
    int top;  //存放栈顶指针
}SqStack;
//初始化一个空的二叉树
void InitBiTree(BiTree &tree)
{
    // tree存储NULL,表示没有二叉树
    tree=NULL;
}
//创建二叉树  #表示空结点
void CreateBitree(BiTree &T)
{
    char ch;
    if((ch=getchar())=='#')
        T=NULL;
    else
    {
        T=(BiTNode*)malloc(sizeof(BiTNode));
        T->data=ch;
        CreateBitree(T->lchild);
        CreateBitree(T->rchild);
    }
}

//初始一个空栈
void InitStack(SqStack &S){
    S.top=-1;   //初始时，栈顶指针指向-1
}
//判断栈是否为空
bool StackEmpty(SqStack &S){
    if(S.top==-1)
        return true;   //栈空
    else{
        return false;  //不空
    }

}
//入栈，要判断栈是不是满了
bool Push(SqStack &S,DataType x){
    if(S.top==MaxSize-1){
        cout<<"栈满了!无法入栈"<<endl;
        return false;
    }
    S.data[++S.top]=x;
    return true;
}
//出栈，判断是不是在栈空
bool Pop(SqStack &S,DataType &x){
    if(S.top==-1){
        cout<<"顺序栈为空!，无法出栈"<<endl;
        return false;
    }
    x=S.data[S.top--];
    return true;
}
//读出栈顶元素
bool GetTop(SqStack &S,DataType &x){
    if(S.top==-1){
        cout<<"顺序栈为空!无法读出"<<endl;
        return false;
    }
    x=S.data[S.top];
    return true;
}
//销毁顺序栈
void DestoryStack(SqStack &S){
    S.top==-1;
}
//将中序递归遍历转为非递归算法
void InOrder2(BiTree &tree,SqStack &S)
{
    InitStack(S);BiTree p =tree;
    while(p||!StackEmpty(S))
    {
        if(p)
        {
            Push(S,p);  //入栈
            p=p->lchild;
        }
        else{
            Pop(S,p);printf("%c",p->data);//访问结点
            p=p->rchild;
        }
    }
}

int main(){
    BiTree tree;
    SqStack S;
    InitBiTree(tree);
    CreateBitree(tree);
    InOrder2(tree,S);
    return 0;
}