设有ABCDEF，6个数据项，其出现的频度分别为654321，构造一棵哈夫曼树，
时间：2026-02-25 15:13:00
浏览：829次
六个权值(频率)是 6 5 4 3 2 1(1) 从小到大排序 1 2 3 4 5 6 (这是有序序列)(2) 每次提取最小的两个结点,取结点1和结点2,组成新结点N3,其权值=1+2=3, 取数值较小的结点作为左分支,1为左分支,2为右分支.(3) 将新结点N3放入有序序列,保持从小到大排序: 3 N3 4 5 6 (注意,新结点N3要放在结点3的后面)(4) 重复步骤(2),提取最小的两个结点,结点3与N3组成新结点N6,其权值=3+3=6, 结点3与N3权值一样,但是,将结点3看成较小,所以,结点3作为左分支,N3就作为右分支.(5) 将新结点N6放入有序序列,保持从小到大排序: 4 5 6 N6 (注意,新结点N6要放在结点6的后面)(6) 重复步骤(2),提取最小的两个结点,结点4与结点5组成新结点N9,其权值=4+5=9, 4的数值较小,作为左分支,5就作为右分支.(7) 将新结点N9放入有序序列,保持从小到大排序: 6 N6 N9(8) 重复步骤(2),提取最小的两个结点,结点6与N6组成新结点N12,其权值=6+6=12, 结点6作为左分支,N6就作为右分支.(9) 将新结点N9放入有序序列,保持从小到大排序: N9 N12(10)重复步骤(2),提取剩下的两个结点,N9与N12组成新结点N21,其权值=9+12=21, 数值较小的N9作为左分支,N12就作为右分支. 有序序列已经没有结点,最后得到"哈夫曼树": N21 / \ N9 N12 / \ / \ 4 5 6 N6 / \ 3 N3 / \ 1 2 哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.从根结点N21到结点6,先经历右分支,后经历左分支,结点6的编码就是10从根结点N21到结点5,先经历左分支,后经历右分支,结点5的编码就是01从根结点N21到结点4,先后经历两次左分支,结点4的编码就是00从根结点N21到结点3,先经历两次右分支,最后经历左分支,结点3的编码就是110从根结点N21到结点2,先后经历四次右分支,结点2的编码就是1111从根结点N21到结点1,先经历三次右分支,最后经历左分支,结点1的编码就是1110得出所有结点的"哈夫曼编码":字符 A (频率6): 10字符 B (频率5): 01字符 C (频率4): 00字符 D (频率3): 110字符 E (频率2): 1111字符 F (频率1): 1110//C语言测试程序(来自其他网友)////输入构造哈夫曼树中带权叶子结点数(n)：6//输入6个整数作为权值：6 5 4 3 2 1//可以得出哈夫曼树的广义表形式,以及哈夫曼编码.#include#includetypedef int ElemType;struct BTreeNode{ ElemType data; struct BTreeNode* left; struct BTreeNode* right;};//1、输出二叉树，可在前序遍历的基础上修改。// 采用广义表格式，元素类型为intvoid PrintBTree_int(struct BTreeNode* BT){ if (BT != NULL) { printf("%d", BT->data); //输出根结点的值 if (BT->left != NULL || BT->right != NULL) { printf("("); PrintBTree_int(BT->left); //输出左子树 if (BT->right != NULL) printf(","); PrintBTree_int(BT->right); //输出右子树 printf(")"); } }}//2、根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针struct BTreeNode* CreateHuffman(ElemType a[], int n){ int i, j; struct BTreeNode **b, *q; b = malloc(n*sizeof(struct BTreeNode)); //初始化b指针数组，使每个指针元素指向a数组中对应的元素结点 for (i = 0; i < n; i++) { b[i] = malloc(sizeof(struct BTreeNode)); b[i]->data = a[i]; b[i]->left = b[i]->right = NULL; } for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树 { //k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标 int k1 = -1, k2; //让k1初始指向森林中第一棵树，k2指向第二棵 for (j = 0; j < n; j++) { if (b[j] != NULL && k1 == -1) { k1 = j; continue; } if (b[j] != NULL) { k2 = j; break; } } //从当前森林中求出最小权值树和次最小 for (j = k2; j < n; j++) { if (b[j] != NULL) { if (b[j]->data < b[k1]->data) { k2 = k1; k1 = j; } else if (b[j]->data < b[k2]->data) k2 = j; } } //由最小权值树和次最小权值树建立一棵新树，q指向树根结点 q = malloc(sizeof(struct BTreeNode)); q->data = b[k1]->data + b[k2]->data; q->left = b[k1]; q->right = b[k2]; b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置 b[k2] = NULL;//k2位置为空 } free(b); //删除动态建立的数组b return q; //返回整个哈夫曼树的树根指针}//3、求哈夫曼树的带权路径长度ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0{ if (FBT == NULL) //空树返回0 return 0; else { if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点 { printf("+ %d * %d ",FBT->data,len); return FBT->data * len; } else //访问到非叶子结点，进行递归调用， { //返回左右子树的带权路径长度之和，len递增 return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1); } }}//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0{ //定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一 static int a[10]; int i; //访问到叶子结点时输出其保存在数组a中的0和1序列编码 if (FBT != NULL) { if (FBT->left == NULL && FBT->right == NULL) { printf("权值为%d的编码：", FBT->data); for (i = 0; i < len; i++) printf("%d", a[i]); printf("\n"); } else //访问到非叶子结点时分别向左右子树递归调用， { //并把分支上的0、1编码保存到数组a的对应元素中， //向下深入一层时len值增1 a[len] = 0; HuffManCoding(FBT->left, len + 1); a[len] = 1; HuffManCoding(FBT->right, len + 1); } }}int main(){ int n, i; ElemType* a; struct BTreeNode* fbt; printf("输入构造哈夫曼树中带权叶子结点数(n)："); while(1) { scanf("%d", &n); if (n > 1) break; else printf("重输n值："); } a = malloc(n*sizeof(ElemType)); printf("输入%d个整数作为权值：", n); for (i = 0; i < n; i++) scanf(" %d", &a[i]); fbt = CreateHuffman(a, n); printf("广义表形式的哈夫曼树："); PrintBTree_int(fbt); printf("\n"); //printf("哈夫曼树的带权路径长度：\n"); //printf("="); //printf("\n=%d\n", WeightPathLength(fbt, 0)); printf("树中每个叶子结点的哈夫曼编码：\n"); HuffManCoding(fbt, 0); return 0;}
