二叉树的基本操作

本文作者：韩申权
作者博客：http://www.cnblogs.com/hsqdboke
转载请注明出处，侵权必究，保留最终解释权！

#include<stdio.h> //' '空格代表树的元素为空
#include<stdlib.h>
#define OVERFLOW -1
typedef char TElemType;
typedef struct BitNode
{
    TElemType data;
    struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
typedef struct QNode
{
    BitNode data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
void BinTreeInit(BitNode **BT)  //初始化二叉树
{
    *BT=NULL;
}
BitNode *BinTreeCreat(BitNode *BT) //按先序次序构造二叉树
{
    char c;
    scanf("%c",&c);
    if(c==' ')BT=NULL;
    else
    {
        if(!(BT=(BitTree)malloc(sizeof(BitNode))))
            exit(OVERFLOW);
        BT->data=c;
        BT->lchild=BinTreeCreat(BT->lchild); //注意因为有返回值，必须有左值
        BT->rchild=BinTreeCreat(BT->rchild);
    }
    return BT;
}
int BinTreeEmpty(BitNode *BT)//检查二叉树是否为空
{
    if(BT==NULL)return 1;
    else return 0;    
}
void visit(BitNode *BT) //visit函数
{
    printf("%c",BT->data);    
}
void PreOrderTraverse(BitNode *BT)//先序遍历树
{
    if(BT)
    {
    visit(BT);
    PreOrderTraverse(BT->lchild);
    PreOrderTraverse(BT->rchild);
    }
}
void InOrderTraverse(BitNode *BT)//中序遍历树
{
    if(BT)
    {
    InOrderTraverse(BT->lchild);
    visit(BT);
    InOrderTraverse(BT->rchild);
    }
}
void PostOrderTraverse(BitNode *BT)//后序遍历树
{    
    if(BT)
    {
    PostOrderTraverse(BT->lchild);
    PostOrderTraverse(BT->rchild);
    visit(BT);
    }
}
void InitQueue(LinkQueue *Q) //构造一个空的队列
{
    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q->front)exit(OVERFLOW);
    Q->front->next=NULL;
}
int QueueEmpty(LinkQueue *Q)
{
    if(Q->rear==Q->front)return 1;
    else return 0;
}
void EnQueue(LinkQueue *Q,BitNode e) //入队
{
    QNode *p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p)exit(OVERFLOW);
    p->data=e;
    p->next=NULL;
    Q->rear->next=p;
    Q->rear=p;
}
void DeQueue(LinkQueue *Q,BitNode *e)//出队
{
    QNode *p;
    p=Q->front->next;
    *e=p->data;
    Q->front->next=p->next;
    if(Q->rear==p)Q->rear=Q->front;
    free(p);
}
void BFSTraverse(BitNode *BT)//层次遍历树
{
    BitNode m;
    LinkQueue Q;
    InitQueue(&Q);
    EnQueue(&Q,*BT);
    while(!QueueEmpty(&Q))
    {
        DeQueue(&Q,&m);
        visit(&m);
        if(m.lchild)EnQueue(&Q,*(m.lchild));
        if(m.rchild)EnQueue(&Q,*(m.rchild));
    }    
}
int BinTreeDepth(BitNode *BT)//求二叉树的深度
{
    int dep1,dep2;
    if(BT==NULL)return 0;
    else 
    {
        dep1=BinTreeDepth(BT->lchild);
        dep2=BinTreeDepth(BT->rchild);
        if(dep1>dep2)return 1+dep1;
        else return 1+dep2;
    }
}
void BinCountleaf(BitNode *BT,int *count)//求二叉树的叶子节点的个数
{
    if(BT)
    {
        if(!BT->lchild&&!BT->rchild)(*count)++;
        BinCountleaf(BT->lchild,count);
        BinCountleaf(BT->rchild,count);
    }        
}
void BinTreeClear(BitNode **BT)//清除二叉树
{
    if(*BT)
    {
        BinTreeClear(&(*BT)->lchild);
        BinTreeClear(&(*BT)->rchild);
        free(*BT);
        *BT=NULL;
    }
}
int main()
{
    int count=0;
    BitNode *BT=NULL;
    BinTreeInit(&BT); //初始化二叉树
    BT=BinTreeCreat(BT);//构造二叉树
    printf("执行创建树操作后: ");
    if(BinTreeEmpty(BT))printf("树空\n");//判空
    else printf("树不空\n");
    printf("先序遍历二叉树: ");
    PreOrderTraverse(BT);printf("\n");
    printf("中序遍历二叉树: ");
    InOrderTraverse(BT);printf("\n");
    printf("后序遍历二叉树: ");
    PostOrderTraverse(BT);printf("\n");
    printf("层次遍历二叉树: ");
    BFSTraverse(BT);printf("\n");
    printf("二叉树的深度为:%d\n",BinTreeDepth(BT));//求二叉树的深度
    BinCountleaf(BT,&count);//求二叉树中的节点个数
    printf("二叉树的叶子节点个数为:%d\n",count);
    BinTreeClear(&BT);//清空树
    printf("执行清空树操作后: ");
    if(BinTreeEmpty(BT)==1)printf("树空\n");//判空
    else printf("树不空\n");

    return 0;
}　　　　　　　　　　

 或者将构造二叉树的操作改为，main函数里对此函数的调用扫做修改即可：

void BinTreeCreat(BitNode **BT) //按先序次序构造二叉树
{
char c;
scanf("%c",&c);
if(c==' ')*BT=NULL;//此处曾把'*'漏掉
else
{
if(!((*BT)=(BitTree)malloc(sizeof(BitNode))))
exit(OVERFLOW);
(*BT)->data=c;
printf("%c",(*BT)->data);
BinTreeCreat(&(*BT)->lchild); 
BinTreeCreat(&(*BT)->rchild);
}
}