浙江龙网

  1. 首页 > 生活百科 > >

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

生活百科

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

数据结构与算法【Java】08---树结构的实际应用

文章插图
3.4、生成赫夫曼编码和赫夫曼编码后的数据（数据压缩）我们已经生成了 赫夫曼树, 下面我们继续完成任务
  1. 生成赫夫曼树对应的赫夫曼编码 , 如下表:=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
  2. 使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码，将"i like like like java do you like a java"字符串生成对应的编码数据, 形式如下.10101000101111111100100010111111110010001011111111001001010011011100011100000110111010001111001010 00101111111100110001001010011011100
1、生成赫夫曼树对应的赫夫曼编码
代码实现
//测试是否生成了对应的赫夫曼编码Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);System.out.println("生成的对应的赫夫曼编码="+ HuffmanCode.huffmanCodes);//...//生成赫夫曼树对应的赫夫曼编码//思路://1. 将赫夫曼编码表存放在 Map<Byte,String> 形式//生成的赫夫曼编码表{32（空格）=01, 97（a）=100, 100(...)=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();//2. 在生成赫夫曼编码表示，需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();//为了调用方便，我们重载 getCodesprivate static Map<Byte, String> getCodes(Node root) {if(root == null) {return null;}//处理root的左子树getCodes(root.left, "0", stringBuilder);//处理root的右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/** * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合 * @param node传入结点 * @param code路径： 左子结点是 0, 右子结点 1 * @param stringBuilder 用于拼接路径 */private static void getCodes(Node node,String code,StringBuilder stringBuilder){StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);//将code加入到 stringBuilder2 （拼接路径）stringBuilder2.append(code);if (node != null){//如果node等于空，不处理//判断当前node是叶子节点还是非叶子结点if (node.data =https://www.huyubaike.com/biancheng/= null){//非叶子节点//递归处理//向左递归getCodes(node.left,"0", stringBuilder2);//向右递归getCodes(node.right, "1", stringBuilder2);}else {//进入到这里说明是叶子节点，找到了最后huffmanCodes.put(node.data,stringBuilder2.toString());}}}结果：
数据结构与算法【Java】08---树结构的实际应用

文章插图
2、使用赫夫曼编码来生成赫夫曼编码数据
代码实现
//测试返回byte数组byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);System.out.println("huffmanCodeBytes="+Arrays.toString(huffmanCodeBytes));//17//...//编写一个方法，将字符串对应的byte[] 数组 ， 通过生成的赫夫曼编码表 ， 返回一个赫夫曼编码 压缩后的byte[]/** * * @param bytes 这是原始的字符串对应的 byte[] * @param huffmanCodes 生成的赫夫曼编码map * @return 返回赫夫曼编码处理后的 byte[] * 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes(); * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100" * => 对应的 byte[] huffmanCodeBytes ， 即 8位对应一个 byte,放入到 huffmanCodeBytes * huffmanCodeBytes[0] =10101000(补码) => byte[推导10101000=> 10101000 - 1 => 10100111(反码)=> 11011000（原码）= -88 ] * huffmanCodeBytes[1] = -88 */private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {//1.利用 huffmanCodes 将bytes 转成赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();//遍历bytes 数组for(byte b: bytes) {stringBuilder.append(huffmanCodes.get(b));}//System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());//将 "1010100010111111110..." 转成 byte[]//统计返回byte[] huffmanCodeBytes 长度//一句话 int len = (stringBuilder.length() + 7) / 8;int len;if(stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}//创建 存储压缩后的 byte数组byte[] huffmanCodeBytes = new byte[len];int index = 0;//记录是第几个bytefor (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8String strByte;if(i+8 > stringBuilder.length()) {//不够8位strByte = stringBuilder.substring(i);}else{strByte = stringBuilder.substring(i, i + 8);}//将strByte 转成一个byte,放入到 huffmanCodeByteshuffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}

推荐阅读


上一篇：frp服务利用云主机实现Windows远程连接

下一篇：「Tubian」Tubian0.41!支持Windows QQ微信！