霍夫曼树的有关问题

#include<stdio.h>

#include<stdlib.h>

#include<string.h>


typedef char* *HuffmanCode;

typedef struct {

	unsigned int weight;

	unsigned int parent,lchild,rchild;

}HTNode, * HuffmanTree;


void CreateHuffmanTree(HuffmanTree *HT, unsigned int *w, int n);

void Select(HuffmanTree HT, int i, int *s1, int *s2);

void HuffmanTreeCoding(HuffmanTree HT, HuffmanCode *HC, int n);

void PreOrderTraverse(HuffmanTree HT, int length); //先序遍历


int main(void)

{

	int n;

	int i;

	unsigned int *w;

	HuffmanTree HT = NULL; //构造霍夫曼数的头结点 


	printf("Please enter the leaf's total of HuffmanTree:");

	scanf("%d", &n);

	w = (unsigned int *)malloc( (n+1) * sizeof(unsigned int) );  //0号单元不用，所以构造n+1个结点 

	printf("Please enter the leaf's weight value of huffmantree\n");

	for(i = 1; i <= n; i++)

	{

		printf("please enter the value of %d: ",i);

		scanf("%d", &w[i]);

	}

	CreateHuffmanTree(&HT, w, n);

	HuffmanCode HC = NULL;   //用于存储多个字符串的二级指针 

	HuffmanTreeCoding(HT, &HC, n);  //因为要改变指针变量HC的指向，所以要讲HC的地址传入 

	for(int i = 1; i <= n; i++)

	{

		printf("%d : %s\n", w[i], HC[i]);

	}

	printf("\n");


	//PreOrderTraverse(HT, 2 * n);


	return 0; 

}


void CreateHuffmanTree(HuffmanTree *HT, unsigned int *w, int n)

{

	int m;

	int i,s1,s2;

	HuffmanTree p;

	if(n <= 1)

	{

		printf("parameter is illegal!"); //若结点个数小于等于1，则无法进行树的构造 

		return ;

	}

	m = 2 * n - 1; //构造霍夫曼树需要的结点总数

	*HT = (HuffmanTree)malloc( (m+1) * sizeof(HTNode) );

	//因为0号单元不用，所以m需要加一

	p = *HT;

	p++; // (*HT)[0]不用

	for(i = 0; i <= m; p++, i++)

	{

		p->weight = 0;

		p->parent = 0;

		p->lchild = 0;

		p->rchild = 0;

	} 

	p = *HT;

	p++;

	for(i=1; i<=n; p++, i++)

	{

		p->weight = w[i];

	}//存入权值，便于筛选 

	for(i = n+1; i <= m; i++)//0号单元未用，以用单元0~n,故 i=n+1 

	{

		Select(*HT, i-1, &s1, &s2);

		//从前i-1个分量中选择parent为０，且权值最小的两个结点，并取其下标给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; 

	}

}


void Select(HuffmanTree HT, int i, int *s1, int *s2)

{

	int k, j;

	HuffmanTree p;

	p = HT;

	k = 1;

	while(HT[k].parent != 0) k++;

	*s1 = k;

	for(j = 1; j <= i; j++)

	{

		if( (HT[j].parent == 0) && (HT[j].weight < HT[*s1].weight) )

           *s1 = j;

	}//寻找权值最小的结点 

	k = 1;

	while( (HT[k].parent != 0) || (k == *s1) )  k++;

	*s2 = k;

	for(j=1;j<=i;j++)

    {

    	if( (HT[j].parent == 0) && (HT[j].weight < HT[*s2].weight) && (j != *s1) )

           *s2 = j;

    } //寻找次小的结点 

}


void HuffmanTreeCoding(HuffmanTree HT, HuffmanCode *HC, int n)

{  

	int i,start;

	unsigned int c,f;

	char *cd = NULL;

	*HC = (HuffmanCode)malloc(n * sizeof(char *)); //构造字符指针类型的数组 

	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) );

		strcpy( (*HC)[i],&cd[start]);

	}

	free(cd);

}


void PreOrderTraverse(HuffmanTree HT, int length)

{

	HTNode stack[1000];

	int top = -1;

	HTNode p = HT[length - 1];

	while( p.weight != 0 || top != -1 )