1、根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi根结点,其左右子树均为空。
2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3、在F中删除这两棵树,同时将新得到的二叉树加入F中。
4、重复2和3步骤,直到F只含一棵树为止。这棵树便是哈夫曼树。
/**
* 哈夫曼树
*
*/
public class HuffmanTree {
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>(8);
hashMap.put("A", 5);
hashMap.put("B", 87);
hashMap.put("C", 4);
hashMap.put("D", 2);
hashMap.put("E", 2);
hashMap.put("F", 9);
ArrayList<HuffmanTreeNode> huffmanTreeNodes = new ArrayList<>();
for (String key : hashMap.keySet()) {
HuffmanTreeNode huffmanTreeNode = new HuffmanTreeNode(key, hashMap.get(key));
huffmanTreeNodes.add(huffmanTreeNode);
}
HuffmanTreeNode root = createTree(huffmanTreeNodes);
printTree(root);
}
/**
* 先序遍历哈夫曼树 根左右
*
* @param root
*/
private static void printTree(HuffmanTreeNode root) {
if (root == null) {
return;
}
System.out.println("key:" + root.key + " weight:" + root.weight);
printTree(root.leftChildren);
printTree(root.rightChildren);
}
/**
* 创建哈夫曼树
*
* @param huffmanTreeNodes
* @return
*/
private static HuffmanTreeNode createTree(ArrayList<HuffmanTreeNode> huffmanTreeNodes) {
HuffmanTreeNode huffmanTreeNodeNew = null;
while (huffmanTreeNodes.size() >= 2) {
// 取出权值最小的两个值
huffmanTreeNodes.sort(Comparator.comparing(o -> o.weight));
String newKey = huffmanTreeNodes.get(0).key + huffmanTreeNodes.get(1).key;
int newWeight = huffmanTreeNodes.get(0).weight + huffmanTreeNodes.get(1).weight;
System.out.println(newKey + newWeight);
huffmanTreeNodeNew = new HuffmanTreeNode(newKey, newWeight);
huffmanTreeNodeNew.leftChildren = huffmanTreeNodes.get(0);
huffmanTreeNodeNew.rightChildren = huffmanTreeNodes.get(1);
huffmanTreeNodes.remove(0);
huffmanTreeNodes.remove(1);
huffmanTreeNodes.add(huffmanTreeNodeNew);
}
return huffmanTreeNodeNew;
}
/**
* 哈夫曼树节点
*/
static class HuffmanTreeNode {
String key;
// 权重
Integer weight;
HuffmanTreeNode leftChildren;
HuffmanTreeNode rightChildren;
public HuffmanTreeNode(String key, Integer weight) {
this.key = key;
this.weight = weight;
}
}
}
👋 你好,我是 Lorin 洛林,一位 Java 后端技术开发者!座右铭:Technology has the power to make the world a better place.
🚀 我对技术的热情是我不断学习和分享的动力。我的博客是一个关于Java生态系统、后端开发和最新技术趋势的地方。
🧠 作为一个 Java 后端技术爱好者,我不仅热衷于探索语言的新特性和技术的深度,还热衷于分享我的见解和最佳实践。我相信知识的分享和社区合作可以帮助我们共同成长。
💡 在我的博客上,你将找到关于Java核心概念、JVM 底层技术、常用框架如Spring和Mybatis 、MySQL等数据库管理、RabbitMQ、Rocketmq等消息中间件、性能优化等内容的深入文章。我也将分享一些编程技巧和解决问题的方法,以帮助你更好地掌握Java编程。
🌐 我鼓励互动和建立社区,因此请留下你的问题、建议或主题请求,让我知道你感兴趣的内容。此外,我将分享最新的互联网和技术资讯,以确保你与技术世界的最新发展保持联系。我期待与你一起在技术之路上前进,一起探讨技术世界的无限可能性。
📖 保持关注我的博客,让我们共同追求技术卓越。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。