请教各位有关二叉树的问题!!

ccwei

/*此程序主要是训练二叉树的生成,遍历（输出），包括用栈和
不用栈，另外借助层次遍历方法交换左右子树，但目前用栈还末
实现！初步判断是：栈有关的问题！现象是：一下子给栈用满
了！(在TC下调试)*/
#define OVERFLOW  -2
#define INFEASIBLE -1
#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
typedef int Status;
#include "stdio.h"
#define Stack_INIT_S 30
#define MaxNode 30
typedef char TElemType;
typedef struct BiTNode{
        TElemType data;
        struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct Stack{
        BiTree base;
        BiTree top;
        int stacksize;
}SqStack;
FILE *fp;
Status (*Visit)();
Status PrintElement(TElemType e);
Status CreateBiTree(BiTree *T);
Status InOrderTraverse_1(BiTree T);
Status LevelOrder(BiTree T);
Status LevelOrderSwap(BiTree T);

void main(void)
{
        BiTree T=NULL;
        clrscr();
        if ((fp=fopen("d:\\chen\\dataBT.txt","r")==NULL)
        {
                puts("Can not open the data file!";
                exit(ERROR);
        }
        /* 运行是注意在“d:\chen\dataBT.txt”中有数据如下：
        abdhn**o**ip***ejq***k**cf**glr**s**mt***
        */
        CreateBiTree(&T);
        fclose(fp);
        puts("LevelOrderTraverse";
        LevelOrder(T);
        puts(" \nAfter Swaping (shell LevelOrderSwap() )!";
        LevelOrderSwap(T);/*用层次遍历来实施交换！*/
        LevelOrder(T);        putchar('\n');
        /*以下是有错误的函数(InOrderTraverse_2(T)和InOrderTraverse_1(T)
        调用不成功！错误何在呀？)*/
/*        puts("InOrderTraverse_2(with Stack ):";
        InOrderTraverse_2(T);        putchar('\n');
*/        puts("InOrderTraverse_1(with Stack ):";
        InOrderTraverse_1(T);        putchar('\n');
        puts("\nThe end";        getch();
}
Status LevelOrder(BiTree T)
/*层次遍历二叉树，借助了队列！*/
{
        BiTree queue[MaxNode];
        int front,rear;
        Visit=PrintElement;
        if(T==NULL)
                return FALSE;
        front=-1;
        rear=0;
        queue[rear]=T;
        while(front!=rear)
        {
                front++;
                Visit(queue[front]->;data);
                if(queue[front]->;lchild!=NULL)
                {
                        rear++;
                        queue[rear]=queue[front]->;lchild;
                }
                if(queue[front]->;rchild!=NULL)
                {
                        rear++;
                        queue[rear]=queue[front]->;rchild;
                }
        }
        return OK;
}
Status LevelOrderSwap(BiTree T)
/*用层次遍历来实施交换！*/
{
        BiTree swapT, queue[MaxNode];
        int front,rear;
        if(T==NULL)
                return FALSE;
        front=-1;
        rear=0;
        queue[rear]=T;
        while(front!=rear)
        {
                front++;
                if(queue[front]->;lchild!=NULL)
                {
                        rear++;
                        queue[rear]=queue[front]->;lchild;
                }
                if(queue[front]->;rchild!=NULL)
                {
                        rear++;
                        queue[rear]=queue[front]->;rchild;
                }
                swapT=queue[front]->;lchild;
                queue[front]->;lchild=queue[front]->;rchild;
                queue[front]->;rchild=swapT;
        }
        return OK;
}

Status InitStack(SqStack *S)
{
        S->;base=(BiTree)malloc(Stack_INIT_S*sizeof(BiTNode));
        if(!S->;base)
        {
                printf("Overflow! in InintStack()!";
                exit(OVERFLOW);
        }
        S->;top=S->;base;
        S->;stacksize=Stack_INIT_S;
        return OK;
}
Status Push(SqStack *S,BiTree T)
{
        if(S->;top-S->;base >;S->;stacksize)
        {
                puts("Error for Stack Full in Push()!";
                exit(OVERFLOW);
        }
        *(S->;top)=*T;
        S->;top++;
        return OK;
}

Status Pop(SqStack *S,BiTree T)
{
        if(S->;top==S->;base)
        {
                puts("Error for Stack Emputy in Pop() !";
                exit(FALSE);
        }
        --S->;top;
        *T=*(S->;top);
        return OK;
}
Status GetTop(SqStack *S,BiTree *e)
{
        if(S->;top==S->;base)
                return ERROR;
        *e=S->;top-1;
        return  OK;
}

Status StackEmpty(SqStack S)
{
        if(S.base==S.top)
                return TRUE;
        else
                return FALSE;
}
Status StackFull(SqStack S)
{
        if(S.base+S.stacksize==S.top-1)
                return TRUE;
        else
                return FALSE;
}

Status PrintElement(TElemType e)
{
        printf("%3c",e);
        return OK;
}

/*按先序次序输入,递归调用实现生成二树！*/
Status CreateBiTree(BiTree *T)
{
        char ch;
        ch=fgetc(fp);
        if(ch=='*')
                *T=NULL;
        else
        {
                if(!(*T=(BiTNode*)malloc(sizeof(BiTNode))))
                {
                        puts("OverFlow!! in CreateBiTree()");
                        exit(OVERFLOW);
                }
                (*T)->;data=ch;
                CreateBiTree(&(*T)->;lchild);
                CreateBiTree(&(*T)->;rchild);
        }
        return OK;
}

/*用不递归方法但借助栈来实现中序遍历*/
Status InOrderTraverse_1(BiTree T)
{
        BiTree p=NULL;
        SqStack S;
        Visit=PrintElement;
        InitStack(&S);
        Push(&S,T);
        while(!StackEmpty(S))
        {
                while(GetTop(&S,&p)&& p)
                        Push(&S,p->;lchild);
                Pop(&S,p);
                if(!StackEmpty(S))
                {
                        Pop(&S,p);
                        if(!Visit(p->;data))
                                return ERROR;
                        Push(&S,p->;rchild);
                }
        }
        return OK;
}
/*此算法是另一种方法实现中序遍历*/
Status InOrderTraverse_2(BiTree T)
{
        BiTree p;
        SqStack *S=NULL;
        Visit=PrintElement;
        InitStack(S);
        p=T;
        while(p||!StackEmpty(*S))
        {
                if(p)
                {
                        Push(S,p);
                        p=p->;lchild;
                }
                else
                {
                        Pop(S,p);
                        Visit(p->;data);
                        p=p->;rchild;
                }
        }
        return OK;
}