构建哈夫曼树（哈夫曼树的构造规则是什么）

本文目录

• 哈夫曼树的构造规则是什么
• 数据结构 哈夫曼树在构造时 有顺序要求吗 比如左右子树的顺序要固定什么的 必须谁左谁右之类的
• 哈夫曼树怎么画
• 哈夫曼树的构造是什么
• 哈夫曼树的构造
• 二叉树实现符号不等长高效编码
• 怎样构建哈夫曼树 C语言大师帮帮忙

哈夫曼树的构造规则是什么

哈夫曼树的构造规则是若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

哈夫曼树的数据

为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下。

于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。

因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。

数据结构 哈夫曼树在构造时 有顺序要求吗 比如左右子树的顺序要固定什么的 必须谁左谁右之类的

Huffman树构造时，两个孩子原则上是没有左右之分的，当然，如果是考试，可能会约定左右子树的大小的。

节点按照权值排序的规则，例如两个原始节点或者一个原始节点和一个新建节点，具有相同的权值时，需要统一序列中的前后顺序(序列中的前后顺序也就是确定哪个是左子节点和右子节点)，目的仍然是满足构造出的哈夫曼树具有相同的结构#include《stdio.h》

#include《iostream》

#define INF 0x3f3f3f3f

#define MALL (Bithrnode *)malloc(sizeof(Bithrnode));

typedef struct

{

int weight;

int parent, lchild, rchild;

}HTNode, *Huffmantree;

void Select(Huffmantree HT, int n, int &x1, int &x2)// 查找前n个结点的最小权值的下标下x1、x2；

{

int min1 = INF;

int min2 = INF;

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

int m = 2*n-1;

for(int i=1; i《=2*n-1; ++i)

cout 《《 "结点序号 " 《《 i;

cout 《《 " 权重 " 《《 HT.weight;

cout 《《 " parent " 《《 HT.parent;

cout 《《 " Lchild " 《《 HT.lchild;

cout 《《 " Rchild " 《《 HT.rchild 《《 ’\n’;

int main()

{

Huffmantree HT;

cout 《《 "开始构建哈夫曼树" 《《 ’\n’;

cout 《《 "请输入哈夫曼树的叶子结点的个数： ";

int n;

cin 》》 n;

cout 《《 "请输入每个叶子结点的权值: " 《《 ’\n’;

CreatHuffmantree(HT, n);

print(HT, n);

return 0;

}

扩展资料：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

哈夫曼树怎么画

1、先准备一组数字，以1、7、3、4、9、8为例。

2、对这一组数字进行从小到大的规则排序，排序后为1、3、4、7、8、9。

3、在这些数字中，选择两个最小的数字。

4、用类似树杈的“树枝”连接两个最小的数，在顶点处计算出这两个数字的和，比较剩下的数字和这个和的大小，再取出两个最小的数字进行排序。

5、若两个数的和正好是下一步两个最小数其中一个，那么这个树直接往上生长。若两个数的和比较大，不是下一步两个最小数其中一个，那么就并列生长。

6、继续用倒V型的树杈，向上延伸，算出最后一个结果，就证明哈夫曼树构建成功。

哈夫曼树的构造是什么

哈夫曼树构造：结构化的Huffman算法生成的Huffman树子树都是有序的，所以一般生成Huffman树时都为节点排序，即使这样结果也不唯一。

哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。

历史

1951年，哈夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。

导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。

哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。

1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。

哈夫曼树的构造

第一步：排序 2 4 5 9第二步：挑出2个最小的 2 4 为叶子构造出 62 4第三步：判断 6 不大于 5或9（剩余叶子中最小的2个）=》 同方向生长，得出： 11 6 52 4第四步：继续生长 20 11 9 6 5 2 4权值为 2*3+4*3+5*2+9*1=37也可以20+11+6=37例题：6、13、18、30、7、16排序 6 7 13 16 18 30 13 6 7 26 26大于16或18 =》分支生长 13 13 6 7 26 34 13 13 16 18 6 7此时最小的2个数为 26 30 得出 56 34 26 30 16 18 13 136 7最后得出 90 56 34 26 30 16 18 13 13 6 7 权值 21990+56+26+13+34 or 6*4+7*4+13*3+30*2+16*2+18*2

二叉树实现符号不等长高效编码

二叉树中的最优二叉树（也就是哈夫曼树）可以实现符号不等长高效编码。

哈夫曼树（最优二叉树）：就是将二叉树的WPL降到最低（WPL最小的二叉树）。当用n个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则：权重越大的结点离树根越近。

哈夫曼树构造的编码中，最主要的是“如何选择两个最小的结点？”。可以利用堆来解决，把结点的权值构造成最小堆，从里面挑两个最小的。当然也可以用排序的方法来选择两个最小的结点，但是排序的方法效率不如堆。构建哈夫曼树时，首先需要确定树中结点的构成。

哈夫曼树的特点

1、没有度为1的结点。

2、n个叶子结点的哈夫曼树公有2n-1个结点。

3、哈夫曼树的任意非叶结点的左、右子树互换后，还是哈夫曼树。

4、同一组权值，可能存在不同构的哈夫曼树。

怎样构建哈夫曼树 C语言大师帮帮忙

/********************************************************** 我也贴个现成的，这个是以前上课用的示范代码，有注释* 另外，像《malloc.h》、《conio.h》这种非标准头文件最好不要用**********************************************************//* huffman树的构造方法*/#include《stdlib.h》#include《stdio.h》#define MAXINT 2147483647#define MAXNUM 50 /* 数组w中最多容纳的元素个数，注意 m《=MAXNUM */#define MAXNODE 100 /* 哈夫曼树中的最大结点数，注意 2*m-1《MAXNODE */struct HtNode { /* 哈夫曼树结点的结构 */ int ww; int parent,llink,rlink;};struct HtTree { int root;/* 哈夫曼树根在数组中的下标*/ struct HtNode ht;};typedef struct HtTree *PHtTree; /* 哈夫曼树类型的指针类型 *//* 构造具有m个叶结点的哈夫曼树*/PHtTree huffman(int m, int *w) { PHtTree pht; int i, j, x1, x2, m1, m2; pht = (PHtTree)malloc(sizeof(struct HtTree)); /* 创建空哈夫曼树 */ if (pht == NULL) { printf("Out of space!! \n"); return pht; } for (i = 0; i 《 2*m-1; i++) {/* 置初态 */ pht-》ht.llink = -1; pht-》ht.rlink = -1; pht-》ht.parent = -1; if (i 《 m) pht-》ht; else pht-》ht.ww = -1; } for ( i = 0; i 《 m-1; i++) {/* 每循环一次构造一个内部结点 */ m1 = MAXINT; m2 = MAXINT;/* 相关变量赋初值 */ x1 = -1; x2 = -1; for (j = 0; j 《 m+i; j++) /* 找两个最小权的无父结点的结点 */ if (pht-》ht.parent == -1) { m2 = m1; x2 = x1; m1 = pht-》ht.ww; x1 = j; } else if (pht-》ht.parent == -1) { m2 = pht-》ht.ww; x2 = j; } pht-》ht.parent = m+i; /* 构造一个内部结点 */ pht-》ht.parent = m+i; pht-》ht.ww = m1+m2; pht-》ht.llink = x1; pht-》ht.rlink = x2; pht-》root = m+i; } return pht;}int main() { int m = 0, j = 0, i = 0, parent = 0; int* w; PHtTree pht; printf("please input m = ");/*输入外部结点个数*/ scanf("%d", &m); if (m 《 1) { printf("m is not reasonable!\n"); return 1; } w = (int *)malloc(sizeof(int)*m); if (w == NULL) { printf("overflow!\n"); return 1; } printf("please input the %d numbers：\n",m);/*输入权值*/ for (j = 0; j 《 m; j++) scanf("%d", w+j); pht = huffman(m, w); for (j = 0; j 《 m; j++) { printf("the Reverse code of the %d node is:", j+1);/*得到的编码应倒过来*/ i = j; while (pht-》ht.parent != -1) { parent = pht-》ht.parent; if (pht-》ht.llink == i) printf("0"); else printf("1"); i = parent; } printf("\n"); } return 0;}