这篇文章主要为大家详细介绍了C++实现哈夫曼树的方法，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
序言
对于哈夫曼编码，个人的浅薄理解就是在压缩存储空间用很大用处。
用一个很简单例子，存储一篇英文文章时候，可能A出现的概率较大，Z出现的记录较小，如果正常存储，可能A与Z存储使用的空间一样。但是用哈夫曼编码方式，A经常出现，所用编码长度就短。
构造哈夫曼树，生成哈夫曼编码
一、定义节点类型
struct Node { char C; long key; Node *Left, *Right,*parent; Node() { Left = Right = NULL; } };
二、定义树类型（节点数组）
三要素：不定长数组，元素大小，有效元素个数
struct RootA { Node *NodeA; const int Size; int n; RootA(int Size) :Size(Size) { n = 0; NodeA = new Node[Size]; } ~RootA() { delete[]NodeA; } };
三、创建哈夫曼树
1.将每一个节点都当成一棵树，初始化数组大小，并进行赋值
RootA RA(4); //1.在RA.NodeA中存入字母和权值 for (RA.n = 0;RA.n <RA.Size;RA.n++) { cout <> RA.NodeA[RA.n].C; cout <> RA.NodeA[RA.n].key; }
2.将树按权值大小排序
void Sort(RootA *ra) { for (int i = 0;i n;i++) { bool ESC = false; for (int j = 0;j n - i - 1;j++) { if (ra->NodeA[j].key > ra->NodeA[j + 1].key) { Node T;T = ra->NodeA[j];ra->NodeA[j] = ra->NodeA[j + 1];ra->NodeA[j + 1] = T; ESC = true; } } if (!ESC) return; } }
3.(1)遍历数组，将RA.NodeA[0]和RA.Node[1]合并，其余向前移动，重新排序
(2)将RA.NodeA[0]，RA.NodeA[1]分别放在新合并的RA.NodeA[0]的左右子结点中
while (RA.n > 1) { //1.将RA.NodeA[0]和RA.NodeA[1]合并，将其余向前移动 Node *NewNode0 = new Node; *NewNode0 = RA.NodeA[0]; Node *NewNode1 = new Node; *NewNode1 = RA.NodeA[1]; RA.NodeA[0].C = ' '; RA.NodeA[0].key = RA.NodeA[0].key + RA.NodeA[1].key; RA.NodeA[0].Left = NewNode0; NewNode0->parent = &RA.NodeA[0]; RA.NodeA[0].Right = NewNode1; NewN<div style="color:transparent">来源gaodai.ma#com搞##代!^码网</div>ode1->parent = &RA.NodeA[0]; for (int i = 1;i <RA.n-1;i++) { RA.NodeA[i] = RA.NodeA[i + 1]; } RA.n = RA.n - 1; //2.排序 Sort(&RA); }
4.输出哈夫曼编码
递归，找到叶子节点，记录路径，左记录0，右记录1，直到输出所有叶子节点
void CrateCode(Node *t,string &s) { //1.遍历节点，遍历左节点编码为0,右节点则为1，递归，直到输出所有叶子节 if (t->Left != NULL && t->Right != NULL) { s.push_back('0'); CrateCode(t->Left, s); s.pop_back(); s.push_back('1');CrateCode(t->Right, s); s.pop_back(); } else { cout << "哈夫曼编码："; cout <C << ":" << s<<endl; } }
以上是对构造哈夫曼树以及生成哈夫曼编码的总结，希望对你们有所帮助！
以上就是C++实现哈夫曼树的方法的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C++实现哈夫曼树的方法
转载请注明原文链接：C++实现哈夫曼树的方法
