题目描述 给定n个字符的权值(权值均是大于0的正整数)，构造赫夫曼树HT，并求出这n个字符的赫夫曼编码HC。 注意：构造赫夫曼树HT时，在将2棵二叉树合并成一棵新的二叉树时，将根结点权值小的用作左子树！ 输入 先输入权值的个数n（n>1）。 然后依次输入n个权值（权值均是大于0的正整数） 输出 与输入的n个权值相对应，依次输出对应的编码。 编码时，左孩子分支编码为0，右孩子分支编码为1。 样例输入 Copy 8 5 29 7 8 14 23 3 11 样例输出 Copy 0001 10 1110 1111 110 01 0000 001
#include <cstdio> #include <iostream> #include <cstring> using namespace std; typedef struct { int weight; int parent, lchild, rchild; } HTNode, *HuffmanTree; typedef char **HuffmanCode; void Select(HuffmanTree HT, int k, int &s1, int &s2) { int min1 = 9999999, min2 = 9999999; for(int i=1;i<=k;i++) { if(HT[i].weight<min1&&HT[i].parent==0) { min1 = HT[i].weight; s1 = i; } } int temp = HT[s1].weight; HT[s1].weight = 9999999; for(int i=1;i<=k;i++) { if(HT[i].weight<min2&&HT[i].parent==0) { min2 = HT[i].weight; s2 = i; } } HT[s1].weight = temp; if(HT[s1].weight>HT[s2].weight) { temp = s1; s1 = s2; s2 = temp; } } void CreatHT(HuffmanTree &HT, int n) { if(n<=1) return; int m = 2*n-1; HT = new HTNode[m+1]; for(int i=1;i<=m;i++) { HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; } for(int i=1;i<=n;i++) cin>>HT[i].weight; for(int i=n+1;i<=m;i++) { int s1 = 0, s2 = 0; 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; } } void CreadHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) { HC = new char*[n+1]; char *cd; cd = new char[n]; cd[n-1] = '\0'; int start, c, f; for(int i=1;i<=n;i++) { start = n-1; c = i; f = HT[i].parent; while(f!=0) { --start; if(HT[f].lchild==c) cd[start] = '0'; else cd[start] = '1'; c = f; f = HT[f].parent; } HC[i] = new char[n-start]; strcpy(HC[i], &cd[start]); } delete cd; } int main() { int n; scanf("%d", &n); HuffmanTree HT; HuffmanCode HC; CreatHT(HT, n); CreadHuffmanCode(HT, HC, n); for(int i=1;i<=n;i++) { cout<<HC[i]<<endl; } return 0; }