网站软文代写,网站开发要什么基础,浙江建筑信息网查询,沧州国外网站建设定义 给定N个权值作为N个叶子结点#xff0c;构造一棵二叉树#xff0c;若该树的带权路径长度达到最小#xff0c;称这样的二叉树为最优二叉树#xff0c;也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树#xff0c;权值较大的结点离根较近。 基础知识
路…定义 给定N个权值作为N个叶子结点构造一棵二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二叉树也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树权值较大的结点离根较近。 基础知识
路径从树中的一个结点到另一个结点之间的分支构成这两点之间的路径路径长度路径上的分支数目称作路径长度树的路径长度从树根到每一个结点的路径长度之和权赋予某个实体的一个量结点的带权路径长度从该结点到树根之间的路径长度与结点上权的乘积 树的带权路径长度树中所有叶子结点的带权路径长度之和 哈夫曼编码跟 ASCII 编码有什么区别ASCII 编码是对照ASCII 表进行的编码每一个字符符号都有对应的编码其编码长度是固定的。而哈夫曼编码对于不同字符的出现频率其使用的编码是不一样的。其会对频率较高的字符使用较短的编码频率低的字符使用较高的编码。这样保证总体使用的编码长度会更少从而实现到了数据压缩的目的。 哈夫曼树的构造
假设有n个权值则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn则哈夫曼树的构造规则为
(1) 将w1、w2、…wn看成是有n 棵树的森林(每棵树仅有一个结点)
(2) 在森林中选出两个根结点的权值最小的树合并作为一棵新树的左、右子树且新树的根结点权值为其左、右子树根结点权值之和
(3)从森林中删除选取的两棵树并将新树加入森林
(4)重复(2)、(3)步直到森林中只剩一棵树为止该树即为所求得的哈夫曼树。
例如对 2346 这四个数进行构造 huffman存储结构就是采用二叉树存储方式中的一种静态存储二叉链表的静态结构 因为每次要找到序列中权值最小的进行合并所以在创建哈夫曼树时采用优先级队列每次取出最小值。 列表中由n个数据构建出来的哈夫曼树就有2*n - 1个节点 #include algorithm
#include cmath
#include cstddef
#include functional
#include ios
#includeiostream
#includevector
#includestring.h
#includestack
#includemath.h
#includecstring
#includequeue
using namespace std;const int n 8;
const int m 2 * n;
typedef unsigned int WeightType;
typedef unsigned int NodeType;typedef struct {WeightType weight;NodeType parent, leftchild, rightchild;
}HTNode;typedef HTNode HuffManTree[m];
typedef struct {char ch;char code[n 1];
}HuffManCode;
typedef HuffManCode Huffcode[n 1];void InitHuffManTree(HuffManTree hft, WeightType w[]){memset(hft, 0, sizeof(HuffManTree));for(int i 0; i n; i){hft[i 1].weight w[i];}
}
void PrintHuffManTree(HuffManTree hft){for(int i 1; i m; i){printf(index :%3d weight : %3d parent: %3d leftchild %3d rightchild %3d\n ,i, hft[i].weight, hft[i].parent, hft[i].leftchild, hft[i].rightchild);}printf(\n);
}
struct IndexWeight{int index;WeightType weight;operator WeightType() const {return weight;}
};
void CreateHuffManTree(HuffManTree hft){std::priority_queueIndexWeight, vectorIndexWeight, std::greaterIndexWeight qu;for(int i 0; i n; i){qu.push(IndexWeight{i, hft[i].weight});}int k n 1;while(!qu.empty()){if(qu.empty()) break;IndexWeight left qu.top();qu.pop();if(qu.empty()) break;IndexWeight right qu.top(); qu.pop();hft[k].weight left.weight right.weight;hft[k].leftchild left.index;hft[k].rightchild right.index;hft[left.index].parent k;hft[right.index].parent k;qu.push({k, hft[k].weight});k 1;}
}
void InitHuffManCode(Huffcode hc, const char * ch){memset(hc, 0, sizeof(HuffManCode));for(int i 1 ;i n; i){hc[i].ch ch[i -1];hc[i].code[0] \0;}
}void PrintHuffCode(Huffcode hc){for(int i 1; i n; i){printf(data : %c -code %s\n, hc[i].ch, hc[i].code);}printf(\n);
}
void CreateHuffCode(HuffManTree hft, Huffcode hc){char code[n 1] {0};for(int i 1; i n; i){int k n;code[k] \0;int c i;int pa hft[c].parent;while(pa ! 0){code[--k] hft[pa].leftchild c ? 0 : 1;c pa;pa hft[c].parent;}strncpy(hc[i].code, code[k], n);}
}
int main(){WeightType w[n] {5,29,7,8,14,23,3,11};char ch[n 1] {A,B, C, D, E, F, G, H};HuffManTree hft {0};Huffcode hc { 0};InitHuffManTree(hft, w);InitHuffManCode(hc, ch);PrintHuffManTree(hft);PrintHuffCode(hc);CreateHuffManTree(hft);CreateHuffCode(hft, hc);PrintHuffManTree(hft);PrintHuffCode(hc);return 0;
} 参考
https://blog.csdn.net/Initial_Mind/article/details/124354318
