二叉树基本操作.txt

本程序是用TC编写

#include"stdio.h"
#include"stdlib.h"
#define OK 1
#define ERROR 0
#define MAXSIZE 1024
#define QMAXSIZE 100

 /* 定义DataType为char类型*/
typedef char DataType;

/* 二叉树的结点类型*/
typedef struct BitNode
{
    DataType data;
    struct BitNode *lchild,*rchild;
}BitNode,*BitTree;

typedef BitTree SDataType; /*定义类型有利于实现多态*/

typedef struct
{
    SDataType data[MAXSIZE];
    int top;
}SeqStack;


typedef BitTree QElemType ;

typedef struct
{
    QElemType *base;
    int front;   /*头指针*/
    int rear;    /*尾指针*/
}SqQueue;

/*堆栈应用程序区***************************************************************/

/*初始化顺序栈*/
void SeqStackInit(SeqStack &s)
{
    s.top=0;
}

/*检查顺序栈是否为空*/

int SeqStackEmpty(SeqStack s)
{
    return(s.top==0);
}

/*检查顺序栈是否满*/
int SeqStackFull(SeqStack s)
{
     return(s.top==MAXSIZE);
}

/*将顺序栈置空*/
void ClearStack(SeqStack &s)
{
     s.top=0;
}

/*将元素X压入栈，使其成为新的栈顶元素*/
void SeqStackPush(SeqStack &s,SDataType x)
{
    if(SeqStackFull(s))
    {
        printf("StackFull!");
        return;
    }
    else
    {
        s.data[s.top++]=x;  /*栈顶TOP指向一个空值，其下一位才是元素ID型*/
    }
}

/*把栈顶元素弹出*/
SDataType SeqStackPop(SeqStack &s)
{
    if(SeqStackEmpty(s))
    {
        printf("Stack Empty!\n");
        return NULL;
    }
    else
    {
        return s.data[--s.top];
    }
}

/*取栈顶元素*/

SDataType SeqStackGetTop(SeqStack s)
{
    if(SeqStackEmpty(s))
    {
        printf("Stack Empty!\n");
        return NULL;
    }
    else
    {
        return s.data[s.top-1];
    }
}
/*******************************************************************************/

/*队列应用程序区****************************************************************/


void InitQueue(SqQueue &Q)
{
    Q.base=(QElemType *)malloc(QMAXSIZE*sizeof(QElemType));
    if(!Q.base)
    {
       printf("InitQueue Over Flow!");
       exit(1);
    } /*出错返回*/
     Q.front=0;
     Q.rear=0;  /*设置一个空闲的存储单元*/
}

/*  判断队列是否为空*/
int QueueEmpty(SqQueue Q)
{
    return(Q.front==Q.rear);
}

int QueueFull(SqQueue Q)
{
    return((Q.rear+1)%QMAXSIZE==Q.front);
}

 /*求队列的长度*/
int QueueLength(SqQueue Q)
{
    return((Q.rear-Q.front+QMAXSIZE)%QMAXSIZE);
}

void GetHead(SqQueue Q,QElemType &e)
{
    if(!QueueEmpty(Q))
    {
        e=Q.base[Q.front];
    }
    else
    {
        printf("GetHead:SqQueue Empty!");
    }
}

void EnQueue(SqQueue &Q,QElemType e)
{
    if(!QueueFull(Q))
    {
        Q.base[Q.rear]=e;
        Q.rear=(Q.rear+1)%QMAXSIZE;
    }
    else
    {
        printf("No free cell!");
    }

}

/* 出队*/
void DeQueue(SqQueue &Q,QElemType &e)
{
    if(!QueueEmpty(Q))
    {
        e=Q.base[Q.front];
        Q.front=(Q.front+1)%QMAXSIZE;
    }
    else
    {
        printf("DeQueue:Queue EMpty!");
    }
}


/********************************************************************************/



 int  Visit(BitTree BT)
 {
    printf("%c",BT->data);
    return OK;
 }
/* 初始化二叉树，即把树根指针置空*/
void BinTreeInit(BitTree *BT)
{
      *BT=NULL;   //指针置空
}

/* 按先序次序建立一个二叉树
   有几个叶子节点就要打几个￥
*/
void BinTreeCreate(BitTree *BT)
{
    DataType ch;
    printf("Please input one character:\n");
    scanf("%c",&ch);
    fflush(stdin);
    if(ch=='$')
    {
        *BT=NULL;
    }
    else
    {
        *BT=(BitNode*)malloc(sizeof(BitNode));
        if(!(*BT))
        {
            printf(" CREATE OVERFLOW!\n");
            exit(1);
        }
        (*BT)->data=ch;
       BinTreeCreate(&(*BT)->lchild);
       BinTreeCreate(&(*BT)->rchild);
    }
}

/*检查二叉树是否为空*/
int BinTreeEmpty(BitTree *BT)
{
    return((*BT)==NULL);
}
/*中序遍历二叉树*/
void BinTraverse(BitTree *BT)
{
    SeqStack s;
    BitNode *p;
    SeqStackInit(s);
    p=*BT;
    while(p||!SeqStackEmpty(s))
    {
        if(p)
        {
           SeqStackPush(s,p);
           p=p->lchild;
        }
        else
        {
            p=SeqStackPop(s);
            if(!Visit(p))
            {
                printf("Unsuccessful Visit!\n");
                exit(1);
            }
            p=p->rchild;
        }
    }
}
int BinTreeDepth(BitTree BT)
{
    int Height;
    int lheight;  //左树的高度
    int rheight;   //右树的高度
    if(!BT)
    {
        Height=0;
    }
    else
    {
        lheight=BinTreeDepth(BT->lchild)+1;
        rheight=BinTreeDepth(BT->rchild)+1;
        Height=lheight>rheight?lheight:rheight;
    }
     return Height;
}
int BinTreeCount(BitTree BT)
{
    int count;
    int lcount; //左子树的节点数
    int rcount; //右子树的节点数
    if(BT==NULL)
    {
        count=0;
    }
    else
    {
        lcount=BinTreeCount(BT->lchild);
        rcount=BinTreeCount(BT->rchild);
        count=lcount+rcount+1;
    }
    return count;
}
void BinTreeClear(BitTree *BT)
{
    *BT=NULL;
}

main()
{
    BitTree BT;
     BinTreeInit(&BT);


     BinTreeCreate(&BT);
     BinTraverse(&BT);
     
     printf("\n");

     printf("%d\n",BinTreeDepth(BT));
     printf("%d",BinTreeCount(BT));

     BinTreeClear(&BT);
     if(BT==NULL)
     {
        printf("Sucess!");

     }
     

}