#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
typedef struct node
{
    DataType data;
    struct node *LChild;
    struct node *RChild;
}BiTNode,*BiTree;
typedef struct
void CreBiTree(BiTree *bt)
{
    char ch;
    rewind(stdin);
    ch=getchar();
    if(ch=='.') *bt=NULL;
    else
    {
        *bt=(BiTree)malloc(sizeof(BiTNode))
        (*bt)->data=ch;
        CreBiTree(&((*bt)->LChild));
        CreBiTree(&((*bt)->RChild));
    }
}
void PreOrder(BiTree root)
{
    if(root!=NULL)
    {
        printf("%c",root->data);
        PreOrder(root->LChild);
        PreOrder(root->RChild);
    }
}
void InOrder(BiTree root)
{
    if(root!=NULL)
    {
        InOrder(root->LChild);
        printf("%c",root->data);
        InOrder(root->RChild);
    }
}
void PostOrder(BiTree root)
{
    if(root!=NULL)
    {
        PostOrder(root->LChild);
        PostOrder(root->RChild);
        printf("%c",root->data);
    }
}
int PostBiTreeDepth(BiTree root)
{
    int hl,hr,max;
    if(bt!=NULL)
    {
        hl=PostBiTreeDepth(root->LChild);
        hr=PostBiTreeDepth(root->RChild);
        max=hl>hr?hl:hr;
        return(max+1);
    }
    else
        return(0);
}
int Leaf(BiTree root)
{
    int LeafCount=0;
    if(root!=NULL)
    {
        Leaf(root->LChild);
        Leaf(root->RChild);
        if(root->LChild==NULL&&root->RChild==NULL)
            LeafCount++;
    }
    return(LeafCount);
}
int Bit(BiTree bt)
{
    int bit=0;
    if(bt!=NULL)
    {
        Bit(bt->LChild);
        Bit(bt->RChild);
        bit++;
    }
    return(bit);
}

void main()
{
    int i,flag=1;
    int d,b;
    BiTree T;
    printf("二叉树演示过程\n");
    printf("1.二叉树创建\n");
    printf("2.二叉树遍历\n");
    printf("3.二叉树属性\n");
        printf("4.创建哈夫曼树\n");
        printf("5.哈夫曼编码\n");
    printf("6.退出\n");
    printf("\n");
    while(flag)
    {
        rewind(stdin);
        printf("1-6 请选择:");
        scanf("%d",&i);
        switch(i)
        {
            case 1:
                printf("输入元素:");
                CreBiTree(&T);
                break;
            case 2:
                printf("先序遍历!");
                PreOrder(T);
                printf("\n");
                printf("中序遍历!");
                InOrder(T);
                printf("\n");
                printf("后序遍历!");
                PostOrder(T);
                printf("\n");
                break;
            case 3:
                {
                printf("树的属性:\n");
                d=PostBiTreeDepth(T);
                printf("树的深度 %d\n",d);
                b=Bit(T);
                printf("树的结点数 %d\n",b);
                printf("叶子结点%d\n",Leaf(T));
                break;
                }
            case 4:
                {
                    flag=1;break;
                }
        }
    }
}