Java实现哈夫曼树代码，可运行
Java实现哈夫曼树代码，可运行
import java.util.ArrayList;
import java.util.Comparator;
public class huffmanTree {
private TreeNode root;
private ArrayList<TreeNode> array = new ArrayList<>();
// 将数据放入列表中
public void setArray(Object[][] key){
for(int i=0;i<key.length;i++){
array.add(new TreeNode(new Node(key[i][0], (Integer) key[i][1])));
}
}
// 降序排序
public void sort(){
array.sort(new Comparator<TreeNode>() {
@Override
public int compare(TreeNode o1, TreeNode o2) {
return o1.node.w - o2.node.w;
}
});
}
// 按照规则，生成两个最小节点的合并节点
public TreeNode product(TreeNode left,TreeNode right){
TreeNode newNode = new TreeNode(new Node(left.node.o+""+right.node.o,left.node.w+right.node.w));
newNode.left = left;
newNode.right = right;
return newNode;
}
// 构造哈夫曼树
public huffmanTree(Object[][] key){
setArray(key);
sort();
TreeNode newNode = null;
while (array.size()>1){ // 当列表中只剩一个节点后代表排序完成
// 总取出最小的两个节点
newNode = product(array.get(0), array.get(1));
// 删除已选择的节点
array.remove(0);
array.remove(0);
// 将新生成的节点加入排表中，在重新排序
array.add(newNode);
sort();
}
// 令root指向树的头节点
root = newNode;
}
// 输出叶子节点和其编码 回溯
public void print(TreeNode root,StringBuffer code){
if(root!=null){
if(root.right==null && root.left == null){
System.out.print("{"+root.node.o+":"+root.node.w+"}:"+code.toString());
}
print(root.left,code.append("0"));
code.deleteCharAt(code.length()-1);
print(root.right,code.append("1"));
code.deleteCharAt(code.length()-1);
}
}
// 主程序
public static void main(String[] args){
huffmanTree huffman = new huffmanTree(new Object[][]{{"a",45},{"b",13},{"c",12},{"d",16},{"e",9},{"f",5}});
huffman.print(huffman.root,new StringBuffer(""));
}
}
// 节点信息
class Node{
Object o; // 表示的对象
int w; // 权重
public Node(){}
public Node(Object o,int w){
this.o = o;
this.w = w;
}
}
// 树节点
class TreeNode{
TreeNode left;
TreeNode right;
Node node;
public TreeNode(){}
public TreeNode(Node node){
this.node = node;
}
}
————————————————
版权声明：本文为CSDN博主「时(^ω^)人‡」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44957574/article/details/114766367