哈夫曼树性质
（1）路径长度：路径上的分支数目；（2）树的路径长度：树根到每一个结点的路径长度之和；
（3）树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为WPL = sum(Wk * Lk)；
哈夫曼树构造原理
（1）哈夫曼树的构造过程，典型的使用了 贪心算法，即我们总是选择n的权值集合中，两颗最小的权值作为左右子树成为一颗新的二叉树节点，并放入新的权值集合中，此时n变为n-1；
（2）重复过程1，直到n变为1；
（3）有上述构造的过程可知，哈夫曼树没有度为1的节点；若有n个叶子节点的哈夫曼树共有2n-1个结点；
哈夫曼树编码
（1）任何一个字符的编码都不是另一个字符的编码前缀，我们称为前缀编码；比如110不是011的前缀，11是110的前缀；
（2）将哈夫曼树的左右子树按照约定依次编号为0和1，即可得到一个编码树；
（3）对于上述哈夫曼树，给定的二进制序列如0111110010解码为ADCAB；而对于BDADCAB我们编码二进制序列为101110111110010；
完整代码
说明几点
（1）本代码使用双向链表形式进行对哈夫曼节点进行组织，将所有的链表中按节点值升序排序，每次只需要取链表的前两个节点，然后构造出一个新的节点，根据它的节点值插入到链表中，直到链表为只含一个节点为止；链表形式构造的哈夫曼树，时间复杂度为O(n*n)；
（2）在哈夫曼节点嵌入双向循环链表节点中，即使用Linux中典型的链表构造方式；
（3）输入：随机生成一组哈夫曼节点概率；（注：链表头结点可使插入的情况一致，否则还要有头结点插入的特殊情况）；
#include<stdlib.h> #include<stdio.h> #include<string.h> #include<time.h> #define offsetof(TYPE,MEMBER) ((size_t) &((TYPE *)0)->MEMBER) #define container_of(ptr,type,member)({\ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) char code[] = {'A','B','C','D','E','F','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V'}; struct ListHead { struct ListHead *next; struct ListHead *prev; }; struct HaffmanNode { int weight; struct HaffmanNode *left; struct HaffmanNode *right; struct ListHead list; }; int generateSequence(int *probability) { srand( (unsigned)time( NULL)); int count = 0; int sum = 100; while (true) { int temp = 1 << (rand() % 6); if (temp < sum) { probability[count++] = temp; sum -= temp; } else { probability[count++] = sum; break; } } return count; } void initListHead(struct ListHead *head) { head->next = head; head->prev = head; } struct ListHead* listQueryPiror(int weight,struct ListHead *head) { struct ListHead *node = head->next; while (node != head) { struct HaffmanNode *value = container_of(node,struct HaffmanNode,list); if (value->weight > weight) { return node->prev; } node = node->next; } return head->prev; } void listInsert(struct ListHead *node,struct ListHead *head) { struct ListHead *pos; if (head->prev == head) { pos = head; } else { struct HaffmanNode *temp = container_of(node,list); pos = listQueryPiror(temp->weight,head); } node->next = pos->next; node->prev = pos; pos->next->prev = node; pos->next = node; } void listDelete(struct ListHead *node) { node->next->prev = node->prev; node->prev->next = node->next; } void createHaffmanTree(struct ListHead *head) { while (head != head ->next->next) { struct HaffmanNode *value = (struct HaffmanNode *) malloc(sizeof(struct HaffmanNode)); if (value == NULL) break; struct HaffmanNode *temp = container_of(head->next,list); value->weight = temp->weight; value->left = temp; listDelete(&temp->list); temp = container_of(head->next,list); value->weight += temp->weight; value->right = temp; listDelete(&temp->list); listInsert(&value->list,head); } } struct ListHead * createHaffmanNode(int* probability,int num) { struct ListHead *head = (struct ListHead *)malloc(sizeof(struct ListHead)); initListHead(head); for (int i = 0; i < num; i++) { struct HaffmanNode *value = (struct HaffmanNode *)malloc(sizeof(struct HaffmanNode)); if (value == NULL) break; value->weight= probability[i]; value->left = NULL; value->right = NULL; listInsert(&value->list,head); } createHaffmanTree(head); return head; } void displayHaffmanTree(struct HaffmanNode *root,int level) { if (root != NULL) { displayHaffmanTree(root->left,level+1); printf("\n"); int i; for (i = 0; i < level -1; i++) printf(" "); printf("%.2f ",root->weight * 0.01); displayHaffmanTree(root->right,level+1); } } void printfSequence(int* probability,int num) { printf("------------------------\n"); printf("leaf node and probability as follows:\n"); for (int i = 0; i < num; i++) printf("%c----->%.2f\n",code[i],probability[i] * 0.01); } void freeHaffmanNode(struct HaffmanNode *node) { if (node !=NULL) { freeHaffmanNode(node->left); freeHaffmanNode(node->right); free(node); } } void freeMem(struct ListHead *head) { struct HaffmanNode *temp = container_of(head->next,list); free(head); freeHaffmanNode(temp); } int main(void) { int probability[100]; int num = generateSequence(probability); printfSequence(probability,num); struct ListHead* head = createHaffmanNode(probability,num); printf("\nhaff man list tree display as follows:\n"); displayHaffmanTree(container_of(head->next,list),1); printf("\n"); freeMem(head); return 0; }
输出
sykpour@sykpour:~/Desktop$ gcc -o test test.cc
sykpour@sykpour:~/Desktop$ ./test
------------------------
leaf node and probability as follows:
A----->0.01
B----->0.32
C----->0.32
D----->0.04
E----->0.04
F----->0.08
H----->0.19
haff man list tree display as follows:
0.08
0.17
0.04
0.09
0.01
0.05
0.04
0.36
0.19
1.00
0.32
0.64
0.32 原文链接：https://www.f2er.com/datastructure/382668.html