网站注册和进入asp,网站开发的项目,建设企业网站开发公司,网站架设教程哈夫曼树
路径长度#xff1a;从树中一个结点到另一个结点之间的分支构成这两个节点之间的路径#xff0c;路径上的分支数目称为路径长度
树的带权路径长度#xff1a;树中所有叶子结点的带权路径长度之和#xff0c;通常记为WPL ∑ k 1 n w k l k \sum^{n}_{k1}w_kl_k …哈夫曼树
路径长度从树中一个结点到另一个结点之间的分支构成这两个节点之间的路径路径上的分支数目称为路径长度
树的带权路径长度树中所有叶子结点的带权路径长度之和通常记为WPL ∑ k 1 n w k l k \sum^{n}_{k1}w_kl_k ∑k1nwklk
带权路径长度最小的二叉树称为最优二叉树或哈夫曼树
注意
哈夫曼树不一定是完全二叉树
书中一定没有度为1的结点
树中权值最小的两个结点一定是兄弟
包含n个叶子节点的哈夫曼树共有2n-1个结点
包含n棵树的森林要经过n-1次合并才能形成哈夫曼树共形成n-1个新结点且度为2
树中任意非叶子节点的权值一定不小于下一层任意结点的权值
哈夫曼树的构造
哈夫曼算法
根据给定的权值构成n棵二叉树的森林每棵树只有一个带权为wi的根节点在森林中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树且设置新的二叉树的根节点的权值为其左右子树的权值和在森林中删除这两棵树同时将新得到的二叉树加入森林中重复23直到森林中只有一棵树为止这棵树即为哈夫曼树重复第二步时不一定选用新树
哈夫曼树的实现
采用顺序存储结构
typedef struct{int weight;int parent,lch,rch;
}HTNode,*HTree;void CreateHuffmanTree(HuffmanTree HT,int n){if(n1)return;m2*n-1;//数组共2n-1个元素HTnew HTNode[m1];//0号单元未用HT[m]表示根节点for(i1;im;i){ //将2n-1个元素的lch、rch、parent置为0HT[i].lch0;HT[i].rch0;HT[i].parent0;}for(i1;in;i)cinHT[i].weight;//输入前n个元素的weight值//初始化结束下面开始建立哈夫曼树for(in1;im;i){ //合并产生n-1个结点——构造Huffman树Select(HT,i-1,s1,s2);//在HT[k]中选择两个双亲域为0且权值最小的结点并返回它们在HT中的序号s1和s2HT[s1].parenti;HT[s2].parenti; //表示从F中删除s1、s2HT[i].lchs1; HT[i].rchs2; //s1,s2分别作为i的左右孩子HT[i].weightHT[s1].weightHT[s2].weight;//i的权值为左右孩子权值之和}
}哈夫曼编码
将编码设计为不等长的二进制编码让代传字符中出现次数较多的字符采用较短的编码
前缀编码任一个字符的编码都不是另一个字符的字符的编码的前缀
构造哈夫曼编码
将字符出现的频率作为权值构建哈夫曼树从根节点出发左分支标记0右分支标记1从根节点出发到叶子节点路过的所有分支的编码组合起来就是哈夫曼编码
