线索二叉树#
假设我们有下面的二叉树，然后我们可以使用中序遍历它。
中序遍历的结果是 4、2、5、1、3、6
但是很快我们就发现了两个问题，啥问题呢?
- 问题1: 虽然可以正确的遍历出 4、2、5、1、3、6 但是当我们遍历到2时，我们是不知道2的前一个是谁的(哪怕我们刚才遍历到了它的前一个节点就是4)
- 问题2: node4、5、6、3的左右节点的引用存在空闲的情况
针对这个现状做出了改进就是线索化二叉树，它可以充分利用各个节点中剩余的node这个现状...线索化后如下图
- 如果这个节点的右节点为空，我们就让它让它指向自己的后继节点。 例如上图的红线
- 如何节点的左节点为空,，就让这个空闲的节点指向它的前驱节点，例如上图的蓝色线
这样的话，就实现了任意获取出一个节点我们都能直接的得知它的前驱节点后后继节点到底是谁
java&中序化二叉树;#
思路: 按照原来中序遍历树的思路，对树进行中序遍历，一路递归到节点4，检查到它的左节点为空，就将它的左节点指向它的前驱节点，可是4本来就是最前的节点，故4这个节点的左节点自然指向了null。
然后看它的右节点也为空，于是将他的右节点指向它的后继节点, 可是这时依然没获取到2节点的引用怎么办呢? 于是先找个变量将4节点临时存起来，再往后递归。等递归到2节点时，取出临时变量的4节点，节点4.setRightNode(节点2)。
然后重复这个过程
// 临时保存上一个节点 private TreeNode preNode; // 中序线索化二叉树 void threadNode(TreeNode node) { if (node == null) return; // 处理左边 threadNode(node.getLeftNode()); // 左节点为空,说明没有左子节点, 让这个空出的左节点指向它的上一个节点 if (node.getLeftNode() == null) { // 指向上一个节点 node.setLeftNode(preNode); // 标识节点的类型 node.setLeftType(1); } // 处理前驱节点的右指针 // 比如现在遍历到了1, 1的上一个节点是5, 5的右边空着了, 于是让5的有节点指向1 if (preNode != null && preNode.getRightNode() == null) { preNode.setRightNode(node); preNode.setRightType(1); } // 每次递归调用一次这个方法就更新前驱节点 preNode = node; // 处理右边 threadNode(node.getRightNode()); }
遍历二叉树
public void threadIterator() { TreeNode node = root; while (node != null) { // 循环找 while (node.getLeftType() == 0) node = node.getLeftNode(); // 打印当前节点 System.out.println(node.getValue()); // 如果当前的节点的右type=1说明它有指针指向自己的前一个节点 // 比如现在位置是4, 通过下面的代码可以让node=2 while (node.getRightType() == 1) { node = node.getRightNode(); System.out.println(node.getValue()); } // 替换遍历的节点, 可以让 node从2指向 5, 或者从3指向1 node = node.getRightNode(); } }
赫夫曼树(最优二叉树)#
定义: 什么是赫夫曼树#
赫夫曼树又称为最优二叉树
定义: 在N个带权的叶子节点的所组成的所有二叉树中,如果你能找出那个带权路径最小的二叉树,他就是赫夫曼树
一说起来赫夫曼树,其实我们可以只关心它的叶子节点, 权, 路径这三个要素
- 什么是叶子节点的带权路径?
所谓权,其实就是节点的值, 比如上图中node4的权是8 , node5的权是6 ,node3的权是1, 而且我们只关心叶子节点的权
啥是带权路径呢? 比如上图中 node4的带权路径是 1-2-4
- 树的带权路径长度(weight path length) 简称 WPL
其实就是这个树所有的叶子节点的带权路径长度之和,
计算左树的WPL =2*8+2*6+1*1 = 29
计算左树的WPL =2*1+2*6+1*8 = 22
总结: 权值越大的节点,离根节点越近的节点是最优二叉树
实战: 将数组转换为赫夫曼树#
- 思路:
假设我们现在已经有了数组 [3、5、7、8、11、14、23、29]，如何将这个数组转换成赫夫曼树呢?
取出这里最小的node3和倒数第二小的node5构建成新的树，新树的根节点权是node3、5的权值之和，将构建完成的树放回到原数组中。
重复这个过程，将最小的node7、node8取出构建新树，同样新树的权是node7、8的权重之和。再将构建完成的树放回到原数组中。
如此往复，最终得到的树就是huffman树。
- java实现:
封装TreeNode, 看上面的过程可以看到,需要比较权重的大小,因此重写它的compareTo方法
public class TreeNode implements Comparable{ // 权 private int value; private TreeNode leftNode; private TreeNode rightNode; @Override public int compareTo(Object o) { TreeNode node = (TreeNode) o; return this.value-node.value; }
构建赫夫曼树，思路就是上图的过程：将数组中的各个元素转换成Node，然后存放在List容器中，每轮构建新树时需要排序。当集合中仅剩下一个节点也就是根节点时完成树的构建。
// 创建赫夫曼树 private static TreeNode buildHuffmanTree(int[] arr) { // 创建一个集合,存放将arr转换成的二叉树 ArrayList<TreeNode> list = new ArrayList<>(); for (int i : arr) { list.add(new TreeNode(i)); } // 开始循环, 当集合中只剩下一棵树时 while (list.size() > 1) { // 排序 Collections.sort(list); // 取出权值最小的数 TreeNode leftNode = list.get(list.size() - 1); // 取出权值次要小的数 TreeNode rightNode = list.get(list.size() - 2); // 移除取出的两棵树 list.remove(leftNode); list.remove(rightNode); // 创建新的树根节点 TreeNode parentNode = new TreeNode(leftNode.getValue() + rightNode.getValue(), leftNode, rightNode); // 将新树放到原树的集合中 list.add(parentNode); } return list.get(0); }
实战: 赫夫曼树与数据压缩#
通过上面的介绍我们能直观的看出来，赫夫曼树很显眼的特征就是它是各个节点能组成的树中那颗WPL带权路径长度最短的树。
这条性质常用在数据压缩领域，即我们将现有的数据构建成一个赫夫曼树，其中出现次数越多的字符就越靠近根节点，经过这样的处理就能用最短的方式表示出原有字符。
假设我们有这条消息can you can a can as a canner can a can.
数据对计算机来说不过是0-1这样的数字, 我们看看将上面的字符转换成01这样的二进制数它长什么样子
1. 将原字符串的每一个char强转换成 byte == ASCII 99 97 110 32 121 111 117 32 99 97 110 32 97 32 99 97 110 32 97 115 32 97 32 99 97 110 110 101 114 32 99 97 110 32 97 32 99 97 110 2. 将byte toBinaryString 转换成01串如下: 1100011110000111011101000001111001110111111101011 0000011000111100001110111010000011000011000001100 0111100001110111010000011000011110011100000110000 1100000110001111000011101110100000110001111000011 1011101101110110010111100101000001100011110000111 011101000001100001100000110001111000011101110101110
也就是说，如果我们不对其进行压缩时它将会转换成上面那一大坨在网络上进行传输。
使用赫夫曼进行编码:
思路: 我们将can you can a can as a canner can a can中的每一个符号包括：点、空格全部封装进TreeNode
TreeNode中属性包含权重: 也就是字符出现的次数、包含data、字符本身
public class TreeNode implements Comparable{ // 存放权重就是字符出现的次数 private int weight; // 存放英文数值 private Byte data; // private TreeNode leftNode; private TreeNode rightNode;
封装完成后按照权重的大小倒序排序，各个节点长成这样:
a:11 :11 n:8 c:7 o:1 .:1 y:1 e:1 u:1 s:1 r:1
将赫夫曼树画出来长这样:
特征，我们让左侧的路径上的值是0、右边是1。因此通过这个赫夫曼树其实我们可以得到一张赫夫曼编码表。
比如像下面这样:
n: 00 : 01 a: 10 c: 111 // 每一个字符的编码就是从根节点到它的路径
有了这样编码表下一步就是对数据进行编码。怎么编码呢？其实就是做一下替换，我们现在开始循环遍历一开始的字符串，挨个取出里面的字符, 比如我们取出第一个字符是c，拿着c来查询这个表发现c的编码是111，于是我们将c替换成111。遍历到第二个字符是a，拿着a查询表发现a的值是10，于是我们将a替换成10，重复这个过程。最终我们得到的01串明显比原来短很多。
怎么完成解码呢? 解码也不复杂, 前提也是我们得获取到huffman编码表, 使用前缀匹配法, 比如我们现在接收到了
1111000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
使用前缀就是先取出1 去查查编码表有没有这个数？有的话就返回对应的字符，没有的话就用11再去匹配。
大家可以看看上面的那颗霍夫曼树，所有的data都在叶子节点上，所以使用前缀匹配完全可以，绝对不会出现重复的情况
- 使用java实现这个过程
思路概览:
- 将原生的字节数组转化成一个个的TreeNode
- 取出所有的TreeNode封装成赫夫曼树
- 通过赫夫曼树踢去出赫夫曼编码表
- 使用这个编码表进行编码
- 解码
private static byte[] huffmanZip(byte[] bytes) { // 先统计每个byte出现的次数,放入集合中 List<TreeNode> treeNodes = buildNodes(bytes); // 创建赫夫曼树 TreeNode node = createHuffmanTree(treeNodes); // 创建huffman编码表 Map<Byte, String> codes = createHuffmanCodeTable(node); // 编码, 将每一个byte替换成huffman编码表中的V byte[] encodeBytes = encodeHuffmanByte(bytes, codes); // 使用huffman编码进行解码 byte[] decodeBytes = decode(encodeBytes); return decodeBytes; }
将原生的byte数组，封装成一个个的TreeNode节点。保存在一个容器中并且记录下这个节点出现的次数, 因此我们需要将出现次数多的节点靠近根节点。
/** * 将byte转换成node集合 * * @param bytes * @return */ private static List<TreeNode> buildNodes(byte[] bytes) { ArrayList<TreeNode> list = new ArrayList<>(); HashMap<Byte, Integer> countMap = new HashMap<>(); // 统计每一个节点的出现的次数 for (byte aByte : bytes) { Integer integer = countMap.get(aByte); if (integer == null) { countMap.put(aByte, 1); } else { countMap.put(aByte, integer + 1); } } // 将k-v转化成node countMap.forEach((k, v) -> { list.add(new TreeNode(v, k)); }); return list; }
构建赫夫曼树
/** * 创建huffman树 * * @param treeNodes * @return */ private static TreeNode createHuffmanTree(List<TreeNode> treeNodes) { // 开始循环, 当集合中只剩下一棵树时 while (treeNodes.size() > 1) { // 排序 Collections.sort(treeNodes); // 取出权值最小的数 TreeNode leftNode = treeNodes.get(treeNodes.size() - 1); // 取出权值次要小的数 TreeNode rightNode = treeNodes.get(treeNodes.size() - 2); // 移除取出的两棵树 treeNodes.remove(leftNode); treeNodes.remove(rightNode); // 创建新的树根节点 TreeNode parentNode = new TreeNode(leftNode.getWeight() + rightNode.getWeight(), leftNode, rightNode); // 将新树放到原树的集合中 treeNodes.add(parentNode); } return treeNodes.get(0); }
从赫夫曼树中提取出编码表，思路: 下面是完了个递归，我们规定好左树是0，右边是1, 通过一个SpringBuilder每次迭代都记录下原来走过的路径，当判断到它的data不为空时，说明他就是叶子节点，立即保存这个节点曾经走过的路径，保存在哪里呢? 保存在一个map中，Key就是byte value就是走过的路径。
static StringBuilder stringBuilder = new StringBuilder(); static Map<Byte, String> huffCode = new HashMap<>(); /** * 创建huffman便编码表 * * @param node * @return */ private static Map<Byte, String> createHuffmanCodeTable(TreeNode node) { if (node == null) return null; getCodes(node.getLeftNode(), "0", stringBuilder); getCodes(node.getRightNode(), "1", stringBuilder); return huffCode; } /** * 根据node, 获取编码 * * @param node * @param code * @param stringBuilder */ private static void getCodes(TreeNode node, String code, StringBuilder stringBuilder) { StringBuilder sb = new StringBuilder(stringBuilder); sb.append(code); // 如果节点的data为空,说明根本不是叶子节点,接着递归 if (node.getData() == null) { getCodes(node.getLeftNode(), "0", sb); getCodes(node.getRightNode(), "1", sb); } else { // 如果是叶子节点,就记录它的data和路径 huffCode.put(node.getData(), sb.toString()); } }
根据赫夫曼编码表进行编码:
思路:
举个例子: 比如,原byte数组中的一个需要编码的字节是a
a的ASCII==97
97正常转成二进制的01串就是 0110 0001
但是现在我们有了编码表,就能根据97从编码表中取出编码: 10
换句话说,上面 0110 0001 和 10 地位相同
若干个需要编码的数append在一起,于是我们就有了一个比原来短一些的01串, 但是问题来了,到这里就结束了吗? 我们是将这些01串转换成String, 在getBytes()返回出去吗? 其实不是的,因为我们还需要进行解码,你想想解码不得编码map中往外取值? 取值不得有key? 我们如果在这里将这个01串的byte数组直接返回出去了,再按照什么样的方式将这个byte[]转换成String串呢? ,因为我们要从这个String串中解析出key
然后这里我们进行约定, 将现在得到的01串按照每8位为一组转换成int数, 再将这个int强转成byte, 解码的时候我们就知道了.就按照8位一组进行解码. 解析出来数组再转换成01串,我们就重新拿到了这个编码后的01串,它是个String串
每遇到8个0或者1,就将它强转成Int, 再强转成type, 经过这样的转换可能会出现负数,因此01串的最前面有个符号位,1表示负数
比如说: 如果你打印一下面代码中的encodeByte,你会发现打印的第一个数是-23, 这个-23被保存在新创建的byte数组的第一个位置上, 后续解码时,就从这个byte数组中的第一个位置上获取出这个-23, 将它转换成01二进制串
怎么转换呢? 比如不是-23, 而是-1 真值 1 原码:1,0001 补码: 2^(4+1) +1 = 100000 + (-1) = 1,1111 我们获取到的结果就是1111
/** * 进行编码 * * @param bytes * @param codes * @return */ private static byte[] encodeHuffmanByte(byte[] bytes, Map<Byte, String> codes) { StringBuilder builder = new StringBuilder(); for (byte aByte : bytes) { builder.append(codes.get(aByte)); } // 将这些byte按照每8位一组进行编码 int length = 0; if (builder.length() % 8 == 0) { length = builder.length() / 8; } else { length = builder.length() / 8 + 1; } // 用于存储压缩后的byte byte[] resultByte = new byte[length]; // 记录新byte的位置 int index = 0; // 遍历新得到的串 for (int i = 0; i < builder.length(); i += 8) { String str = null; if (i + 8 > builder.length()) { str = builder.substring(i); } else { str = builder.substring(i, i + 8); } // 将八位的二进制转换成byte // 这里出现负数了.... 涉及到补码的问题 byte encodeByte = (byte) Integer.parseInt(str, 2); // 存储起来 resultByte[index] = encodeByte; index++; } return resultByte; }
解码: 前面我们知道了,约定是按照8位转换成的int 再转换成type[] , 现在按照这个约定,反向转换出我们一开始的01串
/** * 按照指定的赫夫曼编码表进行解码 * * @param encodeBytes * @return */ private static byte[] decode(byte[] encodeBytes) { List<Byte> list = new ArrayList(); StringBuilder builder = new StringBuilder(); for (byte encodeByte : encodeBytes) { // 判断是否是最后一个,如果是最后一次不用用0补全, 因此最后一位本来就不够8位 boolean flag = encodeByte == encodeBytes[encodeBytes.length - 1]; String s = byteToBitStr(!flag, encodeByte); builder.append(s); } // 调换编码表的k-v Map<String, Byte> map = new HashMap<>(); huffCode.forEach((k, v) -> { map.put(v, k); }); // 处理字符串 for (int i = 0; i < builder.length(); ) { int count = 1; boolean flag = true; Byte b = null; while (flag){ String key = builder.substring(i,i+count); b=map.get(key); if (b==null){ count++; }else { flag=false; } } list.add(b); i+=count; } // 将list转数组 byte[] bytes = new byte[list.size()]; int i=0; for (Byte aByte : list) { bytes[i]=aByte; i++; } return bytes; } /** * 将byte转换成二进制的String * * @param b * @return */ public static String byteToBitStr(boolean flag, byte b) { /** * 目标: 全部保留八位.正数前面就补零, 负数前面补1 * 为什么选256呢? 因为我们前面约定好了, 按照8位进行分隔的 * 256的二进制表示是 1 0000 0000 * 假设我们现在是 1 * 计算 1 0000 0000 * 或 0 0000 0001 * ---------------------- * 1 0000 0001 * 结果截取8位就是 0000 0001 * * 假设我们现在是 -1 * 转换成二进制: 1111 1111 1111 1111 1111 1111 1111 1111 * * 计算 1 0000 0000 * 或 1111 1111 1111 1111 1111 1111 1111 1111 * ---------------------- * 1 1111 1111 * 结果截取8位就是 1111 1111 * * */ int temp = b; if (flag) { temp |= 256; } String str = Integer.toBinaryString(temp); if (flag) { return str.substring(str.length() - 8); } else { return str; } }
