#include <stdio.h>
#include <stdlib.h>

typedef struct BiTree
{
    char data;
    struct BiTree *lchild;
    struct BiTree *rchild;
}BiTree, *BiNode;

BiNode CreatBiTree(BiNode T)
{
    char ch;
    scanf("%c", &ch);
    if(ch == ‘#‘)
    {
        T = NULL;
    }
    else
    {
        T = (BiNode)malloc(sizeof(BiTree));
        T->data = ch;
        T->lchild = CreatBiTree(T->lchild);
        T->rchild = CreatBiTree(T->rchild);
    }
    return T;
}


void PreBiTree(BiNode T)
{
    if(T)
    {
        printf("%c", T->data);
        PreBiTree(T->lchild);
        PreBiTree(T->rchild);
    }
}

BiNode Copy(BiNode T, BiNode P)
{
    if(T == NULL)
    {
        return NULL;
    }
    else
    {
        P = (BiNode)malloc(sizeof(BiTree));
        P->data = T->data;
        P->lchild = Copy(T->lchild, P->lchild);
        P->rchild = Copy(T->rchild, P->rchild);
    }
    return P;
}
int Depth(BiTree *T)
{
    int m, n;
    m = n = 0;
    if(T == NULL)
    {
        return 0;
    }
    else
    {
        m = Depth(T->lchild);
        n = Depth(T->rchild);
        if( m > n)
        {
            return (m+1);
        }
        else
        {
            return (n+1);
        }
    }
}

int BNumber(BiNode T)
{
    int m, n;
    if(T==NULL)
    {
        return 0;
    }
    else
    {
        m = BNumber(T->lchild);
        n = BNumber(T->rchild);
        return m+n + 1;
    }
}

int LeafCount(BiNode T)
{
    if(T == NULL)
    {
        return 0;
    }
    if( T->lchild == NULL && T->rchild == NULL)
    {
        return 1;
    }
    else
    {
        return LeafCount(T->lchild) + LeafCount(T->rchild);
    }
}

int main()
{
    int m;
    // ABC##DE#G##F###
    BiNode T;
    T = CreatBiTree(T);
    PreBiTree(T);

    m = Depth(T);
    printf("%d\n", m);

    m = BNumber(T);
    printf("%d\n", m);
    m = LeafCount(T);
    printf("%d\n", m);

}

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
    int weight;
    int parent, lch, rch;
}HTNode, *HuffmanTree;

HuffmanTree CreatHTree(HuffmanTree HT)
{
    int n, m, i, min1, min2; 
    printf("请输入初始结点数目:\t");
    scanf("%d", &n);
    
    if( n < 1)
    {
        return NULL;
    }
    
    HT = (HuffmanTree)malloc(sizeof(HTNode)*m+1);
    
    m = 2*n - 1;
    
    for( i = 1; i <= m; i++)
    {
        HT[i].lch = 0;
        HT[i].parent = 0;
        HT[i].rch = 0;
        HT[i].weight = 0;
    }
    
    for( i = 1; i <= n; i++)
    {
        scanf("%d", &HT[i].weight); 
    }
    // 5 29 7 8 14 23 3 11
    for( i = n + 1; i <= m; i++ )
    {
        min1 = 1;
        min2 = 1;
        search(HT, &min1 ,&min2, i-1);
        HT[i].weight = HT[min1].weight + HT[min2].weight;
        HT[min1].parent = i;
        HT[min2].parent = i;
        HT[i].lch = min1;
        HT[i].rch = min2;
    }
    for( i = 1; i <= m; i++ )
    {
        printf("%d个的权重为%d\n",i, HT[i].weight);
    }
    return HT;
}

void search(HuffmanTree HT, int *min1, int *min2, int i)
{
    int small1 = 10000000, small2 = 10000000, p1 = 0, p2 = 0, n;
    for(n = 1; n <= i; n++)
    {
        if( HT[n].parent == 0)
        {
            if(HT[n].weight < small1)
            {
                small2 = small1;
                small1 = HT[n].weight;
                p2 = p1;
                p1 = n;    
            } 
            else if( HT[n].weight < small2)
            {
                small2 = HT[n].weight;
                p2 = n;
            }
        }
    }
    *min1 = p1;
    *min2 = p2;
}

int main()
{
    HuffmanTree HT;
    HT = CreatHTree(HT);
}