2018-07-16-哈夫曼树

题目：HDOJ-1053
忘记考虑只有一个字母的情况了。
而且为了实现简单，没有采用优先队列。
源代码：

#include<stdio.h>
#include<string.h>

#define N 27

typedef struct huffman
{
    int fr;
    int flag;
    int lc,rc;
}encode;

int input(encode a[])
{
    char c;
    int cnt=0;
    memset(a,0x0,(2*N-1)*sizeof(encode));
    while( (c=getchar())!='\n' )
    {
        cnt++;
        c&=0x1f;
        if(c==0x1f)
        {
            a[0].fr++;
        }
        else
        {
            a[c].fr++;
        }
    }
    if(cnt==3 && a['E'&0x1f].fr==1 && a['N'&0x1f].fr==1 && a['D'&0x1f].fr==1)
        return 0;
    else
        return cnt*8;
}

#define HAVE_NECESSARY_TO_VISIT 1

int create_tree(encode a[])
{
    int i,j,n,le1,le2;
    for(i=0;i<N;i++)
        if( a[i].fr!=0 )
            a[i].flag=HAVE_NECESSARY_TO_VISIT;
    for(i=0;i<N;i++)
        a[i].lc=a[i].rc=-1;
    for(j=N,n=2*N-1;j<n;j++)
    {
        for(i=0;i<n&&a[i].flag==0;i++);
        for(le1=i,i++;i<n&&a[i].flag==0;i++);
        if(i>=n)
            break;
        else
            le2=i;
        if(a[le2].fr < a[le1].fr)
        {
            le1=le1^le2;
            le2=le1^le2;
            le1=le1^le2;
        }
        for(i++;i<n;i++)
        {
            if(a[i].flag==HAVE_NECESSARY_TO_VISIT && a[i].fr<a[le2].fr)
            {
                if(a[i].fr > a[le1].fr)
                {
                    le2=i;
                }
                else
                {
                    le2=le1;
                    le1=i;
                }
            }
        }
        a[j].lc=le1;
        a[j].rc=le2;
        a[j].flag=HAVE_NECESSARY_TO_VISIT;
        a[le1].flag=0;
        a[le2].flag=0;
        a[j].fr=a[le1].fr+a[le2].fr;
    }
    if(j==N)
        return le1;
    else
        return j-1;
}

int traverse(encode a[],int root,int depth)
{
    if(root==-1)
        return 0;
    if( a[root].lc==-1 && a[root].rc==-1 )
        a[root].fr*=depth;
    else
        a[root].fr=0;
    depth++;
    return a[root].fr+traverse(a,a[root].lc,depth)+traverse(a,a[root].rc,depth);
}

int main()
{
    encode a[2*N-1];
    int cnt,root;
    while( (cnt=input(a)) != 0 )
    {
        root=create_tree(a);
        if(root<N)
            printf("%d %d %.1lf\n",cnt,cnt/8,8.0);
        else
        {
            root=traverse(a,root,0);
            printf("%d %d %.1lf\n",cnt,root,(double)cnt/root);
        }
    }
    return 0;
}