关于C语言建立赫夫曼树的问题，我不是很明白，下面是代码：

Question

#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

int min(HuffmanTree t,int i)
{
int j,flag;
unsigned int k=UINT_MAX;
for(j=1;j<=i;j++)
{
if(t[j].weight<k && t[j].parent==0)
k=t[j].weight,flag=j;
}
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int &s1,int &s2)
{
int j;
s1=min(t,i);//注意：这里s2,s2应该是不用的
s2=min(t,i);
if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd=NULL;
if(n<=1)//没有节点的时候就返回空值
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for( ;i<=m;++i,++p)//为什么这一步从n到m进行双亲的赋值
(*p).parent=0;
for(i=n+1;i<=m;++i)//建立赫夫曼树
{
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;//这一步是什么意思？？？
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight + HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//不明白这里为什么是n+1;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';//字符串的常规操作
for(i=1;i<=n;i++)
{
start=n-1;//编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(char *)malloc((n-start)*sizeof(char));//这里又为什么是n-start？？？？？？
strcpy(HC[i],&cd[start]);
}
free(cd);
}

int main()
{
HuffmanTree HT=NULL;//定义一个指针
HuffmanCode HC;//二级指针
int *w,n,i;
printf("Please input the number of all the node digit:");
scanf("%d",&n);
w=(int *)malloc(n*sizeof(int));
printf("Please input the %d node digits:\n",n);
for(i=0;i<n;i++)
scanf("%d",w+i);
HuffmanCoding(HT,HC,w,n);
for(i=1;i<=n;i++)
puts(HC[i]);
getch();
}
我只知道建立赫夫曼树的方法，却不是很理解代码的意思，请大家给我详细解释下，非常感谢

Answer 1

下面是我写程序的时候的注释，两种方法都写上了。这个程序不能运行，主要是为了理解，注释写的很清楚的。
/*这只是讲解，程序并不能运行*/
#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char * * HuffmanCode;

int a[100];
int s1,s2;

int Select()
/*在Select函数中，选取了两个根节点权值最小的树构造了一棵新的数，需要将这两个最小的删掉，将新的加入，再找两个最小的，但如果这样，我们就修改了树了，最后得到
的树中，我们删除了一些结点，所以我想，将这些树的权值放在一个整型数组中，去寻找最小的两个*/
{
min=a[1];
s1=1;
for(i=2;i<=a[0];++i)
if(min>a[i])
{
s2=s1;
s1=i;
}
for(i=s1;i<n;++i)
a[i]=a[i+1];
for(i=s2;i<n;++i)
a[i]=a[i+1];
a[0]=a[0]-2;
return OK;
}

HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
/*HT是树，HC存放赫夫曼树的叶结点的编码，w存放叶结点的权值，n是叶结点的个数*/
{
int m,i,j,start,t;
if(n<=1)
return OK;
m=2*n-1; /*因为有n个叶结点，所以共有2*n-1个结点*/
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*为m个节点分配空间，0结点不使用*/
if(!HT)
return ERROR;
for(p=HT,i=1;i<=n;++i,++p)
{
p->weight=w[i]; /*数组w中存放叶结点的权值，从下标1开始*/
p->parent=0;
p->lchild=0;
p->rchild=0;
} /*以上是为叶结点初始化*/
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
} /*为非叶结点初始化，非叶结点的权值是待计算的*/
a[0]=n;
for(p=HT,i=1;i<=a[0];++i,++p)
a[i]=p->weight;
for(i=n+1;i<=m;++i)
{
Select(); /*找到a数组中两个最小的元素是s1,s2，并且删除它们,a[0]中存储a中元素个数，要及时修改a[0]的值*/
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; /*将求得的新的结点的权值加入a数组中*/
a[0]=a[0]+1;
a[a[0]]=HT[i].weight;
} /*该循环是建赫夫曼树*/
/*以下从叶子到根逆向求每个字符的赫夫曼编码*/
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC)
return ERROR; /*为n个字符编码分配头指针向量，0号单元不使用*/
cd=(char *)malloc(n*sizeof(char));
if(!cd)
return ERROR; /*分配求编码的工作空间*/
cd[n-1]='\0'; /*编码结束符*/
for(i=1;i<=n;++i)
{
start=n-1; /*由于n-1位置已经存放了'/0'，所以下面用--start,从n-2的位置存放0,1编码*/
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]="0";
else
cd[--start]="1";
HC[i]=(char *)malloc((n-start)*sizeof(char)); /*各字符的编码长度不等，故为每一个头指针向量动态分配它所指向的空间大小，就是n-start*/
if(!H[i])
return ERROR;
t=1;
printf("\n%d:",i);
for(j=start;j<=n-2;j++)
{
HC[i][t++]=cd[j];
printf("%c",cd[j]);
}
}
free(cd);
return HT;
}
/*由此得到的赫夫曼树的前n个分量表示叶子结点，最后一个分量表示根结点*/
/*以上算法是从叶子到根逆向处理的*/

/*以下算法是从根出发，遍历整棵赫夫曼树，求得各个叶子结点所表示的字符的赫夫曼编码*/
/*译码的过程是分解电文中字符串，从根出发，按字符'0'或'1'确定找左孩子或右孩子，直至叶子结点，便求得该子串相应的字符。*/
HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
/*HT是树，HC存放赫夫曼树的叶结点的编码，w存放叶结点的权值，n是叶结点的个数*/
{
HuffmanTree p;
char *cd;
int m,i,j,start,t,c,f;
if(n<=1)
exit(OK);
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
if(!HT)
return ERROR;
for(p=HT+1,i=1;i<=n;++i,++p)
{
p->weight=w[i];
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
a[0]=n;
for(p=HT+1,i=1;i<=a[0];++i,++p)
a[i]=p->weight;
for(i=n+1;i<=m;++i)
{
Select();
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;
a[0]=a[0]+1;
a[a[0]]=HT[i].weight;
}

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC)
return ERROR; /*分配n个字符编码的头指针向量*/
p=m; /*m是结点总数*/
cdlen=0; /*应该是计数每一个编码的长度*/
for(i=1;i<=m;++i)
HT[i].weight=0; /*遍历赫夫曼树时用作结点的标志(是否是weight域为0，表示没有遍历过，weight域为1，表示遍历过)*/
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
} /*左孩子不等于0，表示没有走到左边的尽头，0就是NULL，*/
/*我们将一直执行这个if语句，直到走到左边的尽头，将所有左边的边全部赋值为0*/
else
if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd); /*当走到最左边的时候，我们就得到了最左下那个结点的编码，存储在cd数组中，将它赋值到HC[p]中*/
}
}
else
if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen; /*因为这个编码和上一个编码只有最后一位是不一样的，所以cdlen-1*/
}
}
return HT;
}