import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* @author chenyi
* @Description 构建赫夫曼树
* @date 2022/2/21 10:06
*/
public class HuffmanTree {
public static void main(String[] args) {
int[] arr = {13,7,8,3,29,6,1};
Node root = createHuffmanTree(arr);
// 输出来看看
perOrder(root);
}
public static void perOrder(Node node){
if(node==null) {
return;
}
System.out.print(node.val + " ");
perOrder(node.left);
perOrder(node.right);
}
private static Node createHuffmanTree(int[] arr) {
// 将整数数组变为节点集合
List<Node> nodeList = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
nodeList.add(new Node(arr[i]));
}
while (nodeList.size()>1) {
Collections.sort(nodeList);
// 取出最小的两个节点，两个节点之后构建出第三个节点
Node node1 = nodeList.remove(0);
Node node2 = nodeList.remove(0);
Node node3 = new Node(node1.val+node2.val);
node3.left = node1;
node3.right = node2;
nodeList.add(node3);
}
return nodeList.get(0);
}
}
class Node implements Comparable<Node>{
int val;
Node left;
Node right;
@Override
public int compareTo(Node o) {
return this.val-o.val;
}
public Node(int val) {
this.val = val;
}
}
构建赫夫曼树
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 赫夫曼树的概念 要了解赫夫曼树，我们要首先从扩充二叉树说起 二叉树结点的度 结点的度指的是二叉树结点的分支数目， ...
- 赫夫曼树创建思路图解 给你一个数列{13,7,8,3,29,6,1},要求转成一颗赫夫曼树思路分析(示意图): 构...
- 最佳实践-数据压缩(创建赫夫曼树) 将给出的一段文本,比如"i like like like java do yo...
- from:http://data.biancheng.net/view/33.html 赫夫曼树，别名“哈夫曼树”...
