C语言二叉树（先中后序遍历、层序遍历、非递归先中后序遍历）-蒲公英云

C语言二叉树（先中后序遍历、层序遍历、非递归先中后序遍历）

欢迎大家交流指正

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE_QUEUE 1000
#define MAXSIZE_STACK 1000
typedef char TElemType;
typedef int Statistics;
//树的结构体
typedef struct BitNode 
{
    TElemType data;
    Statistics count;  //非递归后续遍历使用,用于统计次数
    struct BitNode *lchlid,*rchlid;
}BitNode;
//队列结构体
typedef struct
{
    BitNode **base;
    int front,rear;
}Queue;
//栈
typedef struct
{
    BitNode **base;
    int top;
}Stack;
//初始化队列
void InitQueue(Queue *T)
{
    T->base=(BitNode **)malloc(sizeof(BitNode *)*MAXSIZE_QUEUE);
    if(!T->base) exit(0);
    T->front=T->rear=0;
}
//初始化栈
void InitStack(Stack *L)
{
    L->base=(BitNode **)malloc(sizeof(BitNode *)*MAXSIZE_STACK);
    if(!L->base) exit(0);
    L->top=0;
}
//入栈
void Pushstack(BitNode *T,Stack *L)
{
    L->base[L->top++]=T;
}
//出栈
BitNode* Popstack(Stack *L)
{
    return L->base[--L->top];
}
//入队
void Push(Queue *Q,BitNode *T)
{
    Q->base[Q->rear++]=T;
}
//出队
BitNode* Pop(Queue *Q)
{
    return (Q->base[Q->front++]);
}
//先序遍历法创建树
void Creat_tree(BitNode **T)
{
    char x;
    scanf("%c",&x);
    if(x=='#')*T=NULL;
    else
    {
        *T=(BitNode *)malloc(sizeof(BitNode));
        if(T==NULL) exit(-2);
        (*T)->data=x;
        Creat_tree(&(*T)->lchlid);
        Creat_tree(&(*T)->rchlid);
    }
}
/***********************
  先序遍历
***********************/
void Print1(BitNode *T)
{
    if(T!=NULL)
    {
        printf("%c",T->data);
        Print1(T->lchlid);
        Print1(T->rchlid);
    }
}
/***********************
  中序遍历
***********************/
void Print2(BitNode *T)
{
    if(T!=NULL)
    {
        Print2(T->lchlid);
        printf("%c",T->data);
        Print2(T->rchlid);
    }
}
/***********************
  后序遍历
***********************/
void Print3(BitNode *T)
{
    if(T!=NULL)
    {
        Print3(T->lchlid);
        Print3(T->rchlid);
        printf("%c",T->data);
    }
}
/***********************
  层序遍历
***********************/
void Print4(BitNode *T)
{
    Queue Q;
    InitQueue(&Q);
    Push(&Q,T);
    while(Q.front!=Q.rear)
    {
        printf("%c",Q.base[Q.front]->data);
        T=Pop(&Q);    
        if(T->lchlid!=NULL)Push(&Q,T->lchlid);
        if(T->rchlid!=NULL)Push(&Q,T->rchlid);
    }
}
/***********************
  非递归的先序遍历
***********************/
void Print5(BitNode *T)
{
    Stack L;
    InitStack(&L);
    while(T!=NULL || L.top!=0)
    {
        while(T!=NULL)
        {
          printf("%c",T->data);
          Pushstack(T,&L);
          T=T->lchlid;
        }
        if(L.top!=0)
        {
            T=Popstack(&L);
            T=T->rchlid;
        }
    }
}
/***********************
  非递归的中序遍历
***********************/
void Print6(BitNode *T)
{
    Stack L;
    InitStack(&L);
    while(T!=NULL || L.top!=0)
    {
        while(T!=NULL)
        {
          Pushstack(T,&L);
          T=T->lchlid;
        }
        if(L.top!=0)
        {
            T=Popstack(&L);
            printf("%c",T->data);
            T=T->rchlid;
        }
    }
}
/***********************
  非递归的后序遍历
***********************/
void Print7(BitNode *T)
{
    Stack L;
    InitStack(&L);
    while(T!=NULL || L.top!=0)
    {
        while(T!=NULL)
        {
            T->count=1;
            Pushstack(T,&L);
            T=T->lchlid;
        }
        if(L.top!=0)
        {
            T=Popstack(&L);
            if(T->count == 1)
            {
                T->count++;
                Pushstack(T,&L);
                T=T->rchlid;
            }
            else if(T->count == 2)
            {
                printf("%c",T->data);
                T=NULL;
            }
        }
    }
}
void main()
{
    struct BitNode *T;
    printf("空以'#'号代替，如AB##CD##E##\n请输入二叉树:");
    Creat_tree(&T);
    printf("先序遍历:");
    Print1(T);
    printf("\n中序遍历:");
    Print2(T);
    printf("\n后序遍历:");
    Print3(T);
    printf("\n层序遍历:");
    Print4(T);
    printf("\n非递归先序遍历:");
    Print5(T);
    printf("\n非递归中序遍历:");
    Print6(T);
    printf("\n非递归后序遍历:");
    Print7(T);
    printf("\n");
}