tree.txt

构造二叉树的抽象数据类型 对于给定的先序序列和中序序列

#include <stdio.h>
#include <conio.h>
#define MAXLENGTH 1000
struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
};
struct SqQueue
{
    struct BiTNode *data[MAXLENGTH];
    int front;
    int rear;
};
void EnQueue(struct SqQueue *Q,struct BiTNode *e)     /*增加队列*/
{
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXLENGTH;
}
struct BiTNode *DeQueue(struct SqQueue *Q)            /*删除队列*/
{
    int now=Q->front;
    Q->front=(Q->front+1)%MAXLENGTH;
    return Q->data[now];
}
void FloorPrint(struct BiTNode *T)      /*按层输出此二叉树*/
{
    struct SqQueue *store;
    struct BiTNode *output;
    store=(struct SqQueue*)malloc(sizeof(struct SqQueue));
    store->front=store->rear=0;
    if(T!=NULL)
    {
        EnQueue(store,T);
        while(store->front!=store->rear)
        {
            int control=store->rear-store->front;
            int i;
            for(i=0;i<control;i++)
            {
                output=(struct BiTNode*)malloc(sizeof(struct BiTNode));
                output=DeQueue(store);
                printf("%c",output->data);
                if(output->lchild!=NULL)
                {   
                    EnQueue(store,output->lchild);
                }
                if(output->rchild!=NULL)
                {
                    EnQueue(store,output->rchild);
                }
            }
            printf("\n");
        }
    }
}
void FloorPrintTree(struct BiTNode *T)      /*按层输出此二叉树所表示的森林*/
{
    struct SqQueue *store;
    struct BiTNode *output;
    int level=1;
    store=(struct SqQueue*)malloc(sizeof(struct SqQueue));
    store->front=store->rear=0;
    if(T!=NULL)
    {
        EnQueue(store,T);
        while(T->rchild!=NULL)
        {
            T=T->rchild;
            EnQueue(store,T);
        }
        while(store->front!=store->rear)
        {
            int control=store->rear-store->front;
            int i;
            for(i=0;i<control;i++)
            {
                output=(struct BiTNode*)malloc(sizeof(struct BiTNode));
                output=DeQueue(store);
                printf("%c",output->data);
                if(output->lchild!=NULL)
                {
                    output=output->lchild;
                    EnQueue(store,output);
                    while(output->rchild!=NULL)
                    {
                        output=output->rchild;
                        EnQueue(store,output);
                    }
                }
            }
            printf("\n");
        }
    }
}
void createtree(struct BiTNode *T,int pre1,int pre2,int in1,int in2,char pre[],char in[])       /*按给定的先序序列和中序序列构造二叉树*/
{
    int control=0;
    int same;
    same=in1;
    if(pre[pre1]!=in[same])
    {
        while(pre[pre1]!=in[same])
        {
            same+=1;
            control+=1;
        }
    }
    if((control==0)&&(pre1==pre2))
    {
        T->data=pre[pre1];
        T->lchild=NULL;
        T->rchild=NULL;
    }
    if((control!=0)&&(control<(pre2-pre1)))
    {
        T->lchild=(struct BiTNode*)malloc(sizeof(struct BiTNode));
        T->rchild=(struct BiTNode*)malloc(sizeof(struct BiTNode));
        T->data=pre[pre1];
        createtree(T->lchild,pre1+1,pre1+control,in1,in1+control-1,pre,in);
        createtree(T->rchild,pre1+control+1,pre2,in1+control+1,in2,pre,in);
    }
    if((control!=0)&&(control==pre2-pre1))
    {
        T->lchild=(struct BiTNode*)malloc(sizeof(struct BiTNode));
        T->data=pre[pre1];
        createtree(T->lchild,pre1+1,pre2,in1,in1+control-1,pre,in);
        T->rchild=NULL;
    }
    if((control==0)&&(pre1!=pre2))
    {
        T->rchild=(struct BiTNode*)malloc(sizeof(struct BiTNode));
        T->data=pre[pre1];
        T->lchild=NULL;
        createtree(T->rchild,pre1+control+1,pre2,in1+control+1,in2,pre,in);
    }
}
main()
{
    struct BiTNode *t,*a,*b,*n;
    char pre[8],in[8];
    int i;
    pre[0]='a';
    pre[1]='b';
    pre[2]='c';
    pre[3]='d';
    pre[4]='e';
    pre[5]='g';
    pre[6]='f';
    pre[7]='h';
    in[0]='c';
    in[1]='b';
    in[2]='e';
    in[3]='g';
    in[4]='d';
    in[5]='f';
    in[6]='a';
    in[7]='h';
    t=(struct BiTNode*)malloc(sizeof(struct BiTNode));
    createtree(t,0,7,0,7,pre,in);
    printf("Please enter you choice:\n1.print in floor of this tree\n2.print in floor of the forest\n");
    scanf("%d",&i);
    if(i==1)
    {
        FloorPrint(t);
    }
    if(i==2)
    {
        FloorPrintTree(t);
    }
    getch();
}