数据结构与算法【Java】08---树结构的实际应用( 五 ) _生活百科

功能：根据赫夫曼编码压缩数据的原理，需要创建 "i like like like java do you like a java" 对应的赫夫曼树
思路:
(1) Node { data (存放数据)，weight (权值)，left和 right }(2) 得到 "i like like like java do you like a java"对应的 byte[] 数组(3)编写一个方法，将准备构建赫夫曼树的Node 节点放到 List, 形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],体现 d:1 y:1 u:1 j:2v:2o:2l:4k:4e:4 i:5a:5:9(4) 可以通过List 创建对应的赫夫曼树

代码实现

import java.util.*;public class HuffmanCode {public static void main(String[] args) {String content = "i like like like java do you like a java";byte[] contentBytes = content.getBytes();System.out.println(contentBytes.length);//40List<Node> nodes = getNodes(contentBytes);System.out.println("nodes="+nodes);//测试创建的二叉树System.out.println("创建赫夫曼树：");Node huffmanTreeRoot = createHuffmanTree(nodes);System.out.println("前序遍历：");huffmanTreeRoot.preOrder();}//前序遍历的方法public static void preOrder(Node root){if (root != null){root.preOrder();}else {System.out.println("赫夫曼树为空");}}/**** @param bytes 接收字节数组* @return 返回的就是 List 形式[Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],*/private static List<Node> getNodes(byte[] bytes){//1.创建一个ArrayListArrayList<Node> nodes = new ArrayList<>();//遍历bytes,存储每一个byte出现的次数=》map[key,value]HashMap<Byte,Integer> counts = new HashMap<>();for (byte b: bytes) {Integer count = counts.get(b);if (count == null){//Map还没有这个数据counts.put(b,1);}else {counts.put(b,count+1);}}//把每个键值对转成一个Node对象,并加入到nodes集合//遍历mapfor (Map.Entry<Byte,Integer> entry : counts.entrySet()){nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}//通过list创建应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes){while (nodes.size() > 1){//排序,从小到大Collections.sort(nodes);//取出第一棵最小的二叉树左节点Node leftNode = nodes.get(0);//取出第二棵最小的二叉树右节点Node rightNode = nodes.get(1);//创建一棵新的二叉树，它的根节点没有data，只有权值Node parent = new Node(null, leftNode.weight+ rightNode.weight);parent.left = leftNode;parent.right = rightNode;//将已经处理的两棵二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);//将新的二叉树加入到nodesnodes.add(parent);}//nodes 最后的节点就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值class Node implements Comparable<Node>{Byte data;//存放数据本身a===>97 ascii码int weight;//权值，表示字符出现的次数Node left;Node right;public Node(Byte data, int weight) {this.data = https://www.huyubaike.com/biancheng/data;this.weight = weight;}@Overridepublic int compareTo(Node o) {//从小到大排序return this.weight-o.weight;}public String toString() {return"Node [data = "https://www.huyubaike.com/biancheng/+ data +" weight=" + weight + "]";}//前序遍历public void preOrder() {System.out.println(this);if(this.left != null) {this.left.preOrder();}if(this.right != null) {this.right.preOrder();}}}

结果：（创建出赫夫曼树前序遍历）