想了解Java数据结构之哈夫曼树概述及实现的新动态吗？本文将为您提供详细的信息，我们还将为您解答关于java哈夫曼树的相关问题，此外，我们还将为您介绍关于c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字
想了解Java数据结构之哈夫曼树概述及实现的新动态吗？本文将为您提供详细的信息，我们还将为您解答关于java 哈夫曼树的相关问题，此外，我们还将为您介绍关于c++ 实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）、c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）、C++数据结构与算法之哈夫曼树的实现方法、C++数据结构之文件压缩（哈夫曼树）实例详解的新知识。
本文目录一览：- Java数据结构之哈夫曼树概述及实现（java 哈夫曼树）
- c++ 实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）
- c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）
- C++数据结构与算法之哈夫曼树的实现方法
- C++数据结构之文件压缩（哈夫曼树）实例详解
Java数据结构之哈夫曼树概述及实现（java 哈夫曼树）
文中详细讲了关于Java哈夫曼树的概述以及用Java实现的方法,对各位正在学习java数据结构的小伙伴们有很大的帮助哟,需要的朋友可以参考下
目录
一、与哈夫曼树相关的概念
二、什么是哈夫曼树
三、哈夫曼树的构造方法
四、哈夫曼树的代码实现
一、与哈夫曼树相关的概念
概念
含义
1. 路径
从树中一个结点到另一个结点的分支所构成的路线
2. 路径长度
路径上的分支数目
3. 树的路径长度
长度从根到每个结点的路径长度之和
4. 带权路径长度
结点具有权值, 从该结点到根之间的路径长度乘以结点的权值, 就是该结点的带权路径长度
5. 树的带权路径长度
树中所有叶子结点的带权路径长度之和
二、什么是哈夫曼树
定义:
给定n个权值作为n个叶子结点, 构造出的一棵带权路径长度(WPL)最短的二叉树,叫哈夫曼树(), 也被称为最最优二叉树.
WPL: Weighted Path Length of Tree 树的带权路径长度
哈夫曼树的特点:
1.权值越大的结点, 距离根节点越近;
2.树中没有度为1的结点, 哈夫曼树的度只能是0 或 1;
3.带权路径长度最短的一棵二叉树;
判断下图三个二叉树那个是哈夫曼树?
当然是WPL最小的树啦, 即中间的二叉树是也;
那么我们是如何手动构造出一棵哈夫曼树的呢?
三、哈夫曼树的构造方法
构造哈夫曼树的步骤:
1.把所有结点的权值按照从小到大的顺序进行排序;
2.取出根节点权值最小的两棵二叉树;
3.组成一棵新的二叉树, 这课新二叉树的根节点的权值是前面两棵二叉树权值的和
4.再将这棵新的二叉树,以根节点的权值大小进行排序, 不断重复1-2-3-4的步骤, 直到给定序列中的所有权值都被处理,我们就得到了一棵哈夫曼树.
[图解分析构造过程]
下面以序列{13,7,8,3}为例, 图解构造哈夫曼树的过程
首先对序列进行升序排列,得到{3,7,8,13};
取出权值最小的两个结点3,7 , 组成一棵二叉树,根节点是权值为10的结点;
在原序列中去除步骤2中已经被使用了的3和7, 并把新的结点权值10加入到序列中并重新排序, 得到{8,10,13};
再次取出权值最小的两个节点8,10, 组成一棵根节点为18的二叉树, 然后我们去除序列中的8,10, 将18添加到序列中并排序, 得到了{13,18};
将序列{13,18}取出构成一棵新的二叉树, 权值为31, 此时序列中只剩下了31这个结点, 他是这个哈夫曼树的根节点;
至此, {13,7,8,3}的哈夫曼树构建完毕.
四、哈夫曼树的代码实现
结点类
package DataStrcture.huffmantreedemo; public class HTreeNode implements Comparable{ // public HTreeNode leftNode; public HTreeNode rightNode; public int weight; // 前序遍历 public void preOrder(){ System.out.println(this); if(this.leftNode != null) this.leftNode.preOrder(); if(this.rightNode != null) this.rightNode.preOrder(); } // 设置左右子节点 public void setLeftNode(HTreeNode node){ this.leftNode = node; } public void setRightNode(HTreeNode node){ this.rightNode = node; } //构造方法和toString() public HTreeNode(int weight){ this.weight = weight; } public String toString(){ return "Node{weight: "+weight+"}"; } //根据权值对结点进行排序 // public int compareto(Object obj){ // return this.weight - ((HTreeNode)(obj)).weight; // } public int compareto(HTreeNode node){ return this.weight - node.weight; } }
哈夫曼树类
package DataStrcture.huffmantreedemo; import java.util.ArrayList; import java.util.Collections; public class HuffmanTree{ //哈夫曼树的实现: //1. 构建哈夫曼树的方法 buildHuffumanTree(int[] arr) //2. 对哈夫曼树进行遍历(二叉树遍历) public static void main(String[] args) { int[] arr = {13,7,8,3,29,6,1}; HTreeNode hTreeNode = buildHuffmanTree(arr); preOrder(hTreeNode); } public static HTreeNode buildHuffmanTree(int[] arr){ // ArrayList nodesList = new ArrayList(); //1. 把存放权值的数组拿出来构建结点 //2. 把这些节点存放到集合中 for(int x : arr){ nodesList.add(new HTreeNode(x)); } while(nodesList.size() > 1){ //3. 利用集合的排序方法,可以根据权值对结点进行排序 Collections.sort(nodesList); // (当然了, 我们需要实现comparable接口中的copareto方法), 在哪实现的? 在结点类中! //4. 不断的循环从集合中取出两个结点进行相加, 直到集合中只剩下一个结点才会终止循环 HTreeNode leftNode = nodesList.get(0); HTreeNode rightNode = nodesList.get(1); HTreeNode parent = new HTreeNode(leftNode.weight + rightNode.weight); 建立父节点和左右子节点的关系(千万不要忘了) //因为我们虽说是父节点和左右子节点, 还是要实实在在的于内存中体现出来的哈 parent.setLeftNode(leftNode); parent.setRightNode(rightNode); //5.从结合中移除用过的左右子节点, 添加父节点进去 nodesList.remove(leftNode); nodesList.remove(rightNode); nodesList.add(parent); } //6. 返回一个最终的唯一结点 return nodesList.get(0); } //前序遍历哈夫曼树 public static void preOrder(HTreeNode root){ if(root != null){ root.preOrder(); }else{ System.out.println("二叉树为空! "); } } }
到此这篇关于Java数据结构之哈夫曼树概述及实现的文章就介绍到这了,更多相关Java哈夫曼树内容请搜索小编以前的文章或继续浏览下面的相关文章希望大家以后多多支持小编！
c++ 实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
using namespace std;
//定义哈夫曼树存储结构
typedef struct
{
char data; //存放结点数据
int weight; //记录结点权值
int parent, lchild, rchild;
}HTNode, * HuffmanTree;
//哈夫曼编码存储表示
typedef char** HuffmanCode; //动态分配数组储存哈夫曼编码表
//初始化
HuffmanTree InitHuffman(HuffmanTree& HT, int n)
{
if (n < 0)
{
cout << "输入初态结点数目不正确！！！" << endl;
return NULL;
}
else
{
int m = 2 * n - 1; //n个叶子结点的哈夫曼树有2n-1个结点
HT = new HTNode[m + 1]; //0号单元未用，申请m+1个空间
for (int i = 1; i <= m; i++)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].weight = 0;
HT[i].data = ''-'';
}
//输入初始数据，为了方便理解HT[0]不存放数据
cout << "请输入初态结点数据及相应权值（格式形式：a 3）：";
for (int i = 1; i <= n; i++)
{
cin >> HT[i].data;
cin >> HT[i].weight;
}
return HT;
}
}
//打印HT
void PrintState(HuffmanTree& HT, int n)
{
int m = 2 * n - 1; //总结点数
cout << "结点i\tdata值\tweight\tparent\tlchild\trchild" << endl;
for (int i = 1; i <= m; i++)
{
cout << setw(3) << i << "\t";
cout << setw(4) << HT[i].data << "\t";
cout << setw(4) << HT[i].weight << "\t";
cout << setw(4) << HT[i].parent << "\t";
cout << setw(4) << HT[i].lchild << "\t";
cout << setw(4) << HT[i].rchild << "\t" << endl;
}
}
//选择双亲域为0且两权值最小的结点，选择范围为1到i-1
int* Select(HuffmanTree& HT, int n, int* Idx)
{
int MIN, MinSecond;
//打擂台法使权最小值和次权最小值最大（假设第一个值权值最小无法进行）
MIN = MinSecond = 99999;
//循环从1到n次
for (int i = 1; i <= n; i++)
{
//如果双亲为0（未删除结点与新生成结点），一定会执行if语句,寻找权最小值
if ((HT[i].parent == 0) && HT[i].weight < MIN)
{
//将最小的权值给MinSecond方便寻找次最小值
MinSecond = MIN;
MIN = HT[i].weight;
//记录权最小值下标
Idx[0] = i;
}
//否则如果满足条件寻找次最小值
else if ((HT[i].parent == 0) && HT[i].weight < MinSecond)
{
MinSecond = HT[i].weight;
//记录权次最小值下标
Idx[1] = i;
}
}
return Idx;
}
//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree& HT, int n)
{
if (n <= 1)
return;
int m = 2 * n - 1; //n个叶子结点的哈夫曼树有2n-1个结点
//从n+1开始构造哈弗曼树
for (int i = n + 1; i <= m; i++)
{
//Idx用于存放两个返回最小权值的下标，i-1为前n个结点，后面随着i增加，n也增加
int* Idx = Idx = new int[2];
Idx = Select(HT, i - 1, Idx);
int s1 = Idx[0]; //权最小值下标
int s2 = Idx[1]; //权次最小值下标
//给两权值最小的结点置双亲,使s1，s2结点不在录入Select范围
HT[s1].parent = i;
HT[s2].parent = i;
//给新节点i左右孩子置位s1,s2
HT[i].lchild = s1;
HT[i].rchild = s2;
//给新结点赋权值
HT[i].weight = HT[s1].weight + HT[s2].weight;
delete[]Idx;
}
}
//哈夫曼编码
void CreateHuffmanCode(HuffmanTree& HT, HuffmanCode& HC, int n)
{
HC = new char* [n + 1]; //分配字符的空间
char* TempCode = new char[n]; //分配临时编码表空间n个
TempCode[n - 1] = ''\0''; //编码有叶子结点开始逆序存放，先将末尾结束符标志打上，为后序strcpy
//for循环逐个逆序求叶子结点的哈夫曼编码
for (int i = 1; i <= n; i++)
{
int start = n - 1; //开始存放的起点指向末尾，用于后面HC拷贝是的起始地址
int NodeIdx = i; //NodeIdx最开始存放叶子结点序号
int ParentsIdx = HT[i].parent; //Parents指向其双亲结点序号
//若有双亲则由下到上进行编码，编码的字符，从序号1开始
while (ParentsIdx)
{
start--; //在一维数组末尾，strat先指向最后
//若双亲结点的左结点序号为NodeIdx，将0打入一维临时数组中，否则打入1
if (HT[ParentsIdx].lchild == NodeIdx)
TempCode[start] = ''0'';
else
TempCode[start] = ''1'';
//结点的序号更新，进入上一层
NodeIdx = ParentsIdx;
ParentsIdx = HT[NodeIdx].parent;
}
//临时一维数组存放编码成功，开始用HC顺序存放字符编码
HC[i] = new char[n - start]; //为序号为i的字符分配编码空间
strcpy_s(HC[i], n - start, &TempCode[start]); //编码字符串拷贝strcpy报错因为没有指定长度
}
//打印哈夫曼编码
cout << "---字符对应编码----" << endl;
for (int i = 1; i <= n; i++)
{
cout << HT[i].data << "\t\t" << HC[i] << endl;
}
delete []TempCode;
}
//输入字符打印哈夫曼编码
void PrintCode(HuffmanTree & HT, HuffmanCode & HC, int n)
{
char *str =new char[100]; //存储需要解码的字符
int flag = 0; //flag用于检查输入是否错误
cout << "请输入需要编码的字符：";
cin >> str;
//匹配字符并打印相应的哈夫曼编码
cout << "输入的字符哈夫曼编码为：";
for (int j = 0; j < strlen(str); j++)
{
flag = 0;
for (int i = 1; i <= n; i++)
{
//匹配成功打印编码
if (HT[i].data == str[j])
{
cout << HC[i] ;
flag = 1; //匹配成功
}
}
//如果有匹配失败的情况，则跳出循环
if (flag == 0)
{
cout << "\n第" << j+1 << "字符输入错误!" ;
break;
}
}
putchar(10);
delete []str; //释放str空间
}
//哈夫曼解码并打印
void HuffmanDecode(HuffmanTree& HT, int n)
{
char* str = new char[1024];
cout << "请输入二进制编码：";
cin >> str;
int flag = 0; //用于检查二进制编码是否输入错误
cout << "解码对应字符为：";
//遍历二进制编码
for (int i = 0; i < strlen(str);)
{
int Root = 2 * n - 1; //Root为根结点序号
//当结点的左右孩子不为空时进入循环，由根结点进入
while (HT[Root].lchild && HT[Root].rchild)
{
if (str[i] == ''0'')
Root = HT[Root].lchild;
else if (str[i] == ''1'')
Root = HT[Root].rchild;
else
{
cout << "输入的二级制编码有误！" << endl;
flag = 1;
break;
}
i++; //相后读取二进制编码，i值更新
}
//如果找到错误跳出循环
if (flag)
break;
//打印编码对应字符
cout << HT[Root].data;
}
delete []str;
}
int main()
{
int n;
cout << "请输入哈夫曼树初态结点数：";
cin >> n;
//初始化哈夫曼树
HuffmanTree HT = InitHuffman(HT, n);
//打印HT初态
cout << "--------------------HT初态--------------------" << endl;
PrintState(HT, n);
//构造哈夫曼树
CreateHuffmanTree(HT, n);
//打印HT终态
cout << "--------------------HT终态--------------------" << endl;
PrintState(HT, n);
HuffmanCode HC;
//哈夫曼编码-由下而上
CreateHuffmanCode(HT, HC, n);
//打印字符对应编码
PrintCode(HT, HC, n);
//哈夫曼解码并打印-由上而下
HuffmanDecode(HT, n);
return 0;
}// 由于编译器版本原因 strcpy 出现不安全原因，导致无法运行，后使用 strcpy_s 给予拷贝长度得到解决；把 “==” 写成 “=” 导致报错；
/*
输入字符串统计字符个数（权值）
int CreateWeightArray(char* str, int* Array) {
// 初始化权值数组，128 为 str [i] 的最大数值
for (int i = 0; i < 128; i++)
{
Array[i] = 0;
}
int length = 0;
// 利用下标记录位权
for (int i = 0; str[i]; i++)
{
Array [str [i]]++; // 值加 1，下标即字符
}
// 统计字符串去重后的长度
for (int i = 0; i < 128; i++)
{
if (Array[i] != 0)
{
length++;
}
}
return length;
}
*/
c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
using namespace std;
//定义哈夫曼树存储结构
typedef struct
{
char data; //存放结点数据
int weight; //记录结点权值
int parent, lchild, rchild;
}HTNode, * HuffmanTree;
//哈夫曼编码存储表示
typedef char** HuffmanCode; //动态分配数组储存哈夫曼编码表
//初始化
HuffmanTree InitHuffman(HuffmanTree& HT, int n)
{
if (n < 0)
{
cout << "输入初态结点数目不正确！！！" << endl;
return NULL;
}
else
{
int m = 2 * n - 1; //n个叶子结点的哈夫曼树有2n-1个结点
HT = new HTNode[m + 1]; //0号单元未用，申请m+1个空间
for (int i = 1; i <= m; i++)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].weight = 0;
HT[i].data = ''-'';
}
//输入初始数据，为了方便理解HT[0]不存放数据
cout << "请输入初态结点数据及相应权值（格式形式：a 3）：";
for (int i = 1; i <= n; i++)
{
cin >> HT[i].data;
cin >> HT[i].weight;
}
return HT;
}
}
//打印HT
void PrintState(HuffmanTree& HT, int n)
{
int m = 2 * n - 1; //总结点数
cout << "结点i\tdata值\tweight\tparent\tlchild\trchild" << endl;
for (int i = 1; i <= m; i++)
{
cout << setw(3) << i << "\t";
cout << setw(4) << HT[i].data << "\t";
cout << setw(4) << HT[i].weight << "\t";
cout << setw(4) << HT[i].parent << "\t";
cout << setw(4) << HT[i].lchild << "\t";
cout << setw(4) << HT[i].rchild << "\t" << endl;
}
}
//选择双亲域为0且两权值最小的结点，选择范围为1到i-1
int* Select(HuffmanTree& HT, int n, int* Idx)
{
int MIN, MinSecond;
//打擂台法使权最小值和次权最小值最大（假设第一个值权值最小无法进行）
MIN = MinSecond = 99999;
//循环从1到n次
for (int i = 1; i <= n; i++)
{
//如果双亲为0（未删除结点与新生成结点），一定会执行if语句,寻找权最小值
if ((HT[i].parent == 0) && HT[i].weight < MIN)
{
//将最小的权值给MinSecond方便寻找次最小值
MinSecond = MIN;
MIN = HT[i].weight;
//记录权最小值下标
Idx[0] = i;
}
//否则如果满足条件寻找次最小值
else if ((HT[i].parent == 0) && HT[i].weight < MinSecond)
{
MinSecond = HT[i].weight;
//记录权次最小值下标
Idx[1] = i;
}
}
return Idx;
}
//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree& HT, int n)
{
if (n <= 1)
return;
int m = 2 * n - 1; //n个叶子结点的哈夫曼树有2n-1个结点
//从n+1开始构造哈弗曼树
for (int i = n + 1; i <= m; i++)
{
//Idx用于存放两个返回最小权值的下标，i-1为前n个结点，后面随着i增加，n也增加
int* Idx = Idx = new int[2];
Idx = Select(HT, i - 1, Idx);
int s1 = Idx[0]; //权最小值下标
int s2 = Idx[1]; //权次最小值下标
//给两权值最小的结点置双亲,使s1，s2结点不在录入Select范围
HT[s1].parent = i;
HT[s2].parent = i;
//给新节点i左右孩子置位s1,s2
HT[i].lchild = s1;
HT[i].rchild = s2;
//给新结点赋权值
HT[i].weight = HT[s1].weight + HT[s2].weight;
delete[]Idx;
}
}
//哈夫曼编码
void CreateHuffmanCode(HuffmanTree& HT, HuffmanCode& HC, int n)
{
HC = new char* [n + 1]; //分配字符的空间
char* TempCode = new char[n]; //分配临时编码表空间n个
TempCode[n - 1] = ''\0''; //编码有叶子结点开始逆序存放，先将末尾结束符标志打上，为后序strcpy
//for循环逐个逆序求叶子结点的哈夫曼编码
for (int i = 1; i <= n; i++)
{
int start = n - 1; //开始存放的起点指向末尾，用于后面HC拷贝是的起始地址
int NodeIdx = i; //NodeIdx最开始存放叶子结点序号
int ParentsIdx = HT[i].parent; //Parents指向其双亲结点序号
//若有双亲则由下到上进行编码，编码的字符，从序号1开始
while (ParentsIdx)
{
start--; //在一维数组末尾，strat先指向最后
//若双亲结点的左结点序号为NodeIdx，将0打入一维临时数组中，否则打入1
if (HT[ParentsIdx].lchild == NodeIdx)
TempCode[start] = ''0'';
else
TempCode[start] = ''1'';
//结点的序号更新，进入上一层
NodeIdx = ParentsIdx;
ParentsIdx = HT[NodeIdx].parent;
}
//临时一维数组存放编码成功，开始用HC顺序存放字符编码
HC[i] = new char[n - start]; //为序号为i的字符分配编码空间
strcpy_s(HC[i], n - start, &TempCode[start]); //编码字符串拷贝strcpy报错因为没有指定长度
}
//打印哈夫曼编码
cout << "---字符对应编码----" << endl;
for (int i = 1; i <= n; i++)
{
cout << HT[i].data << "\t\t" << HC[i] << endl;
}
delete []TempCode;
}
//输入字符打印哈夫曼编码
void PrintCode(HuffmanTree & HT, HuffmanCode & HC, int n)
{
char *str =new char[100]; //存储需要解码的字符
int flag = 0; //flag用于检查输入是否错误
cout << "请输入需要编码的字符：";
cin >> str;
//匹配字符并打印相应的哈夫曼编码
cout << "输入的字符哈夫曼编码为：";
for (int j = 0; j < strlen(str); j++)
{
flag = 0;
for (int i = 1; i <= n; i++)
{
//匹配成功打印编码
if (HT[i].data == str[j])
{
cout << HC[i] ;
flag = 1; //匹配成功
}
}
//如果有匹配失败的情况，则跳出循环
if (flag == 0)
{
cout << "\n第" << j+1 << "字符输入错误!" ;
break;
}
}
putchar(10);
delete []str; //释放str空间
}
//哈夫曼解码并打印
void HuffmanDecode(HuffmanTree& HT, int n)
{
char* str = new char[1024];
cout << "请输入二进制编码：";
cin >> str;
int flag = 0; //用于检查二进制编码是否输入错误
cout << "解码对应字符为：";
//遍历二进制编码
for (int i = 0; i < strlen(str);)
{
int Root = 2 * n - 1; //Root为根结点序号
//当结点的左右孩子不为空时进入循环，由根结点进入
while (HT[Root].lchild && HT[Root].rchild)
{
if (str[i] == ''0'')
Root = HT[Root].lchild;
else if (str[i] == ''1'')
Root = HT[Root].rchild;
else
{
cout << "输入的二级制编码有误！" << endl;
flag = 1;
break;
}
i++; //相后读取二进制编码，i值更新
}
//如果找到错误跳出循环
if (flag)
break;
//打印编码对应字符
cout << HT[Root].data;
}
delete []str;
}
int main()
{
int n;
cout << "请输入哈夫曼树初态结点数：";
cin >> n;
//初始化哈夫曼树
HuffmanTree HT = InitHuffman(HT, n);
//打印HT初态
cout << "--------------------HT初态--------------------" << endl;
PrintState(HT, n);
//构造哈夫曼树
CreateHuffmanTree(HT, n);
//打印HT终态
cout << "--------------------HT终态--------------------" << endl;
PrintState(HT, n);
HuffmanCode HC;
//哈夫曼编码-由下而上
CreateHuffmanCode(HT, HC, n);
//打印字符对应编码
PrintCode(HT, HC, n);
//哈夫曼解码并打印-由上而下
HuffmanDecode(HT, n);
return 0;
}//由于编译器版本原因strcpy出现不安全原因，导致无法运行，后使用strcpy_s给予拷贝长度得到解决；把“==”写成“=”导致报错；
/*
输入字符串统计字符个数（权值）
int CreateWeightArray(char* str, int* Array) {
//初始化权值数组，128为str[i]的最大数值
for (int i = 0; i < 128; i++)
{
Array[i] = 0;
}
int length = 0;
//利用下标记录位权
for (int i = 0; str[i]; i++)
{
Array[str[i]]++; //值加1，下标即字符
}
//统计字符串去重后的长度
for (int i = 0; i < 128; i++)
{
if (Array[i] != 0)
{
length++;
}
}
return length;
}
*/
C++数据结构与算法之哈夫曼树的实现方法
本文实例讲述了C++数据结构与算法之哈夫曼树的实现方法。分享给大家供大家参考，具体如下：
哈夫曼树又称最优二叉树，是一类带权路径长度最短的树。
对于最优二叉树，权值越大的结点越接近树的根结点，权值越小的结点越远离树的根结点。
前面一篇图文详解JAVA实现哈夫曼树对哈夫曼树的原理与java实现方法做了较为详尽的描述，这里再来看看C++实现方法。
具体代码如下：
#include <iostream>
using namespace std;
#if !defined(_HUFFMANTREE_H_)
#define _HUFFMANTREE_H_
/*
* 哈夫曼树结构
*/
class HuffmanTree
{
public:
unsigned int Weight;
unsigned int Parent;
unsigned int lChild;
unsigned int rChild;
};
typedef char **HuffmanCode;
/*
* 从结点集合中选出权值最小的两个结点
* 将值分别赋给s1和s2
*/
void Select(HuffmanTree* HT,int Count,int *s1,int *s2)
{
unsigned int temp1=0;
unsigned int temp2=0;
unsigned int temp3;
for(int i=1;i<=Count;i++)
{
if(HT[i].Parent==0)
{
if(temp1==0)
{
temp1=HT[i].Weight;
(*s1)=i;
}
else
{
if(temp2==0)
{
temp2=HT[i].Weight;
(*s2)=i;
if(temp2<temp1)
{
temp3=temp2;
temp2=temp1;
temp1=temp3;
temp3=(*s2);
(*s2)=(*s1);
(*s1)=temp3;
}
}
else
{
if(HT[i].Weight<temp1)
{
temp2=temp1;
temp1=HT[i].Weight;
(*s2)=(*s1);
(*s1)=i;
}
if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
{
temp2=HT[i].Weight;
(*s2)=i;
}
}
}
}
}
}
/*
* 霍夫曼编码函数
*/
void HuffmanCoding(HuffmanTree * HT,HuffmanCode * HC,int *Weight,int Count)
{
int i;
int s1,s2;
int TotalLength;
char* cd;
unsigned int c;
unsigned int f;
int start;
if(Count<=1) return;
TotalLength=Count*2-1;
HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];
for(i=1;i<=Count;i++)
{
HT[i].Parent=0;
HT[i].rChild=0;
HT[i].lChild=0;
HT[i].Weight=(*Weight);
Weight++;
}
for(i=Count+1;i<=TotalLength;i++)
{
HT[i].Weight=0;
HT[i].Parent=0;
HT[i].lChild=0;
HT[i].rChild=0;
}
//建造哈夫曼树
for(i=Count+1;i<=TotalLength;++i)
{
Select(HT,i-1,&s1,&s2);
HT[s1].Parent = i;
HT[s2].Parent = i;
HT[i].lChild = s1;
HT[i].rChild = s2;
HT[i].Weight = HT[s1].Weight + HT[s2].Weight;
}
//输出霍夫曼编码
(*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
cd = new char[Count*sizeof(char)];
cd[Count-1]='\0';
for(i=1;i<=Count;++i)
{
start=Count-1;
for(c = i,f = HT[i].Parent; f != 0; c = f,f = HT[f].Parent)
{
if(HT[f].lChild == c)
cd[--start]='0';
else
cd[--start]='1';
(*HC)[i] = new char [(Count-start)*sizeof(char)];
strcpy((*HC)[i],&cd[start]);
}
}
delete [] HT;
delete [] cd;
}
/*
* 在字符串中查找某个字符
* 如果找到，则返回其位置
*/
int LookFor(char *str,char letter,int count)
{
int i;
for(i=0;i<count;i++)
{
if(str[i]==letter) return i;
}
return -1;
}
void OutputWeight(char *Data,int Length,char **WhatLetter,int **Weight,int *Count)
{
int i;
char* Letter = new char[Length];
int* LetterCount = new int[Length];
int AllCount=0;
int Index;
int Sum=0;
float Persent=0;
for(i=0;i<Length;i++)
{
if(i==0)
{
Letter[0]=Data[i];
LetterCount[0]=1;
AllCount++;
}
else
{
Index=LookFor(Letter,Data[i],AllCount);
if(Index==-1)
{
Letter[AllCount]=Data[i];
LetterCount[AllCount]=1;
AllCount++;
}
else
{
LetterCount[Index]++;
}
}
}
for(i=0;i<AllCount;i++)
{
Sum=Sum+LetterCount[i];
}
(*Weight) = new int[AllCount];
(*WhatLetter) = new char[AllCount];
for(i=0;i<AllCount;i++)
{
Persent=(float)LetterCount[i]/(float)Sum;
(*Weight)[i]=(int)(1000*Persent);
(*WhatLetter)[i]=Letter[i];
}
(*Count)=AllCount;
delete [] Letter;
delete [] LetterCount;
}
#endif
void main()
{
HuffmanTree * HT = NULL;
HuffmanCode HC;
char Data[100];
char *WhatLetter;
int *Weight;
int Count;
cout<<"请输入一行文本数据:"<<endl;
cin>>Data;
cout<<endl;
OutputWeight(Data,strlen(Data),&WhatLetter,&Weight,&Count);
HuffmanCoding(HT,&HC,Weight,Count);
cout<<"字符 出现频率 编码结果"<<endl;
for(int i = 0; i<Count; i++)
{
cout<<WhatLetter[i]<<" ";
cout<<Weight[i]/1000.0<<"%\t";
cout<<HC[i+1]<<endl;
}
cout<<endl;
}
希望本文所述对大家C++程序设计有所帮助。
C++数据结构之文件压缩（哈夫曼树）实例详解
C++数据结构之文件压缩（哈夫曼树）实例详解
概要：
项目简介：利用哈夫曼编码的方式对文件进行压缩，并且对压缩文件可以解压
开发环境：windows vs2013
项目概述：
1.压缩
a.读取文件，将每个字符，该字符出现的次数和权值构成哈夫曼树
b.哈夫曼树是利用小堆构成，字符出现次数少的节点指针存在堆顶，出现次数多的在堆底
c.每次取堆顶的两个数，再将两个数相加进堆，直到堆被取完，这时哈夫曼树也建成
d.从哈夫曼树中获取哈夫曼编码，然后再根据整个字符数组来获取出现了得字符的编码
e.获取编码后每次凑满8位就将编码串写入到压缩文件（value处理编码1与它即可，0只移动位）
f.写好配置文件，统计每个字符及其出现次数，并以“字符+','+次数”的形式保存到配置文件中
2.解压
a.读取配置文件，统计所有字符的个数
b.构建哈夫曼树，读解压缩文件，将所读到的编码字符的这个节点所所含的字符写入到解压缩文件中，知道将压缩文件读完
c.压缩解压缩完全完成，进行小文件大文件的测试
实例代码：
#pragma once
#include<vector>
template<class T>
struct Less
{
bool operator()(const T& l,const T& r) const
{
return l < r;
}
};
template<class T>
struct Greater
{
bool operator()(const T& l,const T& r) const
{
return l > r;
}
};
template<class T,class Compare>
class Heap
{
public:
Heap()
{}
Heap(T* array,size_t n) //建堆
{
_array.reserve(n);
for (size_t i = 0; i < n; i++)
{
_array.push_back(array[i]);
}
for (int i = (_array.size() - 2) >> 1; i >= 0; --i)
{
_AdjustDown(i);
}
}
const T& Top()const
{
return _array[0];
}
void Push(const T& x)
{
_array.push_back(x);
_AdjustUp(_array.size() - 1);
}
size_t Size()
{
return _array.size();
}
void Pop()
{
assert(_array.size() > 0);
swap(_array[0],_array[_array.size() - 1]);
_array.pop_back();
_AdjustDown(0);
}
bool Empty()
{
return _array.size() == 0;
}
void Print()
{
for (size_t i = 0; i < _array.size(); ++i)
{
cout << _array[i] << " ";
}
cout << endl;
}
protected:
void _AdjustUp(int child) //上调
{
Compare ComFunc;
int parent = (child - 1) >> 1;
while (child)
{
if (ComFunc(_array[child],_array[parent]))
{
swap(_array[child],_array[parent]);
child = parent;
parent = (child - 1) >> 1;
}
else
{
break;
}
}
}
void _AdjustDown(int root) //下调
{
Compare ComFunc;
int parent = root;
int child = root * 2 + 1;
while (child < _array.size())
{
if (child + 1 < _array.size() && ComFunc(_array[child + 1],_array[child]))
{
++child;
}
if (ComFunc(_array[child],_array[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
protected:
vector<T> _array;
};
void TestHeap()
{
int a[] = { 10,11,13,12,16,18,15,17,14,19 };
//Heap<int> heap(a,sizeof(a) / sizeof(a[0]));
//Heap<int,Less<int>> heap(a,sizeof(a) / sizeof(a[0]));
Heap<int,Greater<int>> heap(a,sizeof(a) / sizeof(a[0]));
heap.Print();
heap.Push(25);
heap.Print();
heap.Pop();
heap.Print();
}
#pragma once
#include"Heap.h"
template<class T>
struct HuffmanTreeNode
{
HuffmanTreeNode<T>* _left;
HuffmanTreeNode<T>* _right;
HuffmanTreeNode<T>* _parent;
T _w; //权值
HuffmanTreeNode(const T& x)
:_w(x),_left(NULL),_right(NULL),_parent(NULL)
{}
};
template<class T>
class HuffmanTree
{
typedef HuffmanTreeNode<T> Node;
public:
HuffmanTree()
:_root(NULL)
{}
HuffmanTree(T* a,size_t n,const T& invalid = T()) //构建哈夫曼树
{
struct Compare
{
bool operator()(Node* l,Node* r) const
{
return l->_w < r->_w;
}
};
Heap<Node*,Compare> minHeap;
for (size_t i = 0; i < n; ++i)
{
if (a[i] != invalid)
{
minHeap.Push(new Node(a[i]));
}
}
while (minHeap.Size() > 1)
{
Node* left = minHeap.Top();
minHeap.Pop();
Node* right = minHeap.Top();
minHeap.Pop();
Node* parent = new Node(left->_w + right->_w);
parent->_left = left;
parent->_right = right;
left->_parent = parent;
right->_parent = parent;
minHeap.Push(parent);
}
_root = minHeap.Top();
}
Node* GetRoot()
{
return _root;
}
~HuffmanTree()
{
_Destory(_root);
}
protected:
void _Destory(Node* root)
{
if (root == NULL)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
HuffmanTree(const HuffmanTree<T>& tree);
HuffmanTree& operator=(const HuffmanTree<T>& tree);
protected:
Node* _root;
};
void TestHuffmanTree()
{<pre code_snippet_id="2340790" snippet_file_name="blog_20170418_2_3778260" name="code">#pragma once
#include<iostream>
using namespace std;
#include<assert.h>
#include"HuffmanTree.h"
typedef long long LongType;
struct CharInfo
{
unsigned char _ch; //字符
LongType _count; //字符出现的次数
string _code; //huffman编码
CharInfo(LongType count = 0)
:_count(count),_ch(0),_code("")
{}
bool operator<(const CharInfo& info) const
{
return _count < info._count;
}
CharInfo operator+(const CharInfo& info)
{
return CharInfo(_count + info._count);
}
bool operator!=(const CharInfo& info)const
{
return _count != info._count;
}
};
struct CountInfo
{
unsigned char _ch; //字符
LongType _count; //字符出现的次数
};
class FileCompress
{
public:
FileCompress()
{
for (size_t i = 0; i < 256; ++i)
{
_info[i]._ch = i;
}
}
void Compress(const char* filename)
{
assert(filename);
//统计字符出现的次数，均已二进制方式读写
FILE* fout = fopen(filename,"rb");
assert(fout);
int ch = fgetc(fout);
string CompressFile = filename;
CompressFile += ".huffman";
FILE* fin = fopen(CompressFile.c_str(),"wb");
assert(fin);
CountInfo info;
while (ch != EOF)
{
_info[(unsigned char)ch]._count++;
ch = fgetc(fout);
}
//构建huffman tree
CharInfo invalid;
invalid._count = 0;
HuffmanTree<CharInfo> tree(_info,256,invalid);
//生成huffman code
GetHuffmanCode(tree.GetRoot());
//压缩
//写配置文件
for (size_t i = 0; i < 256; ++i)
{
if (_info[i]._count)
{
info._ch = _info[i]._ch;
info._count = _info[i]._count;
fwrite(&info,sizeof(info),1,fin);
}
}
info._count = -1;
fwrite(&info,fin);
fseek(fout,SEEK_SET); //返回到文件开始
ch = fgetc(fout);
char value = 0; //二进制
int pos = 0; //左移位数
while (ch != EOF)
{
string& code = _info[(unsigned char)ch]._code;
size_t i = 0;
for (i = 0; i < code.size(); ++i)
{
value <<= 1;
++pos;
if (code[i] == '1')
{
value |= 1;
}
if (pos == 8) //满8位写进文件中
{
fputc(value,fin);
value = 0;
pos = 0;
}
}
ch = fgetc(fout);
}
if (pos)
{
value <<= (8 - pos);
fputc(value,fin);
}
fclose(fin);
fclose(fout);
}
void GetHuffmanCode(HuffmanTreeNode<CharInfo>* root) //huffman编码
{
if (root == NULL)
{
return;
}
if (root->_left == NULL && root->_right == NULL)
{
HuffmanTreeNode<CharInfo> *parent,*cur;
cur = root;
parent = cur->_parent;
string& code = _info[(unsigned char)root->_w._ch]._code;
while (parent)
{
if (cur == parent->_left)
{
code += '0';
}
else
{
code += '1';
}
cur = parent;
parent = cur->_parent;
}
reverse(code.begin(),code.end());
}
GetHuffmanCode(root->_left);
GetHuffmanCode(root->_right);
}
//解压
void UnCompress(const char* filename)
{
assert(filename);
string UnCompressFile = filename;
size_t index = UnCompressFile.rfind('.');
assert(index != string::npos);
UnCompressFile = UnCompressFile.substr(0,index);
UnCompressFile += ".unhuffman";
FILE* fout = fopen(filename,"rb");
assert(fout);
FILE* fin = fopen(UnCompressFile.c_str(),"wb");
assert(fin);
CountInfo info;
fread(&info,sizeof(CountInfo),fout);
//读配置信息
while (1)
{
fread(&info,fout);
if (info._count == -1)
{
break;
}
_info[(unsigned char)info._ch]._ch = info._ch;
_info[(unsigned char)info._ch]._count = info._count;
}
//重建huffman树
CharInfo invalid;
invalid._count = 0;
HuffmanTree<CharInfo> tree(_info,invalid);
HuffmanTreeNode<CharInfo>* root = tree.GetRoot();
HuffmanTreeNode<CharInfo>* cur = root;
LongType count = root->_w._count;
int value = fgetc(fout);
if (value == EOF) //只有一种字符
{
if (info._ch != 0)
{
while (cur->_w._count--)
{
fputc(cur->_w._ch,fin);
}
}
}
else
{
while (value != EOF)
{
int pos = 7;
char test = 1;
while (pos >= 0)
{
if (value & (test << pos))
{
cur = cur->_right;
}
else
{
cur = cur->_left;
}
if (cur->_left == NULL && cur->_right == NULL)
{
fputc(cur->_w._ch,fin);
cur = root;
if (--count == 0)
{
break;
}
}
--pos;
}
value = fgetc(fout);
}
}
fclose(fout);
fclose(fin);
}
protected:
CharInfo _info[256]; //所有字符信息
};
void TestFileCompress()
{
FileCompress fc;
//fc.Compress("实验.doc");
//fc.UnCompress("实验.doc.huffman");
//fc.Compress("qq.JPG");
//fc.UnCompress("qq.JPG.huffman");
//fc.Compress("www.MP3");
//fc.UnCompress("www.MP3.huffman");
fc.Compress("yppppp.txt");
fc.UnCompress("yppppp.txt.huffman");
}</pre><br>
int array[10] = { 2,4,6,9,7,8,5,3 };HuffmanTree<int> t(array,10);}
<pre></pre>
<p></p>
<pre></pre>
<p></p>
<p></p>
<p></p>
<pre code_snippet_id="2340790" snippet_file_name="blog_20170418_3_1128302" name="code">#include <iostream>
#include <assert.h>
#include <windows.h>
using namespace std;
#include"Heap.h"
#include"HuffmanTree.h"
#include"FileCompress.h"
int main()
{
//TestHeap();
TestHuffmanTree();
TestFileCompress();
system("pause");
return 0;
}</pre><br>
<br>
<p></p>
<p><br>
</p>
<p><br>
</p>
<link rel="stylesheet" href="http://static.blog.csdn.net/public/res-min/markdown_views.css?v=1.0" rel="external nofollow" >
以上就是哈夫曼树的实例详解，如有疑问请留言或者到本站社区交流，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
今天关于Java数据结构之哈夫曼树概述及实现和java 哈夫曼树的讲解已经结束，谢谢您的阅读，如果想了解更多关于c++ 实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）、c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）、C++数据结构与算法之哈夫曼树的实现方法、C++数据结构之文件压缩（哈夫曼树）实例详解的相关知识，请在本站搜索。
本文标签：
