非递归遍历树

//非递归遍历二×树
#include<iostream>
using namespace std;
//二叉链存储
typedef struct BiNode{
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

//链栈
typedef struct StackNode{
    BiTNode data;
    struct StackNode *next;
}StackNode,*LinkStack;

void CreatBiTree(BiTree &T){
    char ch;
    cin>>ch;
    if(ch=='#') T==NULL;
    else{
        T=new BiTNode;
        T->data=ch;
        CreatBiTree(T->lchild);
        CreatBiTree(T->rchild);
    }
}

void InitStack(LinkStack &S)
{
    //构造一个空栈S，栈顶指针置空
    S=NULL;
}

void StackEmpty(LinkStack S){
    if(!S){
        return true;
    }else{
        return false;
    }
}

void Push(LinkStack &S,BiTree e){
    StackNode *p=new StackNode;
    p->data=*e;
    p->next=S;
    S=p;
}

void pop(LinkStack &S BiTree e){
    if(S!=NULL){
        *e=S->data;
        StackNode *p=S;
        S=S->next;
        delete p;
    }
}
//中序
void InOderTraversel1(BiTree T){
    LinkStack S;BiTree p;
    BiTree q=new BiTNode;
    InitStack(S); p=T;
    while(p||!StackEmpty(S)){
        if(p){
            push(S,p);
            p->lchild;
        }else{
            pop(S,p);
            cout<<q->data;
            p=q->rchild;
        }
    }
}

void main(){
    BiTree tree;
    cout<<"please input\n";
    CreatBiTree(tree);
    cout<<"result:\n";
    InOderTraversel1(tree);
    cout<<endl;
}

非递归遍历树

原文：https://www.cnblogs.com/ygjzs/p/11874577.html