C语言非递归遍历二叉树（破坏树结构的方式）

#include <stdio.h>
#include <stdlib.h>
typedef char treetype;     //二叉树节点数据类型

typedef struct BitNode     //二叉树结构体
{
    treetype data;
    struct BiNode *left;
    struct BitNode *right;
}BitNode,*BitTree;
typedef BitTree stacktype;     //栈节点数据类型

typedef struct node        //栈节点数据结构
{
    stacktype data;
    struct node *next;
}Node,*PNode;

typedef struct stack      //栈的结构
{
    Node *top;
    Node *base;
}Stack,*PStack;

void InitStack(PStack S)   //初始化栈，参数为一级指针，对该地址的内容进行操作，初始化的栈一定是top指针和base指向一个生成的空节点。
{
    PNode initnode=(PNode)malloc(sizeof(Node));
    S->base=initnode;
    S->top=initnode;
    initnode->next=NULL;
    printf("栈创建成功\n");
}

void push(PStack S,stacktype c)
{
    PNode newnode=(PNode)malloc(sizeof(Node));
    if(newnode==NULL)
    {
        return ;
    }
    else
    {
        S->top->data=c;
        newnode->next=S->top;
        S->top=newnode;

    }
}

void createBitTree(BitTree *T)
{
    treetype c;
    scanf("%c",&c);
    if(c=='#')
        return ;
    else
    {
        *T=(BitTree)malloc(sizeof(BitNode));
        (*T)->data=c;
        (*T)->left=NULL;
        (*T)->right=NULL;
        printf("节点创建成功\n");
        createBitTree(&((*T)->left));
        createBitTree(&((*T)->right));
    }
}

void first(BitTree T)    //先序递归遍历
{
        printf("%c\n",T->data);
        if(T->left!=NULL)
            first(T->left);
        if(T->right!=NULL)
            first(T->right);
}
int IsEmpty(PStack S)   //判断是否为空栈，是则返回1，不是则返回0
{
    if(S->base==S->top)
        return 1;
    else return 0;
}

stacktype pop(PStack S)
{
    if(S->base!=S->top)
    {
        PNode p=S->top;
        S->top=S->top->next;
        stacktype c=S->top->data;
        free(p);
        p=NULL;
        return (c);
    }
}

void firstNocircul(BitTree T)   //先序非递归,此方法没有破坏树结构
{
    Stack S;
    InitStack(&S);
    push(&S,T);
    while(IsEmpty(&S)!=1)
    {
        stacktype a=pop(&S);
        printf("%c",a->data);
        if(a->right!=NULL)
            push(&S,a->right);
        if(a->left!=NULL)
            push(&S,a->left);
    }
}

void midNocircle(BitTree T)    //中序非递归遍历，此方法破坏了树结构
{
    Stack S;
    InitStack(&S);
    push(&S,T);
    while(IsEmpty(&S)!=1)
    {
        stacktype a=pop(&S);
        if(a->left==NULL&&a->right==NULL)                                //五左右子树
        {
            printf("%c",a->data);
        }
        if(a->left!=NULL&&a->right!=NULL)  //有左右子树
        {
            push(&S,a->right);
            push(&S,a);
            push(&S,a->left);
            a->left=NULL;
            a->right=NULL;
        }
        if(a->left!=NULL&&a->right==NULL)  //有左子树，无右子树
        {
            push(&S,a);
            push(&S,a->left);
            a->left=NULL;
        }
        if(a->left==NULL&&a->right!=NULL)   //无左子树，有右子树
        {
            push(&S,a->right);
            push(&S,a);
            a->right=NULL;
        }
    }
}

void lastNocircle(BitTree T)         //后序非递归遍历二叉树，此方法破坏了树结构
{
    Stack S;
    InitStack(&S);
    push(&S,T);
    while(IsEmpty(&S)!=1)
    {
        stacktype a=pop(&S);
        if(a->left==NULL&&a->right==NULL)    //无左右子树，这个函数必须放在下面三个函数之前
        {
            printf("%c",a->data);Stack S;
    InitStack(&S);
        }
        if(a->left!=NULL&&a->right!=NULL)    //有左右子树
        {
            push(&S,a);
            push(&S,a->right);
            push(&S,a->left);
            a->left=NULL;
            a->right=NULL;
        }
        if(a->left!=NULL&&a->right==NULL)    //有左子树，无右子树
        {
            push(&S,a);
            push(&S,a->left);
            a->left=NULL;
        }
        if(a->left==NULL&&a->right!=NULL)    //无左子树，有右子树
        {
            push(&S,a);
            push(&S,a->right);
            a->right=NULL;
        }
    }
}
int main()
{
    BitTree T;
    createBitTree(&T);IsEmpty(&S)!=1
    printf("先序非递归遍历的结果是：");
    firstNocircul(T); printf("\n");
    printf("中序非递归遍历的结果是：");
    midNocircle(T);printf("\n");
    printf("后序非递归遍历的结果是：");
  //  lastNocircle(T);printf("\n");

}