有没有通俗易懂的　帮忙贴一下
我是搞不懂啊

好像和哈夫曼树差不多，根据权植，然后找到最小权植，然后，相加变为双亲，

我也不太懂，好像是这样吧

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define INT_MAX 100000
#define N 10000
typedef struct HTNode//类型定义
{                        
 int weight;
 int parent;
 int lchild;
 int rchild;
 char data;
 char code[20];
}*HuffmanTree;
void Select(HuffmanTree HT,int end,int &s1,int &s2)      //查找权值最小的两个字符序号
{
  int i,j,t;
  int min1=INT_MAX;
  int min2;
  
     for (i=1;i<=end;i++)
  {
          if (HT[i].parent==0&&HT[i].weight<min1)
    {
          s1=i;
          min1=HT[i].weight;
    }
  }
   min2=INT_MAX;
     
     for(j=1;j<=end;j++)
  {
          if (HT[j].parent==0&&(s1!=j)&&min2>HT[j].weight)
    {
              s2=j;
              min2=HT[j].weight;
          }
     }
  if(s1>s2)
  {
   t=s1;
   s1=s2;
   s2=t;
  }
}
void Initialization(HuffmanTree &ht,int a,int b)   //初始化HuffmanTree，建立该树
{
 int i,start,f,c,s1,s2;
 char *cd;
 char *str;
 int *w;
 str=new char[a+1];
    w=new int[a+1];
 cout<<"输入源字符:"<<endl;
 for(i=1;i<=a;i++)                              
  //初始化输入字符时，注意：应连续输入，再按回车键！  
  cin>>str[i];
 cout<<"输入权值:"<<endl;
    for(i=1;i<=a;i++)
  cin>>w[i];
 ht=new HTNode[b+1];
 for(i=1;i<=a;i++)
 {
  ht[i].weight=w[i];
  ht[i].parent=0;
  ht[i].lchild=0;
  ht[i].rchild=0;
  ht[i].data=str[i];
 }
 for(;i<=b;i++)
 {
  ht[i].weight=0;
  ht[i].parent=0;
  ht[i].lchild=0;
  ht[i].rchild=0;
  ht[i].data='\0';
  ht[i].code[0]='\0';
 }
   for(i=a+1;i<=b;i++){
        Select(ht,i-1,s1,s2);
        ht[s1].parent=i;
        ht[s2].parent=i;
        ht[i].lchild=s1;
        ht[i].rchild=s2;
        ht[i].weight=ht[s1].weight+ht[s2].weight;
    }
 cd=new char[a];
    cd[a-1]='\0';
      for(i=1;i<=a;++i)            //求出各字符相应的编码
  {
        f=ht[i].parent;
  c=i;
  start=a-1;
        while(f!=0)
  {
           if(ht[f].lchild==c)
      cd[--start]='0';
           else
      cd[--start]='1';
     c=f;
     f=ht[f].parent;
  }
        strcpy(ht[i].code,&cd[start]);
  }
}
void Encoding(HuffmanTree ht)                   //要求输入报文，然后编码！
{
 int i=0,j;
 char str[N];   
 cout<<"输入要编译的字符"<<endl;
    cin>>str;
 cout<<endl<<"编译后的字符为:"<<endl;
 while(str[i]!='\0')
 {
  j=1;
  while(ht[j].data!=str[i])j++;
  cout<<ht[j].code;
  i++;
 }
 cout<<endl<<endl;
}
void Decoding(HuffmanTree ht,int m)              //要求输入原码，进行译码！
{
 
 int i=0,p;
 char s[N];
 cout<<"输入要译回的数字（二进制）:"<<endl;
 cin>>s;
    cout<<"其真实字符为:"<<endl;
 p=m;
 while(s[i]!='\0')
 {
  while(ht[p].lchild!=0&&s[i]!='\0')
  {
   if(s[i]=='0')
    p=ht[p].lchild;
   else
    p=ht[p].rchild;
   i++;
  }   
   
         cout<<ht[p].data;
   p=m;   
 } cout<<endl<<endl;
}
void print(HuffmanTree ht,int n,int m)            //打印HuffmanTree到输出端
{
 int i;
 cout<<"下面将列出创建哈夫曼树的结果:"<<endl<<endl;
 cout<<"loc"<<'\t'<<"w"<<'\t'<<"par"<<'\t'<<"lch"<<'\t'<<"rch"<<'\t'<<"data"<<'\t'<<"code"<<endl;
 
 for(i=1;i<=m;i++)
  cout<<i<<'\t'<<ht[i].weight<<'\t'<<ht[i].parent<<'\t'<<ht[i].lchild<<'\t'<<ht[i].rchild<<'\t'<<ht[i].data<<'\t'<<ht[i].code<<'\t'<<endl;
}
void main()
{
 int n,m;
 char a,b;
 HuffmanTree HT=NULL;
 while(b!='Q')                        //系统界面……
 {
  cout<<"请选择要进行的操作:"<<endl;
  cout<<"创建哈夫曼树型结构(I)"<<'\t'<<"编码(E)"<<'\t'<<"译码(D)"<<'\t'<<"输出(P)"<<'\t'<<"退出程序(Q)"<<endl;
  cin>>a;
  switch(a){
  case 'I':
   cout<<"输入哈夫曼 源字符的个数:"<<endl;
   cin>>n;
   m=2*n-1;
   Initialization(HT,n,m);
   break;
  case 'E':
   Encoding(HT);
   break;
  case 'D':
   Decoding(HT,m);
   break;
  case 'P':
   print(HT,n,m);
   break;
  case 'Q':
   b='Q';
   break;
  }
 }
}

用哈夫曼树就能实现了

哈夫曼树和这个不是一个概念。
哈夫曼树并不是查找树，他有左儿子比根节点小，右儿子比根节点大的特性吗。而且哈夫曼树的节点
还不是原始的数据节点。

分两种情况。
1.所有的查找概率相同
那么先把原始序列排序，然后每次取中间节点作为根节点。左右依次递归
2.查找概率不同
这时得用动态规划实现。
先从小到大排序
状态d[i][j]表示序列中第i个数到第j个数的最少平均查找次数
则d[i][j] = min(d[i][k] + d[k][j] + p*w) i<k<j
其中p为每个节点的查找概率，其中w为每个节点的路经长

好