第 11 章树结构实际应用

1、堆排序

1.1、堆排序基本介绍

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序。
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

完全二叉树：一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树

一般升序采用大顶堆，降序采用小顶堆
大顶堆特点：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]，i 对应第几个节点，i 从0 开始编号

小顶堆特点：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] ，i 对应第几个节点，i 从 0 开始编号

1.2、堆排序基本思想

将待排序序列构造成一个大顶堆

此时，整个序列的最大值就是堆顶的根节点

将其与末尾元素进行交换，此时末尾就为最大值

然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了

1.3、堆排序步骤图解说明

1.3.1、构造大顶堆

首先构造初始堆，将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆），假设原始数组为 [4, 6, 8, 5, 9]

此时我们从最后一个非叶子结点开始（叶子结点自然不用调整，第一个非叶子结点
arr.length/2-1=5/2-1=1，也就是下面的 6 结点），从左至右，从下至上进行调整。

找到第二个非叶节点 4，由于[4,9,8]中 9 元素最大，4 和 9 交换

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换 4 和 6

1.3.2、丢弃堆顶元素

将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换，步骤如下：
将堆顶元素 9 和末尾元素 4 进行交换

1.3.3、重操旧业

照着之前的方法重新调整结构：将栈顶元素 4 与节点 8 互换，使其继续满足堆定义

再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

1.4、堆排序代码思路

1.4.1、堆排序基本思路

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

1.4.2、编码思路

先将数组转为大顶堆，怎么转？

先来个完全二叉树，节点编号从 0 开始

从最深层的非叶子节点开始转换，将最深层的非叶子节点 4 转为大顶堆，即将节点 4 的值与其左右子节点（如果有右节点的话）的值相比较，节点 9 的值大于节点 4 的值，进行交换，交换后，以节点 4 为根节点的子树就是大顶堆咯

再去到倒数第二个非叶子节点，执行上述操作，倒数第二个非叶子节点为节点 3 ，将节点 3 的值与节点 8 的值互换，交换后，以节点 3 为根节点的子树就是大顶堆咯

再去到倒数第三个非叶子节点，执行上述操作，倒数第三个非叶子节点为节点 2 ，节点 2 满足大顶堆，无需执行交换

再去到倒数第四个非叶子节点，执行上述操作，倒数第四个非叶子节点为节点 2 ，节点 2 满足大顶堆，无需执行交换

可以看到，这里出现了特例，由于节点 1 的数值比较小，导致以节点 3 为根节点的子树无法构成大顶堆，也导致了以节点 1 为根节点的子树无法构成大顶堆

如何解决这个问题？假设当前非叶子节点为 nonLeafNode ，与其交换值的节点为 exNode ，当每次 nonLeafNode 与 exNode 交换值之后，还要去到以 exNode 为根节点的更深层子树，将 exNode 的子树调整为大顶堆

以此类推… ，直至退到整棵树的根节点

将整个数组转换为大顶堆之后，将堆顶元素与数组最后一个元素交换位置，这样数组最后一个元素就是整个数组中最大的元素，我们就不用管它了

现在我们拿着新的完全二叉树：节点 0 到节点 8 ，将其调整为大顶堆

这样来想：节点 1 至节点 8 已经满足大顶堆的特点了，现在只需要把节点 0 沉下去，把最大的节点浮上来，就又是一棵新的大顶堆啦~~~

怎么沉？那不还是之前的步骤嘛，判断当前节点值与其左右子节点值的大小

如果无需交换：恭喜，已经是大顶堆了
如果需要交换：假设当前非叶子节点为 nonLeafNode ，与其交换值的节点为 exNode ，交换节点的值后，还要去到以 exNode 为根节点的更深层子树，将 exNode 的子树调整为大顶堆

1.5、堆排序代码实现

1.5.1、理解堆排序

逐步分解堆排序

public class HeapSort {
  public static void main(String[] args) {
    // 要求将数组进行升序排序
    int arr[] = {4, 6, 8, 5, 9};
    heapSort(arr);
    System.out.println("排序后=" + Arrays.toString(arr));
  }
  // 编写一个堆排序的方法
  public static void heapSort(int arr[]) {
    int temp = 0;
    int length = arr.length;
    //分步完成
    adjustHeap(arr, 1, length);
    System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6
    adjustHeap(arr, 0, length);
    System.out.println("第2次" + Arrays.toString(arr)); // 9,6,8,5,4
    temp = arr[length - 1];
    arr[length - 1] = arr[0];
    arr[0] = temp;
    length -= 1;
    adjustHeap(arr, 0, length); 
    System.out.println("第3次" + Arrays.toString(arr)); // 8,6,4,5,9
    temp = arr[length - 1];
    arr[length - 1] = arr[0];
    arr[0] = temp;
    length -= 1;
    adjustHeap(arr, 0, length); 
    System.out.println("第4次" + Arrays.toString(arr)); // 6,5,4,8,9
    temp = arr[length - 1];
    arr[length - 1] = arr[0];
    arr[0] = temp;
    length -= 1;
    adjustHeap(arr, 0, length); 
    System.out.println("第5次" + Arrays.toString(arr)); // 5,4,6,8,9
    temp = arr[length - 1];
    arr[length - 1] = arr[0];
    arr[0] = temp;
    length -= 1;
    adjustHeap(arr, 0, length); 
    System.out.println("第6次" + Arrays.toString(arr)); // 4,5,6,8,9
  }
    // 将一个数组(二叉树), 调整成一个大顶堆
    /**
     * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 =>
     * adjustHeap => 得到 {4, 9, 8, 5, 6} 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9,
     * 8, 5, 6} => {9,6,8,5, 4}
     * 
     * @param arr    待调整的数组
     * @param i      表示非叶子结点在数组中索引
     * @param length 表示对多少个元素继续调整， length 是在逐渐的减少
     */
    public static void adjustHeap(int arr[], int i, int length) {
        int temp = arr[i];// 先取出当前元素的值，保存在临时变量
        // 开始调整
        // 说明
        // 1. k = i * 2 + 1 ：k 是 i结点的左子结点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) { // 说明左子结点的值小于右子结点的值
                k++; // k 指向右子结点
            }
            if (arr[k] > temp) { // 如果子结点大于父结点
                arr[i] = arr[k]; // 把较大的值赋给当前结点
                i = k; // !!! i 指向 k，将小的值沉下去
            } else {
                break; // !!! 由于是从最深处往前调整，我能保证下面的子树已经是大顶堆了
            }
        }
        // 当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
        arr[i] = temp;// 将temp值放到调整后的位置
    }
}

程序运行结果

第一次[4, 9, 8, 5, 6]
第2次[9, 6, 8, 5, 4]
第3次[8, 6, 4, 5, 9]
第4次[6, 5, 4, 8, 9]
第5次[5, 4, 6, 8, 9]
第6次[4, 5, 6, 8, 9]
排序后=[4, 5, 6, 8, 9]

1.5.2、编写堆排序

编写堆排序算法

// 编写一个堆排序的方法
public static void heapSort(int arr[]) {
  int temp = 0;
  // 完成我们最终代码
  // 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
  for (int i = arr.length / 2 - 1; i >= 0; i--) {
    adjustHeap(arr, i, arr.length);
  }
  /*
   * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
   * 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
   */
  for (int j = arr.length - 1; j > 0; j--) {
    // 交换
    temp = arr[j];
    arr[j] = arr[0];
    arr[0] = temp;
    adjustHeap(arr, 0, j);
  }
}
// 将一个数组(二叉树), 调整成一个大顶堆
/**
 * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 =>
 * adjustHeap => 得到 {4, 9, 8, 5, 6} 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9,
 * 8, 5, 6} => {9,6,8,5, 4}
 * 
 * @param arr    待调整的数组
 * @param i      表示非叶子结点在数组中索引
 * @param length 表示对多少个元素继续调整， length 是在逐渐的减少
 */
public static void adjustHeap(int arr[], int i, int length) {
  int temp = arr[i];// 先取出当前元素的值，保存在临时变量
  // 开始调整
  // 说明
  // 1. k = i * 2 + 1 ：k 是 i结点的左子结点
  for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
    if (k + 1 < length && arr[k] < arr[k + 1]) { // 说明左子结点的值小于右子结点的值
      k++; // k 指向右子结点
    }
    if (arr[k] > temp) { // 如果子结点大于父结点
      arr[i] = arr[k]; // 把较大的值赋给当前结点
      i = k; // !!! i 指向 k，将小的值沉下去
    } else {
      break; // !!! 由于是从最深处往前调整，我能保证下面的子树已经是大顶堆了
    }
  }
  // 当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
  arr[i] = temp;// 将temp值放到调整后的位置
}

1.5.3、代码测试

测试代码

public static void main(String[] args) {
    // 要求将数组进行升序排序
    int arr[] = {4, 6, 8, 5, 9};
    heapSort(arr);
    System.out.println("排序后=" + Arrays.toString(arr));
}

程序运行结果

排序后=[4, 5, 6, 8, 9]

1.5.4、测试堆排序性能

测试代码

public class HeapSort {
  public static void main(String[] args) {
    // 创建要给80000个的随机的数组
    int[] arr = new int[8000000];
    for (int i = 0; i < 8000000; i++) {
      arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    }
    System.out.println("排序前");
    Date data1 = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String date1Str = simpleDateFormat.format(data1);
    System.out.println("排序前的时间是=" + date1Str);
    heapSort(arr);
    Date data2 = new Date();
    String date2Str = simpleDateFormat.format(data2);
    System.out.println("排序前的时间是=" + date2Str);
  }
  // 编写一个堆排序的方法
  public static void heapSort(int arr[]) {
    int temp = 0;
    // 完成我们最终代码
    // 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
      adjustHeap(arr, i, arr.length);
    }
    /*
     * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
     * 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
     */
    for (int j = arr.length - 1; j > 0; j--) {
      // 交换
      temp = arr[j];
      arr[j] = arr[0];
      arr[0] = temp;
      adjustHeap(arr, 0, j);
    }
  }
  // 将一个数组(二叉树), 调整成一个大顶堆
  /**
   * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 =>
   * adjustHeap => 得到 {4, 9, 8, 5, 6} 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9,
   * 8, 5, 6} => {9,6,8,5, 4}
   * 
   * @param arr    待调整的数组
   * @param i      表示非叶子结点在数组中索引
   * @param length 表示对多少个元素继续调整， length 是在逐渐的减少
   */
  public static void adjustHeap(int arr[], int i, int length) {
    int temp = arr[i];// 先取出当前元素的值，保存在临时变量
    // 开始调整
    // 说明
    // 1. k = i * 2 + 1 ：k 是 i结点的左子结点
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
      if (k + 1 < length && arr[k] < arr[k + 1]) { // 说明左子结点的值小于右子结点的值
        k++; // k 指向右子结点
      }
      if (arr[k] > temp) { // 如果子结点大于父结点
        arr[i] = arr[k]; // 把较大的值赋给当前结点
        i = k; // !!! i 指向 k，将小的值沉下去
      } else {
        break; // !!! 由于是从最深处往前调整，我能保证下面的子树已经是大顶堆了
      }
    }
    // 当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
    arr[i] = temp;// 将temp值放到调整后的位置
  }
}

程序运行结果：牛批，八百万数据 1s 搞定

排序前
排序前的时间是=2020-07-18 17:13:27
排序前的时间是=2020-07-18 17:13:28

2、赫夫曼树

2.1、赫夫曼树基本介绍

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

2.2、赫夫曼树重要概念

路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1 ，则从根结点到第 L 层结点的路径长度为 L-1
结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ，权值越大的结点离根结点越近的二叉树才是最优二叉树。WPL 最小的就是赫夫曼树

2.3、赫夫曼树创建思路图解

创建赫夫曼树的流程

核心思想：让权值小的节点远离根节点，让权值大的节点靠近根节点
从小到大进行排序，将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树（左右节点都为空的二叉树）
取出根节点权值最小的两颗二叉树，组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复以上的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

以数组 { 13, 7, 8, 3, 29, 6, 1 } 为例，排序后的数组为 { 1, 3, 6, 7, 8, 13, 29 }

取出最小的两颗二叉树： 1 和 3 ，组成一棵二叉树，其根节点权值为 1+ 3 = 4 ，将权值为 4 的二叉树放回原数组中，重新进行排序，得到 { 4, 6, 7, 8, 13, 29 }

取出最小的两颗二叉树： 4 和 6 ，组成一棵二叉树，其根节点权值为 4+ 6 = 10 ，将权值为 10 的二叉树放回原数组中，重新进行排序，得到 { 7, 8, 10, 13, 29 }

继续取出最小的两颗二叉树： 7 和 8，组成一棵二叉树，其根节点权值为 7+ 8= 15，将权值为 15 的二叉树放回原数组中，重新进行排序，得到 { 10, 15, 13, 29 }

以此类推，直至最后一个根节点，将得到如下结果：

编码思路：

将集合中的二叉树排序，从中取两个最权值最低的二叉树组成新的二叉树
将新的二叉树放回集合中，再从中取两个最权值最低的二叉树组成新的二叉树
如此往复 …

何时结束？集合中只剩一个元素时，即为整棵赫夫曼树的根节点

2.4、赫夫曼树代码实现

树节点的定义

// 创建结点类
// 为了让Node 对象支持排序：Collections集合排序
// 让Node 实现Comparable接口
class Node implements Comparable<Node> {
  int value; // 结点权值
  Node left; // 指向左子结点
  Node right; // 指向右子结点
  // 写一个前序遍历
  public void preOrder() {
    System.out.println(this);
    if (this.left != null) {
      this.left.preOrder();
    }
    if (this.right != null) {
      this.right.preOrder();
    }
  }
  public Node(int value) {
    this.value = value;
  }
  @Override
  public String toString() {
    return "Node [value=" + value + "]";
  }
  @Override
  public int compareTo(Node o) {
    // 表示从小到大排序
    return this.value - o.value;
  }
}

创建赫夫曼树

// 创建赫夫曼树的方法
/**
 * 
 * @param arr 需要创建成哈夫曼树的数组
 * @return 创建好后的赫夫曼树的root结点
 */
public static Node createHuffmanTree(int[] arr) {
  // 第一步为了操作方便
  // 1. 遍历 arr 数组
  // 2. 将arr的每个元素构成成一个Node
  // 3. 将Node 放入到ArrayList中
  List<Node> nodes = new ArrayList<Node>();
  for (int value : arr) {
    nodes.add(new Node(value));
  }
  // 我们处理的过程是一个循环的过程
  while (nodes.size() > 1) {
    // 排序 从小到大
    Collections.sort(nodes);
    // 取出根节点权值最小的两颗二叉树
    // (1) 取出权值最小的结点（二叉树）
    Node leftNode = nodes.get(0);
    // (2) 取出权值第二小的结点（二叉树）
    Node rightNode = nodes.get(1);
    // (3)构建一颗新的二叉树
    Node parent = new Node(leftNode.value + rightNode.value);
    parent.left = leftNode;
    parent.right = rightNode;
    // (4)从ArrayList删除处理过的二叉树
    nodes.remove(leftNode);
    nodes.remove(rightNode);
    // (5)将parent加入到nodes
    nodes.add(parent);
  }
  // 返回哈夫曼树的root结点
  return nodes.get(0);
}

测试代码

public static void main(String[] args) {
  int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
  Node root = createHuffmanTree(arr);
  preOrder(root); 
}
// 编写一个前序遍历的方法
public static void preOrder(Node root) {
  if (root != null) {
    root.preOrder();
  } else {
    System.out.println("是空树，不能遍历~~");
  }
}

程序运行结果

Node [value=67]
Node [value=29]
Node [value=38]
Node [value=15]
Node [value=7]
Node [value=8]
Node [value=23]
Node [value=10]
Node [value=4]
Node [value=1]
Node [value=3]
Node [value=6]
Node [value=13]

2.5、赫夫曼树全部代码

public class HuffmanTree {
  public static void main(String[] args) {
    int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
    Node root = createHuffmanTree(arr);
    preOrder(root); 
  }
  // 编写一个前序遍历的方法
  public static void preOrder(Node root) {
    if (root != null) {
      root.preOrder();
    } else {
      System.out.println("是空树，不能遍历~~");
    }
  }
  // 创建赫夫曼树的方法
  /**
   * 
   * @param arr 需要创建成哈夫曼树的数组
   * @return 创建好后的赫夫曼树的root结点
   */
  public static Node createHuffmanTree(int[] arr) {
    // 第一步为了操作方便
    // 1. 遍历 arr 数组
    // 2. 将arr的每个元素构成成一个Node
    // 3. 将Node 放入到ArrayList中
    List<Node> nodes = new ArrayList<Node>();
    for (int value : arr) {
      nodes.add(new Node(value));
    }
    // 我们处理的过程是一个循环的过程
    while (nodes.size() > 1) {
      // 排序 从小到大
      Collections.sort(nodes);
      // 取出根节点权值最小的两颗二叉树
      // (1) 取出权值最小的结点（二叉树）
      Node leftNode = nodes.get(0);
      // (2) 取出权值第二小的结点（二叉树）
      Node rightNode = nodes.get(1);
      // (3)构建一颗新的二叉树
      Node parent = new Node(leftNode.value + rightNode.value);
      parent.left = leftNode;
      parent.right = rightNode;
      // (4)从ArrayList删除处理过的二叉树
      nodes.remove(leftNode);
      nodes.remove(rightNode);
      // (5)将parent加入到nodes
      nodes.add(parent);
    }
    // 返回哈夫曼树的root结点
    return nodes.get(0);
  }
}
// 创建结点类
// 为了让Node 对象支持排序：Collections集合排序
// 让Node 实现Comparable接口
class Node implements Comparable<Node> {
  int value; // 结点权值
  Node left; // 指向左子结点
  Node right; // 指向右子结点
  // 写一个前序遍历
  public void preOrder() {
    System.out.println(this);
    if (this.left != null) {
      this.left.preOrder();
    }
    if (this.right != null) {
      this.right.preOrder();
    }
  }
  public Node(int value) {
    this.value = value;
  }
  @Override
  public String toString() {
    return "Node [value=" + value + "]";
  }
  @Override
  public int compareTo(Node o) {
    // 表示从小到大排序
    return this.value - o.value;
  }
}

3、赫夫曼编码

3.1、赫夫曼编码基本介绍

赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，属于一种程序算法
赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间
赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码

3.2、定长编码与变长编码

3.2.1、定长编码

通信领域中信息的处理方式：定长编码，比如我需要发送如下字符串：

i like like like java do you like a java    // 共40个字符(包括空格)

上述字符串对应的 ASCII 码为：

105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //对应Ascii码
01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001   //对应的二进制

01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001   //对应的二进制

•按照二进制来传递信息，总的长度是 359 (包括空格)

3.2.2、变长编码

通信领域中信息的处理方式：变长编码，比如我需要发送如下字符串：

i like like like java do you like a java    // 共40个字符(包括空格)

统计上述字符串出现的各字符出现的次数

d:1 y:1 u:1 j:2  v:2  o:2  l:4  k:4  e:4 i:5  a:5   :9  // 各个字符对应的个数

•按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如空格出现了9 次，编码为0 ,其它依次类推

0=  ,  1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d

按照上面给各个字符规定的编码，则我们在传输数据时，编码就是：

10010110100...

•缺点：我怎么解码嘞？我是取 1 、还是取 10 、还是取 100 、还是取 1001？

3.3、赫夫曼编码原理剖析

通信领域中信息的处理方式：赫夫曼编码
字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码，即不能匹配到重复的编码
比如我们处理如下字符串

i like like like java do you like a java       // 共40个字符(包括空格)

统计各字符

d:1 y:1 u:1 j:2  v:2  o:2  l:4  k:4  e:4 i:5  a:5   :9  // 各个字符对应的个数

按照上面字符出现的次数构建一颗赫夫曼树，次数作为权值，根据赫夫曼编码表确定具体字符的编码

根据赫夫曼树，给各个字符的编码：向左的路径为 0 ；向右的路径为1

o: 1000   u: 10010  d: 100110  y: 100111  i: 101
a: 110    k: 1110   e: 1111    j: 0000    v: 0001
l: 001     : 01

按照上面的赫夫曼编码，我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)

1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110

编码后长度为 133 ，原来长度是 359 , 压缩了 (359-133) / 359 = 62.9% ，此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀，不会造成匹配的多义性

想想为啥赫夫曼编码就是前缀比编码？从根节点向左（右）走，只有走到叶子节点才是真正需要编码的字符，看图即可明白~

注意，这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl 是一样的，都是最小的

比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树如下，所以我们生成二叉树时，一定要记录该二叉树对应的赫夫曼编码表~~~
为什么会这样捏？权重相同的节点都位于二叉树的同一层，虽然编码具体值会发生变化，但是编码长度不会变化呀

3.4、赫夫曼编码思路

统计字节数组中各个数据的权重
将字节数组按照上面的权重值创建赫夫曼树
根据上面创建的赫夫曼树获得每个数值对应的可变长编码值（往左走为 0 ，往右走为 1）
以每个数值新的编码重新对字符数组进行编码，即可得到赫夫曼编码后的值

3.5、赫夫曼编码算法

3.5.1、赫夫曼节点定义

每个 data 值对应着一个权重值 weight

//创建Node ,待数据和权值
class Node implements Comparable<Node> {
  Byte data; // 存放数据(字符)本身，比如'a' => 97 ' ' => 32
  int weight; // 权值, 表示字符出现的次数
  Node left;//
  Node right;
  public Node(Byte data, int weight) {
    this.data = data;
    this.weight = weight;
  }
  @Override
  public int compareTo(Node o) {
    // 从小到大排序
    return this.weight - o.weight;
  }
  public String toString() {
    return "Node [data = " + data + " weight=" + weight + "]";
  }
  // 前序遍历
  public void preOrder() {
    System.out.println(this);
    if (this.left != null) {
      this.left.preOrder();
    }
    if (this.right != null) {
      this.right.preOrder();
    }
  }
}

3.5.2、获取数据权重

获取字节数组中每个数值对应的权重值

/**
 * 
 * @param bytes 接收字节数组
 * @return 返回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
 */
private static List<Node> getNodes(byte[] bytes) {
  // 1创建一个ArrayList
  ArrayList<Node> nodes = new ArrayList<Node>();
  // 遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
  Map<Byte, Integer> counts = new HashMap<>();
  for (byte b : bytes) {
    Integer count = counts.get(b);
    if (count == null) { // Map还没有这个字符数据,第一次
      counts.put(b, 1);
    } else {
      counts.put(b, count + 1);
    }
  }
  // 把每一个键值对转成一个Node 对象，并加入到nodes集合
  // 遍历map
  for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
    nodes.add(new Node(entry.getKey(), entry.getValue()));
  }
  return nodes;
}

3.5.3、创建赫夫曼树

统计字节数组中每个数值出现的次数，即每个数值对应的权重值，并根据数值及其权重值，来创建赫夫曼树

// 可以通过List 创建对应的赫夫曼树
private static Node createHuffmanTree(List<Node> nodes) {
  while (nodes.size() > 1) {
    // 排序, 从小到大
    Collections.sort(nodes);
    // 取出第一颗最小的二叉树
    Node leftNode = nodes.get(0);
    // 取出第二颗最小的二叉树
    Node rightNode = nodes.get(1);
    // 创建一颗新的二叉树,它的根节点 没有data, 只有权值
    Node parent = new Node(null, leftNode.weight + rightNode.weight);
    parent.left = leftNode;
    parent.right = rightNode;
    // 将已经处理的两颗二叉树从nodes删除
    nodes.remove(leftNode);
    nodes.remove(rightNode);
    // 将新的二叉树，加入到nodes
    nodes.add(parent);
  }
  // nodes 最后的结点，就是赫夫曼树的根结点
  return nodes.get(0);
}

3.5.4、生成赫夫曼编码表

根据上面生成的赫夫曼树，获取字节数组中每个数值对应的可变长编码

// 生成赫夫曼树对应的赫夫曼编码
// 思路:将赫夫曼编码表存放在 Map<Byte,String> 形式
// 生成的赫夫曼编码表{32=01, 97=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>();
// 为了调用方便，我们重载 getCodes
private static Map<Byte, String> getCodes(Node root) {
  if (root == null) {
    return null;
  }
  // 处理root的左子树
  getCodes(root.left, "0", new StringBuilder());
  // 处理root的右子树
  getCodes(root.right, "1", new StringBuilder());
  return huffmanCodes;
}
/**
 * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合
 * @param node  传入结点
 * @param code  路径： 左子结点是 0, 右子结点 1
 * @param stringBuilder 用于拼接路径
 */
private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
  // 因为对象传递的是引用，所以不能再原有的 StringBuilder 上进行操作
    StringBuilder curNodeCode = new StringBuilder(stringBuilder);
  // 将code 加入到  curNodeCode
  curNodeCode.append(code);
  if (node != null) { // 如果node == null不处理
    // 判断当前node 是叶子结点还是非叶子结点
    if (node.data == null) { // 非叶子结点
      // 递归处理
      // 向左递归
      getCodes(node.left, "0", curNodeCode);
      // 向右递归
      getCodes(node.right, "1", curNodeCode);
    } else { // 说明是一个叶子结点
      // 就表示找到某个叶子结点的最后
      huffmanCodes.put(node.data, curNodeCode.toString());
    }
  }
}

3.5.5、生成赫夫曼编码

根据原字节数组及其对应的赫夫曼编码表，生成赫夫曼编码，我觉着老师的编码方式有问题，关键就在于最后一个字节，最后一个字节很有可能不满 8 个 bit
要么在前面填充 0 ，要么在后面填充 0 ，然后二进制字符串转换为 byte ，想想：

如果在前面填充 0 ，解码的时候，你怎么知道前面的 0 ，从哪个 0 开始算起才是有效的 0 ？？？就比如说最后一个字节编码为 01100 ，好，我们就在前面全填充 0 ，即最后一个字节为 0001100 ，来，你解码的时候，给我把它解出来，是 0001100 、还是 001100、还是 01100 、还是 1100 ？根本无从下手。。。

如果在后面填充 0 ，解码的时候，你怎么知道后面的 0 ，从哪个 0 开始算起才是有效的 0 ？？？就比如说最后一个字节编码为 01100 ，好，我们就在后面全填充 0 ，即最后一个字节为 00110000 ，来，你解码的时候，给我把它解出来，是 0011 、还是 00110、还是 001100 、还是 0011000 、还是 00110000 ？根本无从下手。。。

所以在赫夫曼编码生成的字节数组最后额外开辟了一个空间，用来存储最后一个字节的有效位数，这样就没得问题啦~~~

//编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
/**
 * 
 * @param bytes 这是原始的字符串对应的 byte[]
 * @param huffmanCodes 生成的赫夫曼编码map
 * @return 返回赫夫曼编码处理后的 byte[] 
 * 
 */
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));
  }
  // 统计返回 byte[] huffmanCodeBytes 长度
  // 一句话 int len = (stringBuilder.length() + 7) / 8;
  int len;
  byte countToEight = (byte) (stringBuilder.length() % 8);
  if (countToEight == 0) {
    len = stringBuilder.length() / 8;
  } else {
    len = stringBuilder.length() / 8 + 1;
    // 后面补零
    for (int i = countToEight; i < 8; i++) {
      stringBuilder.append('0');
    }
  }
  // 创建 存储压缩后的 byte数组，huffmanCodeBytes[len]记录赫夫曼编码最后一个字节的有效位数
  byte[] huffmanCodeBytes = new byte[len + 1];
  huffmanCodeBytes[len] = countToEight;
  int index = 0;// 记录是第几个byte
  for (int i = 0; i < stringBuilder.length(); i += 8) { // 因为是每8位对应一个byte,所以步长 +8
    String strByte;
    strByte = stringBuilder.substring(i, i + 8);
    // 将strByte 转成一个byte,放入到 huffmanCodeBytes
    huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
    index++;
  }
  return huffmanCodeBytes;
}

3.5.6、代码测试

代码

public static void main(String[] args) {
    //如何将 数据进行解压(解码)  
    //分步过程
    String content = "i like like like java do you like a java";
    byte[] contentBytes = content.getBytes();
    List<Node> nodes = getNodes(contentBytes);
    System.out.println("nodes=" + nodes);
    //测试一把，创建的赫夫曼树
    System.out.println("生成赫夫曼树");
    Node huffmanTreeRoot = createHuffmanTree(nodes);
    System.out.println("前序遍历");
    huffmanTreeRoot.preOrder();
    //测试一把是否生成了对应的赫夫曼编码
    Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    System.out.println("~生成的赫夫曼编码表= " + huffmanCodes);
    //测试
    byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
    System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));//17
    //发送huffmanCodeBytes 数组 
}

程序运行结果

nodes=[Node [data = 32 weight=9], Node [data = 97 weight=5], Node [data = 100 weight=1], Node [data = 101 weight=4], Node [data = 117 weight=1], Node [data = 118 weight=2], Node [data = 105 weight=5], Node [data = 121 weight=1], Node [data = 106 weight=2], Node [data = 107 weight=4], Node [data = 108 weight=4], Node [data = 111 weight=2]]
生成赫夫曼树
前序遍历
Node [data = null weight=40]
Node [data = null weight=17]
Node [data = null weight=8]
Node [data = 108 weight=4]
Node [data = null weight=4]
Node [data = 106 weight=2]
Node [data = 111 weight=2]
Node [data = 32 weight=9]
Node [data = null weight=23]
Node [data = null weight=10]
Node [data = 97 weight=5]
Node [data = 105 weight=5]
Node [data = null weight=13]
Node [data = null weight=5]
Node [data = null weight=2]
Node [data = 100 weight=1]
Node [data = 117 weight=1]
Node [data = null weight=3]
Node [data = 121 weight=1]
Node [data = 118 weight=2]
Node [data = null weight=8]
Node [data = 101 weight=4]
Node [data = 107 weight=4]
~生成的赫夫曼编码表= {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
huffmanCodeBytes=[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, -32, 5]

3.5.7、封装赫夫曼编码函数

将上述操作封装成一个函数，对外暴露该方法即可

// 使用一个方法，将前面的方法封装起来，便于我们的调用.
/**
 * 
 * @param bytes 原始的字符串对应的字节数组
 * @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
 */
private static byte[] huffmanZip(byte[] bytes) {
  List<Node> nodes = getNodes(bytes);
  // 根据 nodes 创建的赫夫曼树
  Node huffmanTreeRoot = createHuffmanTree(nodes);
  // 对应的赫夫曼编码(根据 赫夫曼树)
  Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
  // 根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
  byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
  return huffmanCodeBytes;
}

3.6、赫夫曼解码

3.6.1、字节转二进制字符串

1、字节转二进制字符串方法

编写将字节转换为二进制字符串的方法

正数：高位补 0 即可，然后截取低八位即可；
负数直接截取低八位即可，其实往第八位（索引从 0 开始）补个 1 也没事儿。。。8 位的负数转为 32 位的负数，其 8~31 位都是 1

// 将 byte 转换为对应的字符串
private static String byteToBitString(byte b) {
    // 使用变量保存 b
    int temp = b; // 将 b 转成 int  
    temp |= 0x100; // 如果是正数我们需要将高位补零
    // 转换为二进制字符串，正数：高位补 0 即可，然后截取低八位即可；负数直接截取低八位即可
    // 负数在计算机内存储的是补码，补码转原码：先 -1 ，再取反
    String binaryStr = Integer.toBinaryString(temp);
    return binaryStr.substring(binaryStr.length() - 8);
}

2、关于二进制的理解

测试代码 1：

public static void main(String[] args) {
  byte b = (byte) Integer.parseInt("11110000", 2);
  System.out.println(b);
  String byteToBitString = byteToBitString(b);
  System.out.println(byteToBitString);
}
// 将 byte 转换为对应的字符串
private static String byteToBitString(byte b) {
  // 使用变量保存 b
  int temp = b; // 将 b 转成 int   
  temp |= 0x100; // 如果是正数我们需要将高位补零
  // 转换为二进制字符串，正数：高位补 0 即可，然后截取低八位即可；负数直接截取低八位即可
  // 负数在计算机内存储的是补码，补码转原码：先 -1 ，再取反
  String binaryStr = Integer.toBinaryString(temp);
  return binaryStr.substring(binaryStr.length() - 8);
}

程序运行结果

-16
11110000

测试代码 2：

@SuppressWarnings("unused")
public static void main(String[] args) {
  byte b = (byte) Integer.parseInt("01110000", 2);
  System.out.println(b);
  String byteToBitString = byteToBitString(b);
  System.out.println(byteToBitString);
}
// 将 byte 转换为对应的字符串
private static String byteToBitString(byte b) {
  // 使用变量保存 b
  int temp = b; // 将 b 转成 int   
  temp |= 0x100; // 如果是正数我们需要将高位补零
  // 转换为二进制字符串，正数：高位补 0 即可，然后截取低八位即可；负数直接截取低八位即可
  // 负数在计算机内存储的是补码，补码转原码：先 -1 ，再取反
  String binaryStr = Integer.toBinaryString(temp);
  return binaryStr.substring(binaryStr.length() - 8);
}

程序运行结果

112
01110000

关于字节转二进制字符串的总结：

为什么要在正数的第八位（索引从 0 开始）补个 1 ，就能实现高位补零的效果？
因为如果不补零，调用 Integer.toBinaryString(temp); 方法，只会从第一个非零元素开始输出，会将高位的 0 抹去
8 位的正数转为 32 位正数，其 8~31 2位都是零，在其的第八位补个 1 ，就能输出 0~7 位的零呀~~~

为什么负数的第八位（索引从 0 开始）补个 1 ，无关紧要？

首先搞清楚，负数在计算机中是以补码形式存储，何为补码：原码取反码 + 1

分析分析：
-16 的原码（8 位）：1001 0000

-16 的反码（8 位）：1110 1111

-16 的补码（8 位）：1111 0000

-16 的原码（32 位）：1000 0000 0000 0000 0000 0000 0001 0000

-16 的反码（32 位）：1111 1111 1111 1111 1111 1111 1110 1111

-16 的补码（32 位）：1111 1111 1111 1111 1111 1111 1111 0000

结论：8 位的负数转为 32 位负数，其 8~31 位都是 1 ，在其的第八位补个 1 ，无关紧要呀~~~

3.6.2、编写赫夫曼解码

编码思路

首先根据赫夫曼编码得到的字符数组，反解出赫夫曼编码对应的字符串 huffmanStr
因为现在要拿着赫夫曼编码值去找恢复对应的数值，所以我们需要拿到各个编码对应着哪个数值（将赫夫曼码表反转一下就行）
在 huffmanStr 中匹配编码值，逐个恢复数据，处理完毕后，便解码得到了原字节数组
注意：我这里做了调整，huffmanBytes 中最后一个字节记录了 huffmanBytes 倒数第二个字节的有效位数（从高位开始的有效位数）

// 编写一个方法，完成对压缩数据的解码
/**
 * 
 * @param huffmanCodes 赫夫曼编码表 map
 * @param huffmanBytes 赫夫曼编码得到的字节数组
 * @return 就是原来的字符串对应的数组
 */
private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
  // 1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
  StringBuilder stringBuilder = new StringBuilder();
  // 将byte数组转成二进制的字符串
  for (int i = 0; i < huffmanBytes.length - 1; i++) {
    byte b = huffmanBytes[i];
    String strToAppend = byteToBitString(b);
    // 判断是不是最后一个字节
    boolean isLastByte = (i == huffmanBytes.length - 2);
    if (isLastByte) {
      // 得到最后一个字节的有效位数
      byte validBits = huffmanBytes[huffmanBytes.length - 1];
      strToAppend = strToAppend.substring(0, validBits);
    }
    stringBuilder.append(strToAppend);
  }
  // 把字符串按照指定的赫夫曼编码进行解码
  // 把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
  Map<String, Byte> map = new HashMap<String, Byte>();
  for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
    map.put(entry.getValue(), entry.getKey());
  }
  // 创建要给集合，存放byte
  List<Byte> list = new ArrayList<>();
  // i 可以理解成就是索引,扫描 stringBuilder
  for (int i = 0; i < stringBuilder.length();) {
    int count = 1; // 小的计数器
    boolean flag = true;
    Byte b = null;
    while (flag) {
      // 1010100010111...
      // 递增的取出 key 1
      String key = stringBuilder.substring(i, i + count);// i 不动，让count移动，指定匹配到一个字符
      b = map.get(key);
      if (b == null) {// 说明没有匹配到
        count++;
      } else {
        // 匹配到
        flag = false;
      }
    }
    list.add(b);
    i += count;// i 直接移动到 count
  }
  // 当for循环结束后，我们list中就存放了所有的字符 "i like like like java do you like a java"
  // 把list 中的数据放入到byte[] 并返回
  byte b[] = new byte[list.size()];
  for (int i = 0; i < b.length; i++) {
    b[i] = list.get(i);
  }
  return b;
}

3.6.3、代码测试

代码

public static void main(String[] args) {
    String content = "i like like like java do you like a java";
    byte[] contentBytes = content.getBytes();
    System.out.println("原来的字符串=" + content);
    byte[] huffmanCodesBytes = huffmanZip(contentBytes);
    byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
    System.out.println("解码后的字符串=" + new String(sourceBytes)); // "i like like like java do you like a java"
}

程序运行结果

原来的字符串=i like like like java do you like a java
解码后的字符串=i like like like java do you like a java

3.7、文件压缩与解压

3.7.1、文件压缩

将赫夫曼编码得到的字节数组、赫夫曼编码表都要写入到文件中（使用 ObjectOutputStream 流包装 FileOutputStream 流，可直接写入对象）

// 编写方法，将一个文件进行压缩
/**
 * 
 * @param srcFile 你传入的希望压缩的文件的全路径
 * @param dstFile 我们压缩后将压缩文件放到哪个目录
 */
public static void zipFile(String srcFile, String dstFile) {
  // 创建输出流
  OutputStream os = null;
  ObjectOutputStream oos = null;
  // 创建文件的输入流
  FileInputStream is = null;
  try {
    // 创建文件的输入流
    is = new FileInputStream(srcFile);
    // 创建一个和源文件大小一样的byte[]
    byte[] b = new byte[is.available()];
    // 读取文件
    is.read(b);
    // 直接对源文件压缩
    byte[] huffmanBytes = huffmanZip(b);
    // 创建文件的输出流, 存放压缩文件
    os = new FileOutputStream(dstFile);
    // 创建一个和文件输出流关联的ObjectOutputStream
    oos = new ObjectOutputStream(os);
    // 把 赫夫曼编码后的字节数组写入压缩文件
    oos.writeObject(huffmanBytes); // 我们是把
    // 这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
    // 注意一定要把赫夫曼编码 写入压缩文件
    oos.writeObject(huffmanCodes);
  } catch (Exception e) {
    // TODO: handle exception
    System.out.println(e.getMessage());
  } finally {
    try {
      is.close();
      oos.close();
      os.close();
    } catch (Exception e) {
      // TODO: handle exception
      System.out.println(e.getMessage());
    }
  }
}

3.7.2、文件解压

先要得到编码后的字节数组和赫夫曼编码表（使用 ObjectInputStream 流封装 FileInputStream 流可直接读取对象）
再调用赫夫曼解码方法，进行解码

// 编写一个方法，完成对压缩文件的解压
/**
 * 
 * @param zipFile 准备解压的文件
 * @param dstFile 将文件解压到哪个路径
 */
public static void unZipFile(String zipFile, String dstFile) {
  // 定义文件输入流
  InputStream is = null;
  // 定义一个对象输入流
  ObjectInputStream ois = null;
  // 定义文件的输出流
  OutputStream os = null;
  try {
    // 创建文件输入流
    is = new FileInputStream(zipFile);
    // 创建一个和 is关联的对象输入流
    ois = new ObjectInputStream(is);
    // 读取byte数组 huffmanBytes
    byte[] huffmanBytes = (byte[]) ois.readObject();
    // 读取赫夫曼编码表
    Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
    // 解码
    byte[] bytes = decode(huffmanCodes, huffmanBytes);
    // 将bytes 数组写入到目标文件
    os = new FileOutputStream(dstFile);
    // 写数据到 dstFile 文件
    os.write(bytes);
  } catch (Exception e) {
    // TODO: handle exception
    System.out.println(e.getMessage());
  } finally {
    try {
      os.close();
      ois.close();
      is.close();
    } catch (Exception e2) {
      // TODO: handle exception
      System.out.println(e2.getMessage());
    }
  }
}

3.7.3、代码测试

压缩与解压缩

public class HuffmanCode {
  public static void main(String[] args) {
    // 测试压缩文件
    String srcFile = "C:\\Users\\Heygo\\Desktop\\src.png";
    String dstFile = "C:\\Users\\Heygo\\Desktop\\src.zip";
    zipFile(srcFile, dstFile);
    System.out.println("压缩文件ok~~");
    // 测试解压文件
    srcFile = "C:\\\\Users\\\\Heygo\\\\Desktop\\\\src.zip";
    dstFile = "C:\\\\Users\\\\Heygo\\\\Desktop\\\\srcCopy.png";
    unZipFile(srcFile, dstFile);
    System.out.println("解压成功!");
  }

莫得问题啊

3.8、赫夫曼编解码全部代码

public class HuffmanCode {
  public static void main(String[] args) {
    // 测试压缩文件
    String srcFile = "C:\\Users\\Heygo\\Desktop\\src.png";
    String dstFile = "C:\\Users\\Heygo\\Desktop\\src.zip";
    zipFile(srcFile, dstFile);
    System.out.println("压缩文件ok~~");
    // 测试解压文件
    srcFile = "C:\\\\Users\\\\Heygo\\\\Desktop\\\\src.zip";
    dstFile = "C:\\\\Users\\\\Heygo\\\\Desktop\\\\srcCopy.png";
    unZipFile(srcFile, dstFile);
    System.out.println("解压成功!");
  }
  /**
   * 
   * @param bytes 接收字节数组
   * @return 返回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
   */
  private static List<Node> getNodes(byte[] bytes) {
    // 1创建一个ArrayList
    ArrayList<Node> nodes = new ArrayList<Node>();
    // 遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
    Map<Byte, Integer> counts = new HashMap<>();
    for (byte b : bytes) {
      Integer count = counts.get(b);
      if (count == null) { // Map还没有这个字符数据,第一次
        counts.put(b, 1);
      } else {
        counts.put(b, count + 1);
      }
    }
    // 把每一个键值对转成一个Node 对象，并加入到nodes集合
    // 遍历map
    for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
      nodes.add(new Node(entry.getKey(), entry.getValue()));
    }
    return nodes;
  }
  // 可以通过List 创建对应的赫夫曼树
  private static Node createHuffmanTree(List<Node> nodes) {
    while (nodes.size() > 1) {
      // 排序, 从小到大
      Collections.sort(nodes);
      // 取出第一颗最小的二叉树
      Node leftNode = nodes.get(0);
      // 取出第二颗最小的二叉树
      Node rightNode = nodes.get(1);
      // 创建一颗新的二叉树,它的根节点 没有data, 只有权值
      Node parent = new Node(null, leftNode.weight + rightNode.weight);
      parent.left = leftNode;
      parent.right = rightNode;
      // 将已经处理的两颗二叉树从nodes删除
      nodes.remove(leftNode);
      nodes.remove(rightNode);
      // 将新的二叉树，加入到nodes
      nodes.add(parent);
    }
    // nodes 最后的结点，就是赫夫曼树的根结点
    return nodes.get(0);
  }
  // 生成赫夫曼树对应的赫夫曼编码
  // 思路:将赫夫曼编码表存放在 Map<Byte,String> 形式
  // 生成的赫夫曼编码表{32=01, 97=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>();
  // 为了调用方便，我们重载 getCodes
  private static Map<Byte, String> getCodes(Node root) {
    if (root == null) {
      return null;
    }
    // 处理root的左子树
    getCodes(root.left, "0", new StringBuilder());
    // 处理root的右子树
    getCodes(root.right, "1", new StringBuilder());
    return huffmanCodes;
  }
  /**
   * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合
   * @param node  传入结点
   * @param code  路径： 左子结点是 0, 右子结点 1
   * @param stringBuilder 用于拼接路径
   */
  private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    StringBuilder curNodeCode = new StringBuilder(stringBuilder);
    // 将code 加入到 curNodeCode
    curNodeCode.append(code);
    if (node != null) { // 如果node == null不处理
      // 判断当前node 是叶子结点还是非叶子结点
      if (node.data == null) { // 非叶子结点
        // 递归处理
        // 向左递归
        getCodes(node.left, "0", curNodeCode);
        // 向右递归
        getCodes(node.right, "1", curNodeCode);
      } else { // 说明是一个叶子结点
        // 就表示找到某个叶子结点的最后
        huffmanCodes.put(node.data, curNodeCode.toString());
      }
    }
  }
  //编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
  /**
   * 
   * @param bytes 这是原始的字符串对应的 byte[]
   * @param huffmanCodes 生成的赫夫曼编码map
   * @return 返回赫夫曼编码处理后的 byte[] 
   * 
   */
  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));
    }
    // 统计返回 byte[] huffmanCodeBytes 长度
    // 一句话 int len = (stringBuilder.length() + 7) / 8;
    int len;
    byte countToEight = (byte) (stringBuilder.length() % 8);
    if (countToEight == 0) {
      len = stringBuilder.length() / 8;
    } else {
      len = stringBuilder.length() / 8 + 1;
      // 后面补零
      for (int i = countToEight; i < 8; i++) {
        stringBuilder.append('0');
      }
    }
    // 创建 存储压缩后的 byte数组，huffmanCodeBytes[len]记录赫夫曼编码最后一个字节的有效位数
    byte[] huffmanCodeBytes = new byte[len + 1];
    huffmanCodeBytes[len] = countToEight;
    int index = 0;// 记录是第几个byte
    for (int i = 0; i < stringBuilder.length(); i += 8) { // 因为是每8位对应一个byte,所以步长 +8
      String strByte;
      strByte = stringBuilder.substring(i, i + 8);
      // 将strByte 转成一个byte,放入到 huffmanCodeBytes
      huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
      index++;
    }
    return huffmanCodeBytes;
  }
  // 使用一个方法，将前面的方法封装起来，便于我们的调用.
  /**
   * 
   * @param bytes 原始的字符串对应的字节数组
   * @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
   */
  private static byte[] huffmanZip(byte[] bytes) {
    List<Node> nodes = getNodes(bytes);
    // 根据 nodes 创建的赫夫曼树
    Node huffmanTreeRoot = createHuffmanTree(nodes);
    // 对应的赫夫曼编码(根据 赫夫曼树)
    Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    // 根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
    byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
    return huffmanCodeBytes;
  }
  // 将 byte 转换为对应的字符串
  private static String byteToBitString(byte b) {
    // 使用变量保存 b
    int temp = b; // 将 b 转成 int   
    temp |= 0x100; // 如果是正数我们需要将高位补零
    // 转换为二进制字符串，正数：高位补 0 即可，然后截取低八位即可；负数直接截取低八位即可
    // 负数在计算机内存储的是补码，补码转原码：先 -1 ，再取反
    String binaryStr = Integer.toBinaryString(temp);
    return binaryStr.substring(binaryStr.length() - 8);
  }
  // 编写一个方法，完成对压缩数据的解码
  /**
   * 
   * @param huffmanCodes 赫夫曼编码表 map
   * @param huffmanBytes 赫夫曼编码得到的字节数组
   * @return 就是原来的字符串对应的数组
   */
  private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
    // 1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
    StringBuilder stringBuilder = new StringBuilder();
    // 将byte数组转成二进制的字符串
    for (int i = 0; i < huffmanBytes.length - 1; i++) {
      byte b = huffmanBytes[i];
      String strToAppend = byteToBitString(b);
      // 判断是不是最后一个字节
      boolean isLastByte = (i == huffmanBytes.length - 2);
      if (isLastByte) {
        // 得到最后一个字节的有效位数
        byte validBits = huffmanBytes[huffmanBytes.length - 1];
        strToAppend = strToAppend.substring(0, validBits);
      }
      stringBuilder.append(strToAppend);
    }
    // 把字符串按照指定的赫夫曼编码进行解码
    // 把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
    Map<String, Byte> map = new HashMap<String, Byte>();
    for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
      map.put(entry.getValue(), entry.getKey());
    }
    // 创建要给集合，存放byte
    List<Byte> list = new ArrayList<>();
    // i 可以理解成就是索引,扫描 stringBuilder
    for (int i = 0; i < stringBuilder.length();) {
      int count = 1; // 小的计数器
      boolean flag = true;
      Byte b = null;
      while (flag) {
        // 1010100010111...
        // 递增的取出 key 1
        String key = stringBuilder.substring(i, i + count);// i 不动，让count移动，指定匹配到一个字符
        b = map.get(key);
        if (b == null) {// 说明没有匹配到
          count++;
        } else {
          // 匹配到
          flag = false;
        }
      }
      list.add(b);
      i += count;// i 直接移动到 count
    }
    // 当for循环结束后，我们list中就存放了所有的字符 "i like like like java do you like a java"
    // 把list 中的数据放入到byte[] 并返回
    byte b[] = new byte[list.size()];
    for (int i = 0; i < b.length; i++) {
      b[i] = list.get(i);
    }
    return b;
  }
  // 编写方法，将一个文件进行压缩
  /**
   * 
   * @param srcFile 你传入的希望压缩的文件的全路径
   * @param dstFile 我们压缩后将压缩文件放到哪个目录
   */
  public static void zipFile(String srcFile, String dstFile) {
    // 创建输出流
    OutputStream os = null;
    ObjectOutputStream oos = null;
    // 创建文件的输入流
    FileInputStream is = null;
    try {
      // 创建文件的输入流
      is = new FileInputStream(srcFile);
      // 创建一个和源文件大小一样的byte[]
      byte[] b = new byte[is.available()];
      // 读取文件
      is.read(b);
      // 直接对源文件压缩
      byte[] huffmanBytes = huffmanZip(b);
      // 创建文件的输出流, 存放压缩文件
      os = new FileOutputStream(dstFile);
      // 创建一个和文件输出流关联的ObjectOutputStream
      oos = new ObjectOutputStream(os);
      // 把 赫夫曼编码后的字节数组写入压缩文件
      oos.writeObject(huffmanBytes); // 我们是把
      // 这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
      // 注意一定要把赫夫曼编码 写入压缩文件
      oos.writeObject(huffmanCodes);
    } catch (Exception e) {
      // TODO: handle exception
      System.out.println(e.getMessage());
    } finally {
      try {
        is.close();
        oos.close();
        os.close();
      } catch (Exception e) {
        // TODO: handle exception
        System.out.println(e.getMessage());
      }
    }
  }
  // 编写一个方法，完成对压缩文件的解压
  /**
   * 
   * @param zipFile 准备解压的文件
   * @param dstFile 将文件解压到哪个路径
   */
  public static void unZipFile(String zipFile, String dstFile) {
    // 定义文件输入流
    InputStream is = null;
    // 定义一个对象输入流
    ObjectInputStream ois = null;
    // 定义文件的输出流
    OutputStream os = null;
    try {
      // 创建文件输入流
      is = new FileInputStream(zipFile);
      // 创建一个和 is关联的对象输入流
      ois = new ObjectInputStream(is);
      // 读取byte数组 huffmanBytes
      byte[] huffmanBytes = (byte[]) ois.readObject();
      // 读取赫夫曼编码表
      Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
      // 解码
      byte[] bytes = decode(huffmanCodes, huffmanBytes);
      // 将bytes 数组写入到目标文件
      os = new FileOutputStream(dstFile);
      // 写数据到 dstFile 文件
      os.write(bytes);
    } catch (Exception e) {
      // TODO: handle exception
      System.out.println(e.getMessage());
    } finally {
      try {
        os.close();
        ois.close();
        is.close();
      } catch (Exception e2) {
        // TODO: handle exception
        System.out.println(e2.getMessage());
      }
    }
  }
}
//创建Node ,待数据和权值
class Node implements Comparable<Node> {
  Byte data; // 存放数据(字符)本身，比如'a' => 97 ' ' => 32
  int weight; // 权值, 表示字符出现的次数
  Node left;//
  Node right;
  public Node(Byte data, int weight) {
    this.data = data;
    this.weight = weight;
  }
  @Override
  public int compareTo(Node o) {
    // 从小到大排序
    return this.weight - o.weight;
  }
  public String toString() {
    return "Node [data = " + data + " weight=" + weight + "]";
  }
  // 前序遍历
  public void preOrder() {
    System.out.println(this);
    if (this.left != null) {
      this.left.preOrder();
    }
    if (this.right != null) {
      this.right.preOrder();
    }
  }
}

3.9、赫夫曼编解码总结

如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化，比如视频，ppt 等等文件
赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件)
如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显

4、二叉排序树

4.1、二叉排序树需求

4.1.1、需求分析

给你一个数列 { 7, 3, 10, 12, 5, 1, 9 } ，要求能够高效的完成对数据的查询和添加。

4.1.2、解决方案

使用数组

数组未排序，优点：直接在数组尾添加，速度快。缺点：查找速度慢
数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。

使用链式存储-链表：不管链表是否有序，查找速度都慢，但添加数据速度比数组快，不需要数据整体移动。
使用二叉排序树

4.2、二叉排序树介绍

二叉排序树：BST(Binary Sort(Search) Tree) ，对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点
二叉树的中序遍历为有序数列
比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

第 11 章：树结构实际应用（一）

第 11 章 树结构实际应用