数据结构C语言版二叉链表存储树

8086zzl

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef char TElemtype;
typedef int status;
typedef struct BiTNode
{
        TElemtype date;//数据域
        struct BiTNode *lchild,*rchild;//左孩子,右孩子指针
}BiTNode,*BiTree;
typedef struct QNode
{
        BiTree Qdata;
        struct QNode *next;
}QNode,*QNodePtr;
typedef struct LinkQueue
{
        QNodePtr front;
        QNodePtr rear;
}LinkQueue;
status PrintTElement(TElemtype e);
status EnQueue(LinkQueue &Q,BiTree e);
status DeQueue(LinkQueue &Q,BiTree &b);
status InitQueue(LinkQueue &Q);
status QueueEmpty(LinkQueue Q);
status CreateBiTree(BiTree &T)//先序输入节点值
{
        TElemtype ch;
        scanf("%c",&ch);//输入字符节点
        if(ch=='#')//遇到' '时节点值为空
        T=NULL;
        else
        {
                T=(BiTNode *)malloc(sizeof(BiTNode));
                if(!T)
                exit(OVERFLOW);
                T->date=ch;//数据域赋值
                CreateBiTree(T->lchild);//递归创建左孩子
                CreateBiTree(T->rchild);//递归创建右孩子
        }
}
status PreorderTraverse(BiTree T,status(*visit)(TElemtype e))//先序遍历二叉树T，每个节点调用一次visit函数
{
        if(!T)//判断是否为空树
        return ERROR;
        else
        {
                visit(T->date);//遍历节点
                PreorderTraverse(T->lchild,visit);//递归遍历左子树
                PreorderTraverse(T->rchild,visit);//递归遍历右子树
        }
        return OK;
}
status InorderTraverse(BiTree T,status(*visit)(TElemtype e))//中序遍历二叉树
{
        if(!T)
        return ERROR;
        else
        {
                InorderTraverse(T->lchild,visit);//先遍历左子树
                visit(T->date);//再遍历根节点
                InorderTraverse(T->rchild,visit);//最后遍历右子树
        }
        return OK;
}
status PostorderTraverse(BiTree T,status(*visit)(TElemtype e))//后序遍历二叉树
{
        if(!T)
        return ERROR;
        else
        {
                PostorderTraverse(T->lchild,visit);//先遍历左子树
                PostorderTraverse(T->rchild,visit);//再遍历右子树
                visit(T->date);//最后遍历根节点
        }
        return OK;
}
status LevelOrder(BiTree T)//按层次遍历二叉树T， Q为队列
{
    LinkQueue Q;
    BiTree b;
        InitQueue(Q);
        if (T)
        {                                        // 若树非空
        EnQueue(Q,T);                                        //根结点入队列
        while(!QueueEmpty(Q))
                {
                DeQueue(Q,b);                                     //队首元素出队列
                   if (b->lchild)  
                           EnQueue(Q,b->lchild);//左子树非空，则入队列
                   if (b->rchild)
                           EnQueue(Q,b->rchild);//右子树非空，则入队列
        }
    }
    return OK;
}
status InitQueue(LinkQueue &Q)//初始化队列
{
        Q.front=Q.rear=(QNode *)malloc(sizeof(QNode));
        Q.front->next=NULL;
        return OK;
}
status DeQueue(LinkQueue &Q,BiTree &b)//队列元素出队列
{
        QNodePtr p;
        if(QueueEmpty(Q))
        return ERROR;
        else
        {
                p=Q.front->next;
                b=p->Qdata;
                printf("%c",b->date);
                Q.front->next=p->next;
                if(p==Q.rear)
                {
                        Q.rear=Q.front;
                }
                free(p);
        }
        return OK;
}
status EnQueue(LinkQueue &Q,BiTree e)//队列元素进队列
{
        QNodePtr p;
        p=(QNode *)malloc(sizeof(QNode));
        if(!p)
        return ERROR;
        p->Qdata=e;
        p->next=NULL;
        Q.rear->next=p;
        Q.rear=p;
}
status QueueEmpty(LinkQueue Q)
{
        if(Q.front==Q.rear)
        return OK;
        else
        return ERROR;
}
status Depth(BiTree T)//求二叉树的深度
{
        int depth,depthl,depthr;
        if(!T)
        depth=0;
        else
        {
                depthl=Depth(T->lchild);
                depthr=Depth(T->rchild);
                depth=1+(depthl>depthr?depthl:depthr);
        }
        return depth;
}
int countleaf(BiTree T)//求叶子结点的个数
{
        int num1,num2,num;     
        if (T==NULL)
        num=0;
        else
        if((T->lchild==NULL)&&(T->rchild==NULL))       
        num=1;
        else
        {
                num1=countleaf (T->lchild);
                num2= countleaf(T->rchild);
                num= num1+num2;
        }
        return num;
}
status  count_n(BiTree T)//求总结点的个数
{
        int num1,num2,num;
        if (T==NULL)
        num=0;
        else
        {
                num1=count_n(T->lchild);
                num2=count_n(T->rchild);
                num= num1+num2+1;
    }
        return num;
}
status Doublenum(BiTree T)//求双亲节点的个数
{
        int num=0,num1=0,num2=0;
        if(!T)
        num=0;
        else if(T->lchild&&T->rchild)
        {
                num=1;
                num1=Doublenum(T->lchild);
                num2=Doublenum(T->rchild);
                num+=num1+num2;
        }
        return num;
}
status singlenum(BiTree T)//求单分支节点的个数
{
        if(!T)
        return 0;
        else if(!T->lchild&&T->rchild)
        return (singlenum(T->rchild)+1);
        else if(!T->rchild&&T->lchild)
        return (singlenum(T->lchild+1));
        else
        return (singlenum(T->lchild)+singlenum(T->rchild));
}
status PrintTElement(TElemtype e)//输出，即visit(函数指针)指向的函数
{
        printf("%c",e);
        return OK;
}
int main()
{
        BiTree T;
        int m;
        printf("输入各个节点的值:\n");
        if(CreateBiTree(T))
        printf("先序成功建立二叉树!\n");
        printf("建立的二叉树的深度为:%d\n",Depth(T));
        printf("先序遍历二叉树:\n");
        PreorderTraverse(T,PrintTElement);
        printf("\n");
        printf("中序遍历二叉树:\n");
        InorderTraverse(T,PrintTElement);
        printf("\n");
        printf("后序遍历二叉树:\n");
        PostorderTraverse(T,PrintTElement);
        printf("\n");
        printf("层序遍历二叉树:\n");
        LevelOrder(T);
        printf("\n");
        printf("该二叉树的叶子节点个数为:%d\n",countleaf(T));       
        printf("该二叉树的节点总个数为:%d\n",count_n(T));
        printf("该二叉树的单分支个数为:%d\n",singlenum(T));
        printf("该二叉树的双分支个数为:%d\n",Doublenum(T));
        return 0;
}