哈夫曼树（huffman）

学完了huffman树，讲一下自己对它的理解

huffman树遵循二叉树的原则，每个节点最多有两个子节点，但是每个节点都带有一个权重，如果我们要将一组字符串 “ B D C A F E ” 插入huffman树，每个字符都会带有一个权重，“ B（8）D（15）C（15）A（27）F（5）E（30）”
首先要根据字符的权重从小到大排序，得到 “ F（5）B（8）C（15）D（15）A（27）E（30）” ，然后取出最小的两个，F和B ，从树的叶子节点开始插，然后得到F和B 的权重和 13 当做他们的父节点，这时候再把13和之前的字符串重新排序，重新取出两个权重最小的节点出来拼接（注：取出来的节点要从原数据里删除），如果取出来的两个里有之前的13（父节点），就把另一个和它一块组合成两个孩子节点继续往上走，刚才这里会走到下图的13和C那边，C的权重比13大，所以在右边，小即左边，继续往上走时从字符串里取出了两个最小的D（15）和A（27） 都比刚才的28小，他们和28没有关联，所以会另外生成一个新的父节点（权重42），然后再取得时候才会取到28和E（30），他们合成的父节点58，最后字符串里只剩下2个无名节点（我们不需要关注的节点），最后全部插入结果如图一：

在这里插入图片描述

图一

我们会发现我们需要的数据会全部插在叶子节点上！这个有什么用呢，如果我们把树从根节点往下查找数据，往左走用0来表示，右用1来表示，那么生成的编码都将是唯一的！
看图二：

在这里插入图片描述

图二

比如D在此树的编码会是00，A 01，E 11，C 1101，F 1000，B 1001
所以利用huffman树这一规则，我们可以来做压缩，压缩通俗的讲就是把内容转化成占内存空间更小的字节，比如01。
下面我们用代码写出一颗哈夫曼树：
树的节点里和二叉排序树一样有值、左右孩子、父节点这里加了一个权重，用来判断树的存放位置的，节点里有个比大小的方法compareTo

public class HuffmanTree<Y> {public TreeNode<Y> root;   //根节点private String defaultParentItem = "Y";/*** 节点** @param <Y> 值*/public static class TreeNode<Y> implements Comparable<TreeNode<Y>> {Y item; //值int weight; //权重TreeNode<Y> left;   //左孩子TreeNode<Y> right;  //右孩子TreeNode<Y> parent; //父节点public TreeNode(Y item, int weight) {this.item = item;this.weight = weight;this.left = null;this.right = null;this.parent = null;}@Overridepublic int compareTo(@NonNull TreeNode<Y> o) {if (this.weight > o.weight) {return -1;} else if (this.weight < o.weight) {return 1;}return 0;}}
}

这里用数组传进来直接把一串内容插入到哈夫曼树里

    /*** 传一个数组进来 创建哈夫曼树** @param list 集合* @return 根节点*/public TreeNode<Y> createHuffmanTree(ArrayList<TreeNode<Y>> list) {//这里就当list里超过2个 就一直循环，知道删了只剩一个时出来 那时候这个节点就是根节点while (list.size() > 1) {//用Collections进行排序Collections.sort(list);//取list的最后2个当做左右孩子树TreeNode<Y> left = list.get(list.size() - 1);TreeNode<Y> right = list.get(list.size() - 2);//根据左右权重创建父节点TreeNode<Y> parent = new TreeNode<>((Y) defaultParentItem, left.weight + right.weight);//把左右树和父节点连接parent.left = left;left.parent = parent;parent.right = right;right.parent = parent;//从list里删除左右树list.remove(left);list.remove(right);//再把父节点添加进去list.add(parent);}root = list.get(0);return list.get(0);}

这边输出我从根节点从左往右依次向下走输出，利用了队列的先进先出原则

    /*** 横向依次输出树** @param root 根节点*/public void showHuffmanTree(TreeNode<Y> root) {//这里用LinkedList队列可以依次取出值LinkedList<TreeNode<Y>> list = new LinkedList<>();//入队list.offer(root);while (!list.isEmpty()) {//出队 直接输出TreeNode<Y> node = list.pop();if (node.item != defaultParentItem) {System.out.print(node.item + " ");}//如果左右还有孩子 就把左右孩子也入队，到下一个循环排在后面依次输出if (node.left != null) {list.offer(node.left);}if (node.right != null) {list.offer(node.right);}}}

根据节点，取到自己的位置（编码）
思想：根据节点依次向上走，如果自己是父节点的左孩子，就往栈里插入0，右孩子就插入1，一直到没有父节点时（即自己遍历到根节点了），然后从栈中取出数据返回即可

    /*** 根据节点获取编码** @param node 节点* @return 编码*/public String getCode(TreeNode<Y> node) {String str = "";TreeNode<Y> treeNode = node;//用栈装 待会拿出来就是正序了Stack<String> stack = new Stack<>();while (treeNode != null && treeNode.parent != null) {if (treeNode.parent.left == treeNode) {stack.push("0");} else if (treeNode.parent.right == treeNode) {stack.push("1");}treeNode = treeNode.parent;}//把stack里的值出栈while (!stack.isEmpty()) {str = str + stack.pop();}return str;}

这边呢，我根据传进来的字符串编码，然后遍历它，得到字节，从根节点root出发向下走，如果是0就往左走，1往右走，如果走到的节点没有左孩子和右孩子了，即使我们要找的值，然后加进集合里把node再次=根节点重新开始。。。

    /*** 根据传进来的编码返回一个list** @param code 编码字符串* @return 集合*/public ArrayList<TreeNode<Y>> getTreeNodeList(String code) {ArrayList<TreeNode<Y>> resultList = new ArrayList<>();TreeNode node = root;//依次循环 是0就往左边走 1右边走for (int i = 0; i < code.length(); i++) {if (code.charAt(i) == '0') {//如果左孩子不为空 就移到左孩子if (node.left != null) {node = node.left;//如果移动过后它的左孩子和右孩子都为空 则说明自己就是要取的值了 然后把node再次赋值为根节点，重新查if (node.left == null && node.right == null) {resultList.add(node);node = root;}}} else if (code.charAt(i) == '1') {if (node.right != null) {node = node.right;if (node.left == null && node.right == null) {resultList.add(node);node = root;}}}}return resultList;}

好了到这里程序的一些简单功能基本上写完了让我们看看程序执行的效果：
执行程序代码（这边用了注解）：

    @org.junit.Testpublic void huffmanTreeTest() {ArrayList<HuffmanTree.TreeNode<String>> list = new ArrayList<>();HuffmanTree.TreeNode node1 = new HuffmanTree.TreeNode("good", 50);list.add(node1);HuffmanTree.TreeNode node2 = new HuffmanTree.TreeNode("morning", 10);list.add(node2);HuffmanTree.TreeNode node3 = new HuffmanTree.TreeNode("afternoon", 20);list.add(node3);HuffmanTree.TreeNode node4 = new HuffmanTree.TreeNode("hello", 110);list.add(node4);HuffmanTree.TreeNode node5 = new HuffmanTree.TreeNode("hi", 200);list.add(node5);System.out.print("原   数   据 ：");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i).item + " ");}HuffmanTree<String> huffmanTree = new HuffmanTree<>();//创建树HuffmanTree.TreeNode root = huffmanTree.createHuffmanTree(list);//展示树System.out.print("\nhuffmanTree里：");huffmanTree.showHuffmanTree(root);String node1Code = huffmanTree.getCode(node1);String node2Code = huffmanTree.getCode(node2);String node3Code = huffmanTree.getCode(node3);String node4Code = huffmanTree.getCode(node4);String node5Code = huffmanTree.getCode(node5);//根据节点查询相应编码System.out.println("\n" + node1.item + "      在huffmanTree里的编码：" + node1Code);System.out.println(node2.item + "   在huffmanTree里的编码：" + node2Code);System.out.println(node3.item + " 在huffmanTree里的编码：" + node3Code);System.out.println(node4.item + "     在huffmanTree里的编码：" + node4Code);System.out.println(node5.item + "        在huffmanTree里的编码：" + node5Code);String code = node1Code + node2Code + node3Code + node4Code + node5Code;System.out.println("list里所有值的组成编码：" + code);System.out.println("================================解 码================================");ArrayList<HuffmanTree.TreeNode<String>> resultList = huffmanTree.getTreeNodeList(code);if (resultList != null) {for (int i = 0; i < resultList.size(); i++) {System.out.print(resultList.get(i).item + " ");}}}