数据结构与算法----哈夫曼树（老师作业）

哈夫曼树的创建：

1. 初始状态下分别有n个结点，结点的权值分别为给定的n个数，将它们视作n棵只有根节点的数
2. 合并其中根结点权值最小的两棵树，生成这两棵树的父结点，权值为这两个根结点的权值之和
3. 重复操作2直至只剩下一棵树为止

代码如下： 

//哈夫曼编码 
void HUffumanco(HuffmanTree HT,HUffmancode HC,int n)//哈夫曼表存储在编码表HC中 
{
	HC=(HUffmancode)malloc(sizeof(char*)*(n+1));//数组的0号单元不使用，从1号单元开始所以数组HC大小为n+1 
	char *code=(char*)malloc(sizeof(char)*n);//分配临时存放编码的动态数组 
    code[n-1]='';//编码结束符 
	int i,start,c,p;
	for(i=1;i<=n;i++)//逐个求哈夫曼编码 
	{   //从叶子结点开始向上回溯直到根结点 
		start=n-1;//start指针指向 
	    c=i;
	    p=HT[c].parent;
		while(p!=0)//直到父结点为0为止
		{
			start--;//回溯一次strat向前指1个位置 
			if(HT[p].Lchild==c)//结点c是p的左孩子 
			{
				code[start]='0';
			}
			else//是p的右孩子 
			{
				code[start]='1';
			}
			c=p;
			p=HT[c].parent;
		 } 
		 HC[i]=(char*)malloc(sizeof(char)*(n-start));
		 strcpy(HC[i],code[start]);//将求得的编码从临时空间复制到HC的当前行中 
	 } 
	 free(code);//释放临时空间 
}

完整代码：

#include 
#include 
#include 
typedef char **HUffmancode;//动态分配数组存储哈夫曼树编码 
typedef struct HTNode{
	int weight;
	int parent,Lchild,Rchild;
}HTNode,*HuffmanTree;
 
void Select(HuffmanTree HT,int n,int s1,int s2)
{
	int min;//把第一个出现父结点为零的结点赋值给min,然后再将它与接下来的结点比较找到权值最小的那个结点赋给s1 
	int i;
	for(i=1;i<=n;i++)
	{
		if(HT[i].parent==0)//父结点为零的点 
		{
			min=i;
			break;
		}
	}
	for(i=min+1;i<=n;i++)
	{
		if(HT[i].parent==0&&HT[i].weight