#include<stdio.h>
#include <string.h>
#include <stdlib.h>
typedef char T;
int i=0;    //叶子结点数
typedef struct btnode    //结点定义
{
    T Element;
    struct btnode *LChild,*RChild;
}BTNode;
typedef struct btree    //头结点定义
{
    struct btnode *Root;
}BTree;
BTNode* NewNode()      //创建空间
{
    BTNode *p=(BTNode*)malloc(sizeof(BTNode));
    return p;
}
void CreateBT(BTree *Bt)    //创建一棵空二叉树
{
    Bt->Root=NULL;
}
void MakeBT(BTree *Bt,T x,BTree *Lt,BTree *Rt)    //进行树的建立
{
    BTNode *p=NewNode();
    p->Element=x;
    p->LChild=Lt->Root;
    p->RChild=Rt->Root;
    Lt->Root=Rt->Root=NULL;
    Bt->Root=p;
}
void Visit(BTNode *p)  //输出结点*P的元素值
{
    printf("%c",p->Element);
}
void PreOrd(void(*Visit)(BTNode *u),BTNode *t)    //先序遍历递归函数
{
    if(t)
    {
        (*Visit)(t);
        PreOrd(Visit,t->LChild);
        PreOrd(Visit,t->RChild);
    }
}
void InOrd(void(*Visit)(BTNode *u),BTNode *t)    //中序遍历递归函数
{
    if(t)
    {
        InOrd(Visit,t->LChild);
        (*Visit)(t);
        InOrd(Visit,t->RChild);
    }
}
void PostOrd(void(*Visit)(BTNode *u),BTNode *t)    //后序遍历递归函数
{
    if(t)
    {
        PostOrd(Visit,t->LChild);
        PostOrd(Visit,t->RChild);
        (*Visit)(t);
    }
}
void PreOrder(BTree Bt,void (*Visit)(BTNode *u))  //先序遍历
{
    PreOrd(Visit,Bt.Root);
}
void InOrder(BTree Bt,void (*Visit)(BTNode *u))    //中序遍历
{
    InOrd(Visit,Bt.Root);
}
void PostOrder(BTree Bt,void (*Visit)(BTNode *u))  //后序遍历
{
    PostOrd(Visit,Bt.Root);
}
int Size(BTNode *p)      //树的结点数与叶子结点数的递归函数
{
    int s,s1,s2;
    if(!p)
        return 0;
    else
    {
        s1=Size(p->LChild);
        s2=Size(p->RChild);
        s=s1+s2+1;
        if(s1==0&&s2==0)//判断是否是叶子节点
        {
            i++;
            printf("%3c",p->Element);
            return s;
        }
        else
        {
            return s;
        }
    }
}
int SizeofBT(BTree Bt)    //树的结点数
{
    return Size(Bt.Root);
}
int Depth(BTNode *p)    //树的高度递归函数
{
    if(!p)
        return 0;
    else
        return 1+max(Depth(p->LChild),Depth(p->RChild));
}
int DepthofBT(BTree Bt)    //树的高度
{
    return Depth(Bt.Root);
}
void BreakBT(BTree* Bt,T *x,BTree *Lt,BTree *Rt)    //树的拆分
{
    BTNode *p=Bt->Root;
    if(p)
    {
        x=p->Element;
        printf("根数：%c\n",x);
        Lt->Root =p->LChild;
        Rt->Root =p->RChild;
        Bt->Root=NULL;
        free(p);
    }
}
void main(void)   
{
    BTree a,x,y,z;   
    T e;        //树的结点的元素
    int j,k;    //树的结点数与高度
    CreateBT(&a);
    CreateBT(&x);
    CreateBT(&y);
    CreateBT(&z);    //建立空树
    MakeBT(&x,'B',&a,&a);
    MakeBT(&x,'A',&x,&z);
    printf("遍历算法测试：\n");
    printf("---------------------------------------\n");
    printf("先序遍历测试结果：");
    PreOrder(x,Visit);
    printf("\n中序遍历测试结果：");
    InOrder(x,Visit);
    printf("\n后序遍历测试结果：");
    PostOrder(x,Visit);   
    printf("\n树的叶子结点为:");//建立树
    j=SizeofBT(x);
    k=DepthofBT(x);
    printf("\n树的叶子结点数为：%d\n",i);
    printf("树的结点数为：%d\n",j);
    printf("树的高度为：%d\n\n\n",k);
    printf("拆树算法测试：\n");
    printf("---------------------------------------\n");
    BreakBT(&x,&e,&z,&y);
    printf("---------------------------------------\n");
    printf("左孩子：\n");
    printf("先序遍历测试结果:");
    PreOrder(z,Visit);
    printf("\n中序遍历测试结果:");
    InOrder(z,Visit);
    printf("\n后序遍历测试结果:");
    PostOrder(z,Visit);
    i=0;
    printf("\n树的叶子结点为:");//建立树
    j=SizeofBT(z);
    k=DepthofBT(z);
    printf("\n树的叶子结点数为：%d\n",i);
    printf("树的结点数为：%d\n",j);
    printf("树的高度为：%d\n\n\n",k);
    printf("---------------------------------------\n");
    printf("先序中序后序遍历二叉树右孩子：\n");
    printf("先序遍历测试结果:");
    PreOrder(y,Visit);
    printf("\n中序遍历测试结果:");
    InOrder(y,Visit);
    printf("\n后序遍历测试结果:");
    PostOrder(y,Visit);
    i=0;
    printf("\n树的叶子结点为:");//建立树
    j=SizeofBT(y);
    k=DepthofBT(y);
    printf("\n树的叶子结点数为：%d\n",i);
    printf("树的结点数为：%d\n",j);
    printf("树的高度为：%d\n\n\n",k);
    printf("\n");
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。