「哈夫曼树java」哈夫曼树JAVA实现代码
本篇文章给大家谈谈哈夫曼树java，以及哈夫曼树JAVA实现代码对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
java用huffman树压缩文件时，文件夹应该如何处理
我讲一下我的思路：
用java的字节流读取一个文件，假设这个文件是100字节的。
int b;
FileInputStream in = new FileInputStream("文件路径");
while((b = in.read()) != -1){...}这样便得到100个整形（0~255）的数。
然后按照huffman的思想是统计每个数在这100个出现的概率，然后将最小的两个概率合起来作为两个叶子结点......一直做下去，直至生成一棵数。
到底什么是哈夫曼树啊，求例子
哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
例子：
1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3、从森林中删除选取的两棵树，并将新树加入森林；
4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
扩展资料：
按照哈夫曼编码构思程序流程：
1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；
2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。
3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。
4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可
5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。
参考资料来源:百度百科——哈夫曼树
哈夫曼编码与译码 java
class
HaffmanNode
//哈夫曼树的结点类
{
int
weight;
//
权值
int
parent,left,right;
//父母结点和左右孩子下标
public
HaffmanNode(int
weight)
{
this.weight
=
weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public
HaffmanNode()
{
this(0);
}
public
String
toString()
{
return
this.weight+",
"+this.parent+",
"+this.left+",
"+this.right;
}
return
code;
}
public
static
void
main(String[]
args)
{
int[]
weight={5,29,7,8,14,23,3,11};
//指定权值集合
HaffmanTree
htree
=
new
HaffmanTree(weight);
System.out.println("哈夫曼树的结点数组:\n"+htree.toString());
String[]
code
=
htree.haffmanCode();
System.out.println("哈夫曼编码:");
for
(int
i=0;
icode.length;
i++)
System.out.println(code[i]);
}
}
哈夫曼树java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于哈夫曼树JAVA实现代码、哈夫曼树java的信息别忘了在本站进行查找喔。