算法基础14：树结构的实际应用

堆排序

堆排序基本介绍

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

5. 小顶堆举例说明

   

6. 一般升序采用大顶堆，降序采用小顶堆

堆排序的基本思想

1. 将待排序序列构造成一个大顶堆
2. 此时，整个序列的最大值就是堆顶的根节点。
3. 将其与末尾元素进行交换，此时末尾就为最大值。
4. 然后将剩余n-1个元素重新构造成一个堆，这样会得到个元素的次小值。如此反复执行，便能得到一个有序序列了。

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

要求：给你一个数组{4,6,8,5,9}，要求使用堆排序法，将数组升序排序。

代码案例

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author：XMD
 * @date: 15.9.22
 */
public class HeapSort {
    public static void main(String[] args) {
        //要求将数组进行升序排序
        int[] arr = {4, 6, 8, 5, 9,-1,3,7,0,2};
        heapSort(arr);
    }

    public static void heapSort(int[] arr) {
        System.out.println("堆排序");


        //完成我们最终代码
        //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
        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--) {
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println("数组：" + Arrays.toString(arr));

    }

    /**
     * 将一个数组（二叉树），调整成一个大顶堆
     * 举例int arr[]={4,6,8,5,9};=>i=1=>adjustHeap=>得到{4,9,8,5,6}
     * 如果我们再次调用adjustHeap传入的是1=0=>得到{4,9,8,5,6}=>{9,6,8,5,4)
     *
     * @param arr    待整顿的数组
     * @param i      表示叶子结点再办数组中的索引
     * @param lenght 表示对多少个元素继续调整，length是在逐滋的减少
     */
    public static void adjustHeap(int[] arr, int i, int lenght) {
        //先取出当前元素的值，保存在临时变量
        int temp = arr[i];
        //开始调整
        //说明
        //1,k=1*2+1k是i结点的左子结点
        for (int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
            //说明左子结点的值小于右子结点的值
            if (k+1 < lenght && arr[k] < arr[k + 1]) {
                k++;
            }
            //如果子节点大于父节点
            if (arr[k] > temp) {
                //把较大的值赋给当前结点
                arr[i] = arr[k];
                //!!  i指向k,继续循环比较
                i = k;
            } else {
                break;
            }
        }
        //当fo下循环结束后，我们已经将以i为父结点的树的最大值，放在了最顶（局部）
        //将temp值放到调整后的位置
        arr[i] = temp;
    }
}

有点难度

哈夫曼/赫夫曼（ huffman）树

基本介绍

代码实现

/**
 * 哈夫曼树
 *
 * @author：XMD
 * @date: 22.9.22
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node = createHuffmanTree(arr);
        preOrder(node);
    }

    public static  void preOrder(Node root){
        if (root != null){
            root.preOrder();
        }

    }


    //创建哈夫曼树
    public static Node createHuffmanTree(int[] arr) {
        //第一步为了操作方便
        //1.遍历arr数组
        //2,将arr的每个元素构成成一个Node
        //3,将Node放入到ArrayList中
        List<Node> nodes = new ArrayList<>();
        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.reght = rightnode;

            //(4)从ArrayList删除处理过的二叉树
            nodes.remove(leftnode);
            nodes.remove(rightnode);
            //(5)将parent加入到nodes
            nodes.add(parent);

            Collections.sort(nodes);
            System.out.println(nodes);
        }

        return nodes.get(0);

    }

}

//创建节点类
//为了让Node对象持续排序Collections集合排序
//让Node实现Comparable接口
class Node implements Comparable<Node> {
    int value;
    Node left;
    Node reght;

    //写一个前序遍历
    public void preOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }
        if (this.reght != null){
            this.reght.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;
    }
}

哈夫曼/赫夫曼（ huffman）编码

基本介绍

原理剖析

思路

数据压缩

import java.util.*;

/**
 * 哈夫曼编码
 *
 * @author：XMD
 * @date: 8.10.22
 */
public class HuffmanCodeDemo {
    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes();


//        System.out.println(bytes.length);
//        List<Node2> nodes = getNodes(bytes);
//        System.out.println(nodes);
//
//        System.out.println("哈夫曼数");
//        Node2 hUffmanTree = createHUffmanTree(nodes);
//        System.out.println(hUffmanTree);
//        System.out.println("前序遍历");
//        perOrder(hUffmanTree);
//
//
//        Map<Byte, String> huffmanCodes = getCodes(hUffmanTree);
//        System.out.println("生产的哈夫曼的编码表：" + huffmanCodes);
//
//
//        byte[] zip = zip(bytes, huffmanCodes);
//        System.out.println("huffmanCodeByte=" + Arrays.toString(zip)); //17个字节

        //数据压缩
        byte[] zip = huffmanZip(bytes);
        System.out.println("压缩后的："  + Arrays.toString(zip));
        
    }

    //使用一个方法，将前面的方法封装起来，便于我们的调用。

    /**
     * 使用一个方法，将前面的方法封装起来，便于我们的调用。
     *
     * @param bytes 原始的字符串对应的字节数组
     * @return
     */
    private static byte[] huffmanZip(byte[] bytes) {
        List<Node2> nodes = getNodes(bytes);
        Node2 hUffmanTree = createHUffmanTree(nodes);
        Map<Byte, String> codes = getCodes(hUffmanTree);
        return zip(bytes, codes);
    }


    private static void perOrder(Node2 root) {
        if (root != null) {
            root.preOrder();
        }
    }

    //编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1,利用huffmanCodes将bytes转成赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte aByte : bytes) {
            stringBuilder.append(huffmanCodes.get(aByte));
        }
        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;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            if (i + 8 > stringBuilder.length()) {
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }

            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }


    //1,将赫夫曼编码表存放在Map<Byte,String>形式
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //2,在生成赫夫曼编码表示，需要去拼接路径，定义一个StringBuilder存储某个叶子结点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    //为了调用方便，我们重载getCodes
    private static Map<Byte, String> getCodes(Node2 root) {
        if (root == null) {
            return null;
        }
        getCodes(root.left, "0", stringBuilder);
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 得到将传入的node节点的所有的叶子结点的夫曼编码，并且放入到huffmanCodes中
     *
     * @param node          传入的节点
     * @param code          左子节点：0，右子节点：1
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node2 node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node != null) {
            if (node.data == null) {
                //判断当前node是叶子结点还是非叶子结点
                //递归处理
                //向左递归
                getCodes(node.left, "0", stringBuilder1);
                //向右递归
                getCodes(node.right, "1", stringBuilder1);
            } else {
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }


    }


    private static List<Node2> getNodes(byte[] bytes) {
        ArrayList<Node2> node2s = new ArrayList<>();

        Map<Byte, Integer> count = new HashMap<>();
        for (byte aByte : bytes) {
            Integer integer = count.get(aByte);
            if (integer == null) {
                count.put(aByte, 1);
            } else {
                count.put(aByte, integer + 1);
            }
        }
        for (Map.Entry<Byte, Integer> entry : count.entrySet()) {
            node2s.add(new Node2(entry.getKey(), entry.getValue()));
        }
        return node2s;
    }

    private static Node2 createHUffmanTree(List<Node2> node2s) {
        while (node2s.size() > 1) {
            //排序，从小到大
            Collections.sort(node2s);
            //取出第一个最小的二叉树
            Node2 leftNode = node2s.get(0);
            //取出第一个最小的二叉树
            Node2 rightNode = node2s.get(1);
            //创建一颗新的二叉树，它的根节点没有datā，只有权值
            Node2 parent = new Node2(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //将已经处理的两颗二叉树从nodes删除
            node2s.remove(leftNode);
            node2s.remove(rightNode);
            node2s.add(parent);
        }
        return node2s.get(0);

    }

}

//创建Node，带数据和权值
class Node2 implements Comparable<Node2> {
    //存放数据
    Byte data;
    //权值，表示字符出现的次数
    int weight;
    Node2 left;
    Node2 right;

    public Node2(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node2 o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node2{" +
                "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();
        }
    }
}

数据解码

import java.util.*;

/**
 * 哈夫曼编码
 *
 * @author：XMD
 * @date: 8.10.22
 */
public class HuffmanCodeDemo {
    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes();


//        System.out.println(bytes.length);
//        List<Node2> nodes = getNodes(bytes);
//        System.out.println(nodes);
//
//        System.out.println("哈夫曼数");
//        Node2 hUffmanTree = createHUffmanTree(nodes);
//        System.out.println(hUffmanTree);
//        System.out.println("前序遍历");
//        perOrder(hUffmanTree);
//
//
//        Map<Byte, String> huffmanCodes = getCodes(hUffmanTree);
//        System.out.println("生产的哈夫曼的编码表：" + huffmanCodes);
//
//
//        byte[] zip = zip(bytes, huffmanCodes);
//        System.out.println("huffmanCodeByte=" + Arrays.toString(zip)); //17个字节

        //数据压缩
        byte[] zip = huffmanZip(bytes);
        System.out.println("压缩后的：" + Arrays.toString(zip));

        //解码
        byte[] decode = decode(huffmanCodes, zip);
        System.out.println("原来字符串=" + new String(decode));
    }


    /**
     * 将一个byte转成一个二进制的字符串
     *
     * @param b    传入的byte
     * @param flag 标志是否需要补高位如果是true,表示需要补高位，如果是false表示不补，如课是最后一个字节，无需补高位
     * @return 是该b对应的二进制的字符串，（注意是按补码返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        int temp = b;
        ////如果是正数我们还存在补高位
        if (flag) {
            temp |= 256;
        }
        String string = Integer.toBinaryString(temp);
        if (flag) {
            //返回的是temp对应的二进制的补码
            return string.substring(string.length() - 8);
        } else {
            return string;
        }
    }

    //编写一个方法，完成对压缩数据的解码

    /**
     * @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; i++) {
            byte b = huffmanBytes[i];
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            String string = byteToBitString(!flag, b);
            stringBuilder.append(string);
        }
        //把字符串安装指定的赫夫曼编码进行解码
        //把赫夫曼编码表进行调换，因为反向查询a->100100->a
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        List<Byte> list = new ArrayList<>();
        for (int s = 0; s < stringBuilder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;

            while (flag) {
                //s不动，让count移动，指定匹配到一个字符
                String key = stringBuilder.substring(s, s + count);
                b = map.get(key);
                //没有匹配到
                if (b == null) {
                    count++;
                } else {
                    //匹配到了
                    flag = false;
                }
            }
            list.add(b);
            s += count;
        }
        //当for循环结束后，我们list中就存放了所有的字符串
        //把list中的数据存入到byte[] 中，并返回
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }


    //使用一个方法，将前面的方法封装起来，便于我们的调用。

    /**
     * 使用一个方法，将前面的方法封装起来，便于我们的调用。
     *
     * @param bytes 原始的字符串对应的字节数组
     * @return
     */
    private static byte[] huffmanZip(byte[] bytes) {
        List<Node2> nodes = getNodes(bytes);
        Node2 hUffmanTree = createHUffmanTree(nodes);
        Map<Byte, String> codes = getCodes(hUffmanTree);
        return zip(bytes, codes);
    }


    private static void perOrder(Node2 root) {
        if (root != null) {
            root.preOrder();
        }
    }

    //编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1,利用huffmanCodes将bytes转成赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte aByte : bytes) {
            stringBuilder.append(huffmanCodes.get(aByte));
        }

        System.out.println("zip code=" + stringBuilder);
        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;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            if (i + 8 > stringBuilder.length()) {
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }

            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }


    //1,将赫夫曼编码表存放在Map<Byte,String>形式
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //2,在生成赫夫曼编码表示，需要去拼接路径，定义一个StringBuilder存储某个叶子结点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    //为了调用方便，我们重载getCodes
    private static Map<Byte, String> getCodes(Node2 root) {
        if (root == null) {
            return null;
        }
        getCodes(root.left, "0", stringBuilder);
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 得到将传入的node节点的所有的叶子结点的夫曼编码，并且放入到huffmanCodes中
     *
     * @param node          传入的节点
     * @param code          左子节点：0，右子节点：1
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node2 node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node != null) {
            if (node.data == null) {
                //判断当前node是叶子结点还是非叶子结点
                //递归处理
                //向左递归
                getCodes(node.left, "0", stringBuilder1);
                //向右递归
                getCodes(node.right, "1", stringBuilder1);
            } else {
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }


    }


    private static List<Node2> getNodes(byte[] bytes) {
        ArrayList<Node2> node2s = new ArrayList<>();

        Map<Byte, Integer> count = new HashMap<>();
        for (byte aByte : bytes) {
            Integer integer = count.get(aByte);
            if (integer == null) {
                count.put(aByte, 1);
            } else {
                count.put(aByte, integer + 1);
            }
        }
        for (Map.Entry<Byte, Integer> entry : count.entrySet()) {
            node2s.add(new Node2(entry.getKey(), entry.getValue()));
        }
        return node2s;
    }

    private static Node2 createHUffmanTree(List<Node2> node2s) {
        while (node2s.size() > 1) {
            //排序，从小到大
            Collections.sort(node2s);
            //取出第一个最小的二叉树
            Node2 leftNode = node2s.get(0);
            //取出第一个最小的二叉树
            Node2 rightNode = node2s.get(1);
            //创建一颗新的二叉树，它的根节点没有datā，只有权值
            Node2 parent = new Node2(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //将已经处理的两颗二叉树从nodes删除
            node2s.remove(leftNode);
            node2s.remove(rightNode);
            node2s.add(parent);
        }
        return node2s.get(0);

    }

}

//创建Node，带数据和权值
class Node2 implements Comparable<Node2> {
    //存放数据
    Byte data;
    //权值，表示字符出现的次数
    int weight;
    Node2 left;
    Node2 right;

    public Node2(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node2 o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node2{" +
                "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();
        }
    }
}

文件压缩/解压

import java.io.*;
import java.util.*;

/**
 * 哈夫曼编码
 *
 * @author：XMD
 * @date: 8.10.22
 */
public class HuffmanCodeDemo {
    public static void main(String[] args) {
//        String str = "i like like like java do you like a java";
//        byte[] bytes = str.getBytes();


//        System.out.println(bytes.length);
//        List<Node2> nodes = getNodes(bytes);
//        System.out.println(nodes);
//
//        System.out.println("哈夫曼数");
//        Node2 hUffmanTree = createHUffmanTree(nodes);
//        System.out.println(hUffmanTree);
//        System.out.println("前序遍历");
//        perOrder(hUffmanTree);
//
//
//        Map<Byte, String> huffmanCodes = getCodes(hUffmanTree);
//        System.out.println("生产的哈夫曼的编码表：" + huffmanCodes);
//
//
//        byte[] zip = zip(bytes, huffmanCodes);
//        System.out.println("huffmanCodeByte=" + Arrays.toString(zip)); //17个字节

        //数据压缩
//        byte[] zip = huffmanZip(bytes);
//        System.out.println("压缩后的：" + Arrays.toString(zip));
//
//        //解码
//        byte[] decode = decode(huffmanCodes, zip);
//        System.out.println("原来字符串=" + new String(decode));


        //测试压缩文件
        String srcFile = "/Users/yons/Downloads/HuffmanCodeDemo.java";
        String dstFile = "/Users/yons/Downloads/临时/HuffmanCodeDemo.zip";
        String dstFile2 = "/Users/yons/Downloads/临时/HuffmanCodeDemo2.java";
        zipFile(srcFile, dstFile);

        //文件解压
        unZipFile(dstFile, dstFile2);
    }

    /**
     * 解压文件
     *
     * @param zipFile
     * @param dstFile
     */
    private static void unZipFile(String zipFile, String dstFile) {
        try (
                FileInputStream is = new FileInputStream(zipFile);
                ObjectInputStream ois = new ObjectInputStream(is)
        ) {
            byte[] huffmanBytes = (byte[]) ois.readObject();
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();

            byte[] decode = decode(huffmanCodes, huffmanBytes);
            FileOutputStream os = new FileOutputStream(dstFile);
            os.write(decode);
        } catch (Exception e) {
            e.printStackTrace();
        }

    }


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


    /**
     * 将一个byte转成一个二进制的字符串
     *
     * @param b    传入的byte
     * @param flag 标志是否需要补高位如果是true,表示需要补高位，如果是false表示不补，如课是最后一个字节，无需补高位
     * @return 是该b对应的二进制的字符串，（注意是按补码返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        int temp = b;
        ////如果是正数我们还存在补高位
        if (flag) {
            temp |= 256;
        }
        String string = Integer.toBinaryString(temp);
        if (flag) {
            //返回的是temp对应的二进制的补码
            return string.substring(string.length() - 8);
        } else {
            return string;
        }
    }

    //编写一个方法，完成对压缩数据的解码

    /**
     * @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; i++) {
            byte b = huffmanBytes[i];
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            String string = byteToBitString(!flag, b);
            stringBuilder.append(string);
        }
        //把字符串安装指定的赫夫曼编码进行解码
        //把赫夫曼编码表进行调换，因为反向查询a->100100->a
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        List<Byte> list = new ArrayList<>();
        for (int s = 0; s < stringBuilder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;

            while (flag) {
                //s不动，让count移动，指定匹配到一个字符
                String key = stringBuilder.substring(s, s + count);
                b = map.get(key);
                //没有匹配到
                if (b == null) {
                    count++;
                } else {
                    //匹配到了
                    flag = false;
                }
            }
            list.add(b);
            s += count;
        }
        //当for循环结束后，我们list中就存放了所有的字符串
        //把list中的数据存入到byte[] 中，并返回
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }


    //使用一个方法，将前面的方法封装起来，便于我们的调用。

    /**
     * 使用一个方法，将前面的方法封装起来，便于我们的调用。
     *
     * @param bytes 原始的字符串对应的字节数组
     * @return
     */
    private static byte[] huffmanZip(byte[] bytes) {
        List<Node2> nodes = getNodes(bytes);
        Node2 hUffmanTree = createHUffmanTree(nodes);
        Map<Byte, String> codes = getCodes(hUffmanTree);
        return zip(bytes, codes);
    }


    private static void perOrder(Node2 root) {
        if (root != null) {
            root.preOrder();
        }
    }

    //编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1,利用huffmanCodes将bytes转成赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte aByte : bytes) {
            stringBuilder.append(huffmanCodes.get(aByte));
        }

//        System.out.println("zip code=" + stringBuilder);
        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;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            if (i + 8 > stringBuilder.length()) {
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }

            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }


    //1,将赫夫曼编码表存放在Map<Byte,String>形式
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //2,在生成赫夫曼编码表示，需要去拼接路径，定义一个StringBuilder存储某个叶子结点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    //为了调用方便，我们重载getCodes
    private static Map<Byte, String> getCodes(Node2 root) {
        if (root == null) {
            return null;
        }
        getCodes(root.left, "0", stringBuilder);
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 得到将传入的node节点的所有的叶子结点的夫曼编码，并且放入到huffmanCodes中
     *
     * @param node          传入的节点
     * @param code          左子节点：0，右子节点：1
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node2 node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node != null) {
            if (node.data == null) {
                //判断当前node是叶子结点还是非叶子结点
                //递归处理
                //向左递归
                getCodes(node.left, "0", stringBuilder1);
                //向右递归
                getCodes(node.right, "1", stringBuilder1);
            } else {
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }


    }


    private static List<Node2> getNodes(byte[] bytes) {
        ArrayList<Node2> node2s = new ArrayList<>();

        Map<Byte, Integer> count = new HashMap<>();
        for (byte aByte : bytes) {
            Integer integer = count.get(aByte);
            if (integer == null) {
                count.put(aByte, 1);
            } else {
                count.put(aByte, integer + 1);
            }
        }
        for (Map.Entry<Byte, Integer> entry : count.entrySet()) {
            node2s.add(new Node2(entry.getKey(), entry.getValue()));
        }
        return node2s;
    }

    private static Node2 createHUffmanTree(List<Node2> node2s) {
        while (node2s.size() > 1) {
            //排序，从小到大
            Collections.sort(node2s);
            //取出第一个最小的二叉树
            Node2 leftNode = node2s.get(0);
            //取出第一个最小的二叉树
            Node2 rightNode = node2s.get(1);
            //创建一颗新的二叉树，它的根节点没有datā，只有权值
            Node2 parent = new Node2(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //将已经处理的两颗二叉树从nodes删除
            node2s.remove(leftNode);
            node2s.remove(rightNode);
            node2s.add(parent);
        }
        return node2s.get(0);

    }

}

//创建Node，带数据和权值
class Node2 implements Comparable<Node2> {
    //存放数据
    Byte data;
    //权值，表示字符出现的次数
    int weight;
    Node2 left;
    Node2 right;

    public Node2(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node2 o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node2{" +
                "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();
        }
    }
}

二叉排序树

介绍

二叉排序树的创建和遍历

/**
 * 二叉排序树
 *
 * @author：XMD
 * @date: 9.10.22
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        BinarySortTree binarySortTree = new BinarySortTree();
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        for (int i : arr) {
            binarySortTree.add(new Node(i));
        }

        //中序遍历
        binarySortTree.infixOrder();
    }


}

class BinarySortTree {
    private Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("空的");
        }
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //递归的形式添加结点，注意需要满足二叉排序树的要求
    public void add(Node node) {
        if (node == null) {
            return;
        }

        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else if (node.value > this.value) {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }


    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }

    }
}

二叉排序数树的删除

/**
 * 二叉排序树
 *
 * @author：XMD
 * @date: 9.10.22
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        BinarySortTree binarySortTree = new BinarySortTree();
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        for (int i : arr) {
            binarySortTree.add(new Node(i));
        }

        //中序遍历
        binarySortTree.infixOrder();

        //测试删除叶子结点
        binarySortTree.delNode(10);

        System.out.println("删除后的遍历-------");
        //中序遍历
        binarySortTree.infixOrder();
    }


}

class BinarySortTree {
    private Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("空的");
        }
    }


    //查找要删除的结点
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.seachParent(value);
        }
    }

    /**
     * @param node 传入的结点（当做二叉排序树的根结点）
     * @return 返回的以node为根结点的二叉排序树的最小结点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        while (target.left != null) {
            target = target.left;
        }
        //删除最小的节点
        delNode(target.value);
        return target.value;

    }

    //删除结点

    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //1,需求先去找到要则除的结点targetNode
            Node targetNode = search(value);
            //如果没有找到要删除的结点
            if (targetNode == null) {
                return;
            }
            //如果我们发现当前这颗二叉排序树只有一个结点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //去找到targetNode的父结点
            Node parent = searchParent(value);
            if (targetNode.left == null && targetNode.right == null) {
                //判断targetNode是父结点的左子结点，还是右子结点
                if (parent.left != null && parent.left.value == value) {
                    //是左子结点
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {
                    //是右子结点
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) {
                //删除有两颗子树的节点
                int treeMin = delRightTreeMin(targetNode.right);
                targetNode.value = treeMin;

            } else {
                //删除只有一个子节点的节点
                //如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    if (parent != null) {
                        //如果targetNode是parent的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            //targetNode是parent的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {
                    //如果要删除的结点有左子结点
                    if (parent != null) {
                        //如果targetNode是parent的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            //如果targetNode是parent的右子结点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }

    }


}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //删除结点

    /**
     * @param value 希望删除的结点的值
     * @return 如果找到返回该结点，否则返回null
     */
    public Node search(int value) {
        if (value == this.value) {
            return this;
        } else if (value < this.value) {
            //如果查找的值小于当前结点，向左子树递归查找
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }


    /**
     * 查找要删除的节点的父节点
     *
     * @param value 要找到的结点的值
     * @return 返回的是要删除的结点的父结点，如果没有就返回null
     */
    public Node seachParent(int value) {
        //如果当前结点就是要刷除的结点的父结点，就返回
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value)) {
            return this;
        } else {
            //如果查找的值小于当前结点的值，并且当前结点的左子结点不为空
            if (value < this.value && this.left != null) {
                return this.left.seachParent(value);
            } else if (value >= this.value && this.right != null) {
                return this.right.seachParent(value);
            } else {
                return null;
            }
        }

    }


    //递归的形式添加结点，注意需要满足二叉排序树的要求
    public void add(Node node) {
        if (node == null) {
            return;
        }

        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else if (node.value > this.value) {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }


    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }

    }
}

平衡二叉树

代码：

/**
 * 平衡二叉树
 *
 * @author：XMD
 * @date: 10.10.22
 */
public class AvlTreeDemo {
    public static void main(String[] args) {
//        int[] arr = {4, 3, 6, 5, 7, 8};
//        int[] arr = {10, 12, 8, 9, 7, 6};
        int[] arr = {10, 12, 8, 9, 7, 6};
        AVLTree avlTree = new AVLTree();
        for (int i : arr) {
            avlTree.add(new Node(i));
        }
        System.out.println("中序遍历");
        avlTree.infixOrder();

        System.out.println("在平衡之后----");
        System.out.println("树的高度=" + avlTree.getRoot().height());
        System.out.println("左子树的高度=" + avlTree.getRoot().leftHeight());
        System.out.println("右子树的高度=" + avlTree.getRoot().rightHeight());
        System.out.println("当前的根节点=" + avlTree.getRoot());
        System.out.println("当前的根左节点=" + avlTree.getRoot().left);
        System.out.println("当前的根右节点=" + avlTree.getRoot().right);
    }

}


class AVLTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("空的");
        }
    }


    //查找要删除的结点
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.seachParent(value);
        }
    }

    /**
     * @param node 传入的结点（当做二叉排序树的根结点）
     * @return 返回的以node为根结点的二叉排序树的最小结点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        while (target.left != null) {
            target = target.left;
        }
        //删除最小的节点
        delNode(target.value);
        return target.value;

    }

    //删除结点

    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //1,需求先去找到要则除的结点targetNode
            Node targetNode = search(value);
            //如果没有找到要删除的结点
            if (targetNode == null) {
                return;
            }
            //如果我们发现当前这颗二叉排序树只有一个结点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //去找到targetNode的父结点
            Node parent = searchParent(value);
            if (targetNode.left == null && targetNode.right == null) {
                //判断targetNode是父结点的左子结点，还是右子结点
                if (parent.left != null && parent.left.value == value) {
                    //是左子结点
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {
                    //是右子结点
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) {
                //删除有两颗子树的节点
                int treeMin = delRightTreeMin(targetNode.right);
                targetNode.value = treeMin;

            } else {
                //删除只有一个子节点的节点
                //如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    if (parent != null) {
                        //如果targetNode是parent的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            //targetNode是parent的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {
                    //如果要删除的结点有左子结点
                    if (parent != null) {
                        //如果targetNode是parent的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            //如果targetNode是parent的右子结点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }

    }
}


class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //返回左子树的高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    //返回右子树的高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }

    //返回当前节点的高度，以该节点为根节点的树的高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }


    //删除结点

    /**
     * @param value 希望删除的结点的值
     * @return 如果找到返回该结点，否则返回null
     */
    public Node search(int value) {
        if (value == this.value) {
            return this;
        } else if (value < this.value) {
            //如果查找的值小于当前结点，向左子树递归查找
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }


    /**
     * 查找要删除的节点的父节点
     *
     * @param value 要找到的结点的值
     * @return 返回的是要删除的结点的父结点，如果没有就返回null
     */
    public Node seachParent(int value) {
        //如果当前结点就是要刷除的结点的父结点，就返回
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value)) {
            return this;
        } else {
            //如果查找的值小于当前结点的值，并且当前结点的左子结点不为空
            if (value < this.value && this.left != null) {
                return this.left.seachParent(value);
            } else if (value >= this.value && this.right != null) {
                return this.right.seachParent(value);
            } else {
                return null;
            }
        }

    }


    //递归的形式添加结点，注意需要满足二叉排序树的要求
    public void add(Node node) {
        if (node == null) {
            return;
        }

        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else if (node.value > this.value) {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }


        //当添加完节点后，如果：右子树的高度-左子树的高度 > 1,需要左旋转
        if (rightHeight() - leftHeight() > 1) {
            //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
            if (right != null && right.leftHeight() > right.rightHeight()){
                right.rightRotate();
                leftRotate();
            }else {
                //左旋转
                leftRotate();
            }
            //必须要！！！
            return;
        }

//        //当添加完一个结点后，如果（左子树的高度~右子树的高度）>1，右旋转
        if (leftHeight() - rightHeight() > 1){
            if (left != null && left.rightHeight() > left.leftHeight()){
                //先对当前结点的左结点（左子树）->左旋转
                left.leftRotate();
                //再对当前结点进行右旋转
                rightRotate();
            }else {
                rightRotate();
            }

        }
    }


    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }


    //左旋转方法
    private void leftRotate() {
        //创建新的结点，以当前根结点的值
        Node newNode = new Node(value);
        //把新的结点的左子树设置成当前的结点 的左子树
        newNode.left = left;
        //把新的结点的右子树设置成当前结点的右子树的左子树
        newNode.right = right.right;
        //把当前节点的值替换成右子节点的值
        value = right.value;
        //把当前结点的右子树设置成当前结点的右子树的右子树
        right = right.right;
        //把当前结点的左子树设置成新的节点
        left = newNode;
    }

    /**
     * 右旋转
     */
    private void rightRotate() {
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;
    }


}