树论之哈夫曼树

本文主要是介绍树论之哈夫曼树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树论之哈夫曼树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树构建

• 哈夫曼树的节点都是叶子节点
• 根据哈夫曼树的特点，构建树最好的选择当然是从底层开始。
• 从底层开始构建时应该选择权重最小的2个值开始构建

哈夫曼树的用途

• 哈夫曼编码是最优前缀码 因此可用于加密解密
• 文件压缩解压

代码再现

public class HuffmanTree {List<TreeNode> leafs;Map<Character,Integer> weights;TreeNode rootNode;Map<Character,String> codeMap;Map<String,Character> decodeMap;private HuffmanTree(Map<Character,Integer> weights) {this.weights = weights;leafs = new ArrayList<>();codeMap = new HashMap<>();decodeMap = new HashMap<>();initTree();}public void initTree(){PriorityQueue<TreeNode> queue = new PriorityQueue();Character[] keys =weights.keySet().toArray(new Character[0]);weights.keySet().toArray(keys);for(Character chr:keys){TreeNode treeNode = new TreeNode(chr.toString(),weights.get(chr).intValue());queue.add(treeNode);leafs.add(treeNode);}for(int n=1;n <= keys.length-1;n++) {TreeNode left = queue.poll();TreeNode right = queue.poll();TreeNode newNode = new TreeNode(left.chars+right.chars,left.freq+right.freq);newNode.left = left ; newNode.right = right;left.parent = newNode;right.parent = newNode;queue.add(newNode);}rootNode = queue.poll();}public String encode(String str) {StringBuilder sbr = new StringBuilder();for(Character c : str.toCharArray()) {sbr.append(codeMap.get(c));}System.out.println(str+"=="+sbr.toString());return sbr.toString();}public void decode(String str) {StringBuilder sbr = new StringBuilder();StringBuilder temp = new StringBuilder();for(Character c : str.toCharArray()) {temp.append(c);if(decodeMap.containsKey(temp.toString())) {sbr.append(decodeMap.get(temp.toString()));temp = new StringBuilder();}}System.out.println(str+"=="+sbr.toString());}public void codes(){for(int i=0;i<leafs.size();i++) {TreeNode current = leafs.get(i);Character c = current.chars.charAt(0);String codes = "";while(current.parent!=null) {if(current == current.parent.left) {codes="0"+codes;}else {codes="1"+codes;}current = current.parent;}System.out.println(c+"::"+codes);codeMap.put(c, codes);decodeMap.put(codes, c);}}public static void main(String[] args) {Map<Character,Integer> weights =new HashMap<Character,Integer>();weights.put('a', 3);weights.put('b', 24);weights.put('c', 6);weights.put('d', 20);weights.put('e', 34);weights.put('f', 4);weights.put('g', 12);HuffmanTree huffman = new HuffmanTree(weights);huffman.codes();huffman.decode(huffman.encode("afeddacbad"));}static class TreeNode implements Comparable<TreeNode>{private String chars;//节点字符private int freq;//权重private TreeNode left;//左节点private TreeNode right;//右节点private TreeNode parent;//父节点private TreeNode(String chars,int freq) {this.chars = chars;this.freq = freq;}@Overridepublic int compareTo(TreeNode o) {return this.freq-o.freq;}}
}

这篇关于树论之哈夫曼树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---