哈夫曼树的建立 [ 标签：哈夫曼,建立 ] 数据结构课程设计题目 - -~ 哈夫曼树的建立 任务：建立最优二叉树函数 要求：可以建立函数输入二叉树，并输出其哈夫曼树 2010、加油 回答:3 人气:10 解决时间:2010-02-04 18:25 满意答案 好评率：0% 给你个大概的代码，把显示跟调用那里改改 #include #include #include #include typedef struct { unsigned int weight; unsigned int parent,lchild,rchild,ch; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 int m,s1,s2; HuffmanTree HT; void Select(int n){ //选择两个权值最小的结点 int i,j; for(i=1;i<=n;i++){ if(!HT[i].parent){ s1 = i;break; } } for(j=i+1;j<=n;j++){ if(!HT[j].parent){ s2 = j;break; } } for(i=1;i<=n;i++){ if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i)){ s1=i; } } for(j=1;j<=n;j++){ if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j)){ s2=j; } } } void HuffmanCoding(HuffmanCode HC[], int *w, int n) { // w存放n个字符的权值(均>0)，构造哈夫曼树HT， // 并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen; int start; if (n<=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 for (i=1; i<=n; i++) {//初始化 HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; HT[i].ch=0; } for (i=n+1; i<=m; i++) {//初始化 HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; HT[i].ch=0; } for (j=1,i=n+1; i<=m; i++,j++) { // 建哈夫曼树 // 在HT[1..i-1]中选择parent为0且 weight最小的两个结点， // 其序号分别为s1和 s2 Select(i-1); 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; HT[i].ch=j; } //-----从叶子到根逆向求每个字符的哈夫曼编码 cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i){ start=n-1; HT[i].ch=i; for(unsigned...
