哈夫曼树（huffman）
2018-12-21 本文已影响0人
一个多洋
学完了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在此树的编码会是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;
}
@Override
public 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.Test
public 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 + " ");
}
}
}
- 感谢观赏！
