二叉树的基本操作(非递归(先序中序遍历))

#include
#include
#include

#define MAXSIZE 100

typedef struct BiTNode
{
        int data;
        struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef BiTree DataType;

typedef struct stack
{
        DataType data[MAXSIZE];
        int top;
}Stack;

void StackInit(Stack *S)
{
        S->top=-1;
}

int StackEmpty(Stack *S)
{
        return S->top==-1;
}

int StackFull(Stack *S)
{
        return S->top==MAXSIZE-1;
}

void push(Stack *S, DataType value)
{
        if(StackFull(S))
        {
                printf("Stack is full!\n");
                exit(-1);
        }
        S->data[++S->top]=value;
}

void pop(Stack *S)
{
        if(StackEmpty(S))
        {
                printf("Stack is empty!\n");
                exit(-1);
        }
        S->top--;
}

DataType top(Stack *S)
{
        if(StackEmpty(S))
        {
                printf("Stack is empty!\n");
                exit(-1);
        }
        return S->data[S->top];
}

void CreateBiTree(BiTree *T)
{
        int ch;
        scanf("%d",&ch);
        if(ch==-1)
        {
                *T=NULL;
        }
        else
        {
                *T=(BiTree)malloc(sizeof(BiTNode));
                if(!(*T))
                        printf("memory alloc error");
                (*T)->data=ch;
                CreateBiTree(&((*T)->lchild));
                CreateBiTree(&((*T)->rchild));
        }
}


void PreOrderTraverse(BiTree T)
{
        BiTree p=T;
        Stack *s;
        StackInit(s);

        while(p!=NULL||!StackEmpty(s))
        {
                while(p!=NULL)
                {
                        printf("%3d",p->data);
                        push(s,p);
                        p=p->lchild;
                }
                if(!StackEmpty(s))
                {
                        p=top(s);
                        pop(s);
                        p=p->rchild;
                }
        }
｝

void InOrderTraverse(BiTree T)
{
        BiTree p=T;
        Stack *s;
        StackInit(s);

        while(p!=NULL||!StackEmpty(s))
        {
                while(p!=NULL)
                {
                        push(s,p);
                        p=p->lchild;
                }
                if(!StackEmpty(s))
                {
                        p=top(s);
                        pop(s);
                        printf("%3d",p->data);
                        p=p->rchild;
                }
        }
}

int main(void)
{
        BiTree T;
        printf("请输入创建一棵二叉树的先序序列:\n");
        CreateBiTree(&T);
        printf("先序序列为:");
        PreOrderTraverse(T);
        printf("\n");
        printf("中序序列为:");
        InOrderTraverse(T);
        printf("\n");
      
        return 0;
}