哈夫曼树
哈夫曼树是一最优二叉树,假设有n个字节点Tn{T1,T2,……,Tn}的权值分别为
Wn{W1,W2,……,Wn},其构造方法
step1:想找出里面权值最小的两个节点,作为新建父节点的左右子树,父节点的权值step2:为这两个子节点的权值之和在Tn中将父节点的左右子树删除,并将父节点加进step3:重复1、2步,直到Tn只剩一个节点为止。
哈夫曼编码:当建好树后,从根开始,每层左子树标记为0,右子树标记为1,按此规律索引到叶节点,此顺序的01串即为该叶节点对应的哈夫曼编码。
下面是我的建树和打印哈夫曼编码过程(实现了简单的解码):
public class HalfmanTree {
//key字符为value为字符的哈夫曼编码的map队列
HashMap<String, String> map_pre= new HashMap<String, String>();
//key字符为哈夫曼编码为字符的value的map队列,解码用的
HashMap<String, String> map_dis= new HashMap<String, String>();
public static void main(String[] args) {
// TODO Auto-generated method stub
//String str="abbcccddddeeeee";
//手动输入字符串
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
//创建一个哈夫曼类
HalfmanTree half=new HalfmanTree();
//把字符串按不同字符统计权值,并存储到结点类数组中
TreeNode [] arraynode=half.countstr(str);
//根据结点类数组建立树
TreeNode n=half.settree(arraynode);
//打印叶节点中字符的哈夫曼编码,并已将编码放入map中
half.print_hfm(n, "");
//打印字符串的哈夫曼编码
half.print_01(str);
//打印解码的map
half.print_map_dis();
//打印解码后的字符串
//System.out.println(half.discover_code("000 001 001 01 01 01 10 10 10 10 11 11 11 11 11"));
} //主函数结束
//以树节点中的权值大小为标准的比较器
Comparator<TreeNode> com=new Comparator<TreeNode>() {
@Override
public int compare(TreeNode o1, TreeNode o2) {
// TODO Auto-generated method stub
if(o1.date>o2.date){
return 1;
}
else
return -1;
}
};
//对字符串进行遍历,以各不同字符及对应权值创建结点类,保存到数组中返回
public TreeNode [] countstr(String str){
boolean flag_ever;//字符串重复标志
//把第一个字符存入结点类队列的第一个
ArrayList<TreeNode> listnode=new ArrayList<TreeNode>();
TreeNode node =new TreeNode();
node.c=str.charAt(0);
node.date=1;
listnode.add(node);
//从第二个开始遍历字符串
for(int i=1;i<str.length();i++){
flag_ever=false;
//得到第i个字符
char c=str.charAt(i);
//遍历结点类队列
for(int j=0;j<listnode.size();j++){
//如果这个字符存在某个结点类中
if(c==listnode.get(j).c){
//把该几点权值计数加1
listnode.get(j).date++;
flag_ever=true;
//结束循环
break;
}
}
//如果重复标志还是false,则表示没有重复的
if(flag_ever==false){
//那么应该新建一个节点,加入队列中
TreeNode newnode =new TreeNode();
newnode.c=c;
newnode.date=1;
listnode.add(newnode);
//System.out.println(listnode.size());
}
}
//将节点类队列的节点存到数组中
TreeNode [] arraynode=new TreeNode[listnode.size()];
for(int i=0;i<arraynode.length;i++){
arraynode[i]=listnode.get(i);
// System.out.println(listnode.get(i).c);
// System.out.println(listnode.get(i).date);
}
return arraynode;
}
//由结点类数组创建一个树,返回根节点
public TreeNode settree(TreeNode node_array[]){
//直到只有一个节点时结束
while(node_array.length>1){
//对数组进行排序,按照com比较器
Arrays.sort(node_array, com);
//由最小两个数的所在节点创建父节点
TreeNode node=new TreeNode();
node.left=node_array[0];
node.right=node_array[1];
node.date=node_array[0].date+node_array[1].date;
//创建新节点数组,长度减一
TreeNode[] newnode_array=new TreeNode[node_array.length-1];
for(int i=2;i<node_array.length;i++){
newnode_array[i-2]=node_array[i];
}
newnode_array[node_array.length-2]=node;
//把新节点数组首地址赋给院节点数组
node_array = newnode_array;
}
//最后一个节点即根节点,赋哈夫曼编码,并返回根节点
node_array[0].s="";
return node_array[0];
}
//打印二叉树编码
public void print_hfm(TreeNode node,String code){
//有节点存在时
if(node!=null){
// if(node.left ==null && node.right==null){
// System.out.println(node.c+"的哈夫曼编码为:"+code);
//
// }
// print_hfm(node.left, code+"0");
// print_hfm(node.right, code+"1");
//该节点为叶子节点时
if(node.left ==null && node.right==null){
System.out.println(node.c+"的哈夫曼编码为:"+node.s+" 权数为:"+node.date);
map_pre.put(""+node.c, node.s);
map_dis.put(node.s,""+node.c);
}
//左子树为空时,打印哈夫曼编码
if(node.left!=null){
node.left.s=node.s+"0";
print_hfm(node.left,node.left.s);
}
//右子树为空时,打印哈夫曼编码
if(node.right!=null){
node.right.s= node.s+"1";
print_hfm(node.right,node.right.s);
}
}
}
//按字符输出哈夫曼编码
public void print_01(String str){
System.out .println(str+"各字符对应编码为:");
for(int i=0;i<str.length();i++){
char ch= str.charAt(i);
String code=map_pre.get(""+ch);
System.out.print(code+'\t');//每个编码直接加tab键间隔
}
System.out .println();
}
//测试打印map_dis
public void print_map_dis (){
Set<Entry<String, String>> entry=map_dis.entrySet();
for(Entry<String, String> en : entry ){
System.out.println("键"+en.getKey()+"的值为:"+en.getValue());
}
}
//解码
public String discover_code(String str_str){
//String str="000001";
String discode="";
Set<String> set=map_dis.keySet();
String s="";
for(int i=0;i<str_str.length();i++){
if(str_str.charAt(i)!='\t'&&str_str.charAt(i)!=' '){
System.out.println(i);
s=s+str_str.charAt(i);
for(String ss :set){
if(s.equals(ss)){
discode=discode+map_dis.get(s);
s="";
break;
}
}
}
}
return discode;
}
}
这只是个简单的给哈夫曼树编码,应用的话可以做个解约软件,有待突破!!!!
分享到:
相关推荐
"哈夫曼编码实现图像压缩" 哈夫曼编码是一种常用的压缩编码算法,采用变长码编码,属于无损压缩算法的一种。这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的。在无损压缩的编码范畴中,...
哈夫曼树和哈夫曼编码是数据结构中的一种重要概念,哈夫曼树是一种特殊的二叉树,它可以用来构造最优的前缀编码。哈夫曼编码是一种变长编码方法,它可以使得总的编码长度最短。 哈夫曼树的定义是指带权路径长度最小...
"数据结构哈夫曼树和哈夫曼编码" 哈夫曼树是一种特殊的二叉树,它是一种带权路径长度最小的二叉树。哈夫曼树是根据给定的权值集合构造的,它的特点是:有n个叶子结点,没有度为1的结点,总的结点数为2n-1,深度≤n-...
"数据结构-哈夫曼树和哈夫曼编码" 哈夫曼树(Huffman Tree)是一种特殊的二叉树,它的特点是:有 n 个叶子结点,不存在度为 1 的结点,总的结点数为 2n-1,深度≤ n-1,形态不唯一。哈夫曼树的定义是:带权路径长度...
《哈夫曼编码译码系统实验报告》\n\n哈夫曼编码是一种高效的数据压缩算法,主要用于提高数据传输效率和节省存储空间。本实验报告基于数据结构课程设计,旨在实现一个哈夫曼编码和译码系统,适用于双工信道的信息收发...
//动态分配数组存储哈夫曼编码表 //-------全局变量-------- HuffmanTree HT; HuffmanCode HC; int *w;//权值数组 //const int n=26;//字符集的个数 char *info;//字符值数组 int flag=0;//初始化标记 //*****...
小程序提供了两种功能的哈夫曼编码方式: 一、读取本地文件的字符: 对其进行哈夫曼编码后输出编码后的文件到指定文本文件。 二、用户输入待分析字符: 编码结果在用户界面直接显现,并同时提供了解码、...
在哈夫曼树中,没有度为1的结点,结点总数是n0+n2(其中n0表示二叉树中度为0的结点数,n2表示度为2的结点数),而由二叉树的性质知道n0=n2+1,所以一棵哈夫曼树中结点总数是2n0-1。 由此可以得出:任何n个字符的...
哈夫曼编码是为每个字符分配一个唯一的二进制编码,使得字符的频率与其编码的长度成反比。频率高的字符编码短,频率低的字符编码长。通过构建哈夫曼树,可以自底向上地生成这些编码。 3. **C#实现步骤** - **创建...
3. 完成课程设计报告,包括问题分析、总体设计、详细设计、测试报告、小结和软件使用说明。 课程设计报告中,需要特别注意的是,哈夫曼树的构建和编码过程,以及如何处理码文件最后一字节的多余位信息。在处理位串...
六、小结 通过哈夫曼编码/译码器的设计,学生不仅掌握了哈夫曼编码的原理,还锻炼了程序设计、数据结构应用和问题解决的能力。这个过程有助于提升对数据结构的理解,为今后的计算机科学学习和实践打下坚实基础。
#### 小结 通过本次实验,不仅能够深入了解哈夫曼编码的工作原理,还能掌握其实现方法。这对于数据压缩领域以及更广泛的计算机科学领域都有着重要的意义。此外,该实验还能够培养编程技能和解决问题的能力,有助于...
- 通过个人设计小结,每个成员反思自己的工作,并提出下一步改进方向。 8. **相关技术**: - 熟悉C/C++编程语言,可能还涉及到MFC库,用于构建图形用户界面。 - 二进制文件的读写操作,以及统计分析,对于构建...
本项目旨在实现一个基于哈夫曼编码原理的编译码器,该编译码器能够统计文本文件中字符的出现频率,并以此为基础构建哈夫曼树,进而对文件进行编码压缩和解码还原。 #### 概要设计 本系统主要分为三个阶段:初始化...
利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。对于双工信道(即可以...
#### 小结 通过上述代码,我们可以清晰地了解到哈夫曼树的创建过程及其带权路径长度的计算方法。哈夫曼树不仅在数据压缩中有重要作用,还在信息编码、网络通信等领域有着广泛的应用前景。通过理解这些基础算法,...
利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。对于双工信道 (即可以双向...