路径和路径长度
路径:在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路。结点的路径长度:从一个结点到另一个结点的路径上分支的数目。结点的权及带权路径长度
结点的权:将树中结点赋予一个有着某种含义的数值。结点的带权路径长度:从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度
树中所有叶子结点的带权路径长度之和。赫夫曼树( Huffman tree )
带权路径长度达到最小的二叉树即为赫夫曼树。在所有含 n 个叶子结点、并带相同权值的二叉树中,必存在一棵其带权路径长度取最小值的树,称为“最优二叉树”。构造 Huffman tree基本思想:使权大的结点靠近根根据给定的 n 个权值 {w1, w2, …, wn},构造 n 棵二叉树的集合F = {T1, T2, … , Tn},其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树;在 F 中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
从F中删去这两棵树,同时加入刚生成的新树;
重复上述两步,直至 F 中只含一棵树为止。哈夫曼构造算法实现一棵有 n 个叶子结点的Huffman树有 2n-1 个结点采用顺序存储结构---一维结构数组结点类型定义
typedef struct { ElemType elem; // 结点值 int weight; // 权值 int parent, lch, rch; }HTNode, *HuffmanTree;
构造HuffmanTree
输入初始n个叶子结点:置HT[1..n]的weight值进行以下n-1次合并,依次产生HT[i],i=n+1..2n-1:
在HT[1..i-1]中选两个未被选过的weight最小的两个结点HT[s1]和HT[s2] (从parent = 0 的结点中选)修改HT[s1]和HT[s2]的parent值: parent=i置HT[i]:weight=HT[s1].weight + HT[s2].weight ,lch=s1, rch=s2Status CreatHuffmanTree(HuffmanTree HT, int n){ if (n = 1) // 结点数量不合法 return ERROR; int m = 2 * n - 1; int i; int s1, s2; HT = new HTNode[m + 1]; // 0号单元未用,HT[m]表示根结点 for (i = 1;i ++i) { HT[i].lch = 0; HT[i].rch = 0; HT[i].parent = 0; for (i = 1;i ++i) // 输入权值 cin HT[i].weight; for (i = n + 1;i ++i) { // 构造Huffman树 Select(HT, i - 1, s1, s2); // 在HT[k](1≤k≤i-1)中选择两个其双亲域为0, 且权值最小的结点, 并返回它们在HT中的序号s1和s2 if (s1 != 0 s2 != 0) { HT[s1].parent = i; HT[s2].parent = i; //表示从F中删除s1,s2 HT[i].lch = s1; HT[i].rch = s2; //s1,s2分别作为i的左右孩子 HT[i].weight = HT[s1].weight + HT[s2].weight; //i 的权值为左右孩子权值之和 return OK; }哈夫曼树的应用哈夫曼编码
算法实现
Status CreatHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) { if (n = 1) return ERROR; int start, i; int f = 0, c; HC = new char* [n + 1]; char* cd = new char[n]; cd[n - 1] = '0'; for (i = 1; i ++i) { while (f != 0) { // 从叶子结点开始向上回溯,直到根结点 start = n - 1; c = i; f = HT[i].parent; if (HT[f].lch == 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; cd = NULL; return OK; }
重要结论
哈夫曼编码是不等长编码哈夫曼编码是前缀编码,即任一字符的编码都不是另一字符编码的前缀哈夫曼编码树中没有度为1的结点。若叶子结点的个数为n,则哈夫曼编码树的结点总数为 2n-1发送过程:根据由哈夫曼树得到的编码表送出字符数据接收过程:按左0、右1的规定,从根结点走到一个叶结点,完成一个字符的译码。反复此过程,直到接收数据结束【51CTO.com原创稿件】近年来,大数据、云计算、人工智能和区块链等技术如雨后春...
参考数据管理是对定义的数据值域进行控制,包括对标准化术语、代码值和其他唯一...
互联网的快速发展,人们对于网络的应用越来越广泛,特别是一些个人或企业都纷纷...
大家好,我是小富~ 最近发现点好玩的工具,迫不及待的想跟大家分享一下。 大家平...
云原生计算基金会(Cloud Native Computing Foundation,CNCF)已发布了第三次中国...
大数据可视化是进行各种大数据分析解决的最重要组成部分之一。 一旦原始数据流被...
往期分享RDS MySQL RDS MySQL 实例空间问题 RDS MySQL 内存使用问题 RDS MySQL ...
怎么在 虚拟主机 安装wordpress?有不少用户都想知道虚拟主机怎么安装wordpress...
编程开发技术这几年发展速度非常迅猛,每一年技术方面的发展趋势都会发生迅速的...
在Java中异步编程,不一定非要使用rxJava, Java本身的库中的CompletableFuture可...