#include "stdio.h"
#define N0 10
#define infi 32767
struct
{ int w,lch,rch,parent;
}ht[2*N0-1+1]; /* Huffman tree */
struct
{ char ch;
  int code[N0+1];
  int start;
}hc[N0+1]; /* Huffman code */
int n,m;
void select(int t, int *s1, int *s2 )
/* in 1..t select min s1, s2 */
{ int i,w1,w2;
  w1=w2=infi; /* ... */
  for( i=1; i<=t; i++ )
    if(ht[i].parent==0)
      if(ht[i].w<w1)
      { w2=w1;
    *s2=*s1;
    *s1=i;
    w1=ht[i].w;
      }
      else if(ht[i].w<w2)
      { w2=ht[i].w;
    *s2=i;
      }
}
void create_ht_hc()
{ int i,parent,child,w,s1,s2;
  char ch;
  printf("n:"); scanf("%d", &n);
  for(i=1; i<=n; i++)
  { printf("character weght:");
    fflush(stdin);
    scanf("%c%d", &ch, &w);
    ht[i].w=w;
    hc[i].ch=ch;
  }
  m=2*n-1;
  for(i=n+1; i<=m; i++)
  { select( i-1, &s1, &s2);
    ht[i].w=ht[s1].w+ht[s2].w;
    ht[i].lch=s1; ht[i].rch=s2;
    ht[s1].parent=ht[s2].parent=i;
  }
  for(i=1; i<=n; i++)
  { child=i;
    while(child!=m)
    {
      parent=ht[child].parent;
      if(child==ht[parent].lch)
     hc[i].code[hc[i].start++]=0;
      else
     hc[i].code[hc[i].start++]=1;
      child=parent;
    }
  }
}
void showcode()
{ int i, j;
  for(i=1; i<=n; i++)
  { printf("%c:", hc[i].ch);
    for(j=hc[i].start-1; j>=0; j--)
    printf("%d",hc[i].code[j]);
    printf("\n");
  }
}

void showtree(int root, int space)
{ int i; char ch;
  if(root)
  { for(i=1; i<=space; i++) printf(" ");
    if(root<=n) ch=hc[root].ch;
    else ch=' ';
    printf("%c:%d\n",ch, ht[root].w);
    showtree(ht[root].lch, space+6);
    showtree(ht[root].rch, space+6);
  }
}
void str2code(char str[], char code[])
/* abcdaabbcdd->01001011001010 */
{
???????????????????????????


}
void code2str(char code[], char str[])
/* 01001001....0->baaabbcddd */
{
   int i=0,j=0, parent=m;
   while( code[i] )
   { if(ht[parent].lch==0)
     {
       str[j++]=hc[parent].ch;
       parent=m;
     }
     if( code[i]=='0' ) parent=ht[parent].lch;
     else parent=ht[parent].rch;
     i++;
   }
   str[j++]=hc[parent].ch;
   str[j]='\0';
}

main()
{ char str[10*N0+1],code[10*N0+1];
  create_ht_hc();
  showtree(m,1);
  showcode();
  fflush(stdin);
  gets(str);
  str2code(str,code);
  puts(code);
  fflush(stdin);
  gets(code);
  code2str(code,str);
  puts(str);
}


[size=1]?[/size]