Java 最优二叉树的哈夫曼算法的简单实现最优二叉树的哈夫曼算法的简单实现
主要介绍了Java 最优二叉树的哈夫曼算法的简单实现,文中通过示例代码介绍的非常详细,对大家的学习或者
工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
最优二叉树也称哈夫曼树,讲的直白点就是每个结点都带权值,我们让大的值离根近、小的值离根远,实现整体权值(带权路
径长度)最小化。
哈夫曼算法的思想我认为就是上面讲的,而它的算法实现思路是这样的:
从根结点中抽出权值最小的两个(涉及排序,但是我这个实现代码没做严格的排序,只有比较)合并出新的根结点重新加入排
序(被抽出来的两个自然是变成非根结点了啊),就这样循环下去,直到合并完成,我们得到一颗最优二叉树——哈夫曼树。
说明:
(1)哈夫曼树有n个叶子结点,则我们可以推出其有n-1个分支结点。因此我在定义名为huffmanTree的HuffmanNode类型数
组时定义长度为2*n-1。
(2)这里排序相关没有做得很好,只是为了实现而实现,以后慢慢完善。
(3)理论上讲哈夫曼树应该是不仅仅局限于数值,能compare就行,但这里只用int表示。
下面是代码:
首先定义哈夫曼树结点
public class HuffmanNode {
private int weight = -1;
private int parent = -1;
private int left = -1;
private int right = -1;
public HuffmanNode(int weight) {
super();
this.weight = weight;
}
public HuffmanNode(int weight, int left, int right) {
super();
this.weight = weight;
this.left = left;
this.right = right;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getParent() {
return parent;
}
public void setParent(int parent) {
this.parent = parent;
}
public int getLeft() {
return left;
}
public void setLeft(int left) {
this.left = left;
}
public int getRight() {
return right;
}
public void setRight(int right) {
this.right = right;
}
@Override