链式非递归 先中后序遍历树的实现

#pragma warning(disable : 4996)
#include 
#include 
#define MAXSIZE 100
//初始化叉树
typedef char Telemtype;
typedef struct Bnode
{
    Telemtype data;
    struct Bnode* lchild, * rchild;
    int flag;
}Bnode, * Btree;

typedef struct Linknode
{
    Bnode data;  //数据域
    struct Linknode* next; //指针域
} LinkStNode, * LiStack;


//建立二叉树(不带参数)
Btree createBtree()
{
    Btree T;
    char ch;
    T = (Bnode*)malloc(sizeof(Bnode));
    scanf("%c", &ch);
    if (ch == '*')
        T = NULL;
    else
    {
        if (!T)
            exit(1);
        T->data = ch; //建立根结点
        T->lchild = createBtree();//建立左孩子
        T->rchild = createBtree();//建立右孩子  
    }
    return T;
}

void InitStrack(LiStack* s)
{
    (*s) = (LiStack)malloc(sizeof(LinkStNode));
    (*s)->next = NULL;
}

int StackEmpty(LiStack s)
{
    return(s->next == NULL);//为空返回1，不为空返回0
}

void Push(LiStack s, Bnode e)
{
    LiStack p;
    p = (LiStack)malloc(sizeof(LinkStNode));

    if (s->next == NULL) {  // 判断栈空
     // 先创建第一个结点
        p->data = e;
        p->next = NULL;     // 后继指向空
        s->next = p;
    }
    else {  // 后续结点都是在头结点和第一个结点之间插入
        p->next = s->next;  // p指向头指针原后继
        p->data = e;        // 存入数据
        s->next = p;        // 头指针后继指向p
    }
}

int Pop(LinkStNode* s, Bnode* e)
{
    LiStack p;
    if (s->next == NULL || s->next == NULL)  //栈空的情况
        return 0;
    p = s->next;   //p指向开始结点
    *e = p->data;
    s->next = p->next;  //删除*p结点
    free(p);   //释放*p结点
    return 1;
}
void PreOrder(Btree bt)
{

    //创建栈；
    LiStack L;
    //初始化栈
    InitStrack(&L);

    Btree p;
    Bnode e, el, er;//取顶元素，取左元素，取右元素 
    e = *bt;
    Push(L, e);
    //非递归前序遍历；
    while (!StackEmpty(L))
    {
        Pop(L, &e);
        p = &e;
        printf("%c ", p->data);    //栈的特点，先进后出；
        if (p->rchild)
        {
            er = *(p->rchild);
            Push(L, er);
        }

        if (p->lchild)
        {
            el = *(p->lchild);
            Push(L, el);
        }
    }

}

void InOrder(Btree bt)//左根右 
{

    //创建栈；
    LiStack L;
    //初始化栈
    InitStrack(&L);

    Btree p;
    Bnode e, el, er;//取顶元素，取左元素，取右元素 
    p = bt;
    //非递归中序遍历；
    while (p != NULL || !StackEmpty(L))
    {
        if (p)
        {
            e = *p;
            Push(L, e);
            p = p->lchild;
        }
        else
        {
            Pop(L, &e);
            p = &e;
            printf("%c ", p->data);
            p = p->rchild;
        }
    }
}

void PostOrder(Btree bt)
{
    //创建栈；
    LiStack L;
    //初始化栈
    InitStrack(&L);

    Btree p;
    Bnode e, el, er;//取顶元素，取左元素，取右元素 
    p = bt;
    //非递归后序遍历；
    while (p != NULL || !StackEmpty(L))
    {
        if (p)
        {
            p->flag = 0;
            e = *p;
            Push(L, e);
            p = p->lchild;
        }
        else
        {
            Pop(L, &e);
            p = &e;
            if (p->flag == 0)
            {
                p->flag = 1;
                e = *p;
                Push(L, e);
                p = p->rchild;
            }
            else
            {
                printf("%c ", p->data);
                p = NULL;
            }
            
            
        }
    }
}
int main()
{
    Btree T;

    T = createBtree();
    PreOrder(T);
    printf("n");
    InOrder(T);
    printf("n");
    PostOrder(T);
    return 0;
}