二叉链表遍历

#include<bits/stdc++.h>
#include<stack>
#include<queue>

using namespace std;

#define Elemtype char

typedef struct Bitnode{
    Elemtype data;
    struct Bitnode *lchild;
    struct Bitnode *rchild;
}Bitnode,*Bitree;

void CreateTree(Bitree &T){
    Elemtype x;
    cin>>x;
    if(x=='*'){
        T=NULL;
    }else{
        T=(Bitree)malloc(sizeof(Bitnode));
        T->data=x;
        CreateTree(T->lchild);
        CreateTree(T->rchild);
    }
}

void PreOrder(Bitree T){
    if(T==NULL){
        return;
    }else{
        cout<<T->data;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void NC_PreOrder(Bitree T){
    stack<Bitree> s;
    s.push(T);
    Bitree p;
    while(!s.empty()){
        while(s.top()){
            p=s.top();
            cout<<p->data;
            s.push(p->lchild);
        }
        s.pop();
        if(!s.empty()){
            p=s.top();
            s.pop();
            s.push(p->rchild);
        }
    }
}



void InOrder(Bitree T){
    if(T==NULL){
        return;
    }else{
        InOrder(T->lchild);
        cout<<T->data;
        InOrder(T->rchild);
    }
}

void NC_InOrder(Bitree T){
    stack<Bitree> s;
    s.push(T);
    while(!s.empty()){
        while(s.top()){
            s.push(s.top()->lchild);
        }
        s.pop();
        if(!s.empty()){
            Bitree t=s.top();
            s.pop();
            cout<<t->data;
            s.push(t->rchild);
        }
    }
}

void PostOrder(Bitree T){
    if(T==NULL){
        return;
    }else{
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout<<T->data;
    }
}

void NC_PostOrder(Bitree T){
    stack<Bitree> s;
    Bitree p=T,r=NULL;
    while(p!=NULL||!s.empty()){
        if(p!=NULL){
            s.push(p);
            p=p->lchild;
        }else{
            p=s.top();
            if(p->rchild&&p->rchild!=r){
                p=p->rchild;
                s.push(p);
                p=p->lchild;
            }else{
                s.pop();
                cout<<p->data;
                r=p;
                p=NULL;
            }
        }
    }

}

int main(){
    Bitree S;
    cout<<"按先序创建二叉树：";
    CreateTree(S);

    cout<<"先序遍历为："<<endl;
    cout<<"非递归遍历：";
    PreOrder(S);
    cout<<endl;
    cout<<"递归遍历：  ";
    NC_PreOrder(S);
    cout<<endl;


    cout<<"中序遍历为："<<endl;
    cout<<"非递归遍历：";
    InOrder(S);
    cout<<endl;
    cout<<"递归遍历：  ";
    NC_InOrder(S);
    cout<<endl;

    cout<<"后序遍历为："<<endl;
    cout<<"非递归遍历：";
    PostOrder(S);
    cout<<endl;
    cout<<"递归遍历：  ";
    NC_PostOrder(S);
    cout<<endl;
    return 0;
}