Java数据结构与算法-java数据结构与算法(五)

简介: Java数据结构与算法-java数据结构与算法

Java数据结构与算法-java数据结构与算法(四)https://developer.aliyun.com/article/1469492


树结构实际应用

堆排序

堆排序基本介绍

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

大顶堆

小顶堆

堆排序基本思想

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

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

堆排序步骤图解说明

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。  原始的数组 [4, 6, 8, 5, 9]

  1. 假设给定无序序列结构如下
  2. 此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点
    arr.length/2-1=5/2-1=1,也就是下面的 6 结点),从左至右,从下至上进行调整。
  3. 找到第二个非叶节点 4,由于[4,9,8]中 9 元素最大,4 和 9 交换。
  4. 这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中 6 最大,交换 4 和 6。

此时,我们就将一个无序序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换.

得到第二大元素。如此反复进行交换、重建、交换。

  1. .将堆顶元素 9 和末尾元素 4 进行交换
  2. 重新调整结构,使其继续满足堆定义
  3. 再将堆顶元素 8 与末尾元素 5 进行交换,得到第二大元素 8
  4. 后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

总结下堆排序的基本思路:

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

代码实现

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

  1. 堆排序不是很好理解,老师通过 Debug 帮助大家理解堆排序
  2. 堆排序的速度非常快,在我的机器上 8 百万数据 3 秒左右。O(nlogn)
package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: HeapSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/6 23:52
 * @version: 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] test = new int[8000000];
        //测试数据
        for (int i = 0; i < 8000000; i++) {
            test[i] = (int) (Math.random() * 800000);
        }
        long time = System.currentTimeMillis();
        heapsort(test);
        long end = System.currentTimeMillis();
        long t = ((end - time) / 1000);
        System.out.println("一共用时 " + t + "秒");
        int arr[] = {4, 6, 8, 5, 9};
    }
    public static void heapsort(int[] arr) {
        int temp = 0;
        //按照 大顶堆的方式调整堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        /*将最大元素和末尾元素交换,将最大元素放入数组末尾
         *重新调整结构,满足堆的定义
         * */
        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        //System.out.println("排序后的数组是 = " + Arrays.toString(arr));
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 大顶堆交换思路, 判断左右节点大小,之后判断左右节点的比对结果,与父节点判断,将最大值交还给父节点
     * @date: 2022/2/6 23:54
     * @param arr 存放需要将交换节点的数组
     * @param i   需要做调整的父节点索引
     * @param length 有多少节点需要调整
     * @return: void
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //   开始调整
        /* 说明
         * k =i*2+1按照之前线索查找树的公式,找出左子树的节点位置
         * */
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //判断条件 k(节点索引)首先不能大于我们要遍历的结点索引总数,之后判断左右节点的大小,交换
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            //找出最大的子节点,与父节点的值比对,
            if (arr[k] > temp) {
                //将较大的值放入到父节点
                arr[i] = arr[k];
                i = k; //i指向k , 继续循环比较
            } else {
                break;
            }
        }
        //    for 循环结束之后 我们i已经是父节点以及最大值的索引了
        // 将 temp 调整到最后免得位置
        arr[i] = temp;
    }
}

赫夫曼树

基本介绍

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

赫夫曼树几个重要概念和举例说明

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

赫夫曼树创建思路图解

给你一个数列 {13, 7, 8, 3, 29, 6, 1},要求转成一颗赫夫曼树.

构成赫夫曼树的步骤:

  1. 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
  2. 取出根节点权值最小的两颗二叉树
  3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
  4. 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数
    据都被处理,就得到一颗赫夫曼树

赫夫曼树的代码实现

package com.hyc.DataStructure.HuffmanTree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.HuffmanTreeDemo
 * @className: HuffmanTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/8 0:21
 * @version: 1.0
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node manTree = createHuffManTree(arr);
        //    测试
        preOrder(manTree);
    }
    //编写一个前序遍历的方法
    public static void preOrder(Node root) {
        if (root != null) {
            root.PreOrder();
        } else {
            System.out.println("空树无法遍历");
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * @date: 2022/2/8 0:42
     * @param arr 需要创建赫夫曼树的数组
     * @return: com.hyc.DataStructure.HuffmanTree.Node 返回已经创建好的赫夫曼树的根节点
     */
    public static Node createHuffManTree(int[] arr) {
        List<Node> nodes = new ArrayList<>();
        //(1)为了方便操作 我们先遍历数组生成对应节点 放入 arrayList
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        //循环处理
        while (nodes.size() > 1) {
            //    先用接口的sort 排序
            Collections.sort(nodes);
            System.out.println("nodes = " + nodes);
            //   (2) 取出根节点权值最小的两颗二叉树
            //    取出权值最小的结点
            Node leftnode = nodes.get(0);
            //取出根节点第二最小的二叉树
            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集合排序
 * 这里我们实现 compareble
 * */
class Node implements Comparable<Node> {
    //赫夫曼树 权重值
    int value;
    Node left;
    Node right;
    //    构造方法 创建节点的时候只需要有权重值就可以了
    public Node(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        //这里我们按照权重从小到大排序
        //从大到小只需要置负 -(this.value - o.value)
        return this.value - o.value;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.PreOrder();
        }
        if (this.right != null) {
            this.right.PreOrder();
        }
    }
}

赫夫曼编码

基本介绍

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

原理剖析

定长编码

变长编码

赫夫曼编码

传输的  字符串  ,按照字符的出险次数出现权重

  1. i like like like java do you like a java
  2. d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
  3. 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

步骤:

  1. 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
  2. 取出根节点权值最小的两颗二叉树
  3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
  4. 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,  就得到一颗赫夫曼树

根据赫夫曼树,给各个字符,规定编码 (前缀编码), 向左的路径为 0 向右的路径为 1 , 编码

如下:

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

10101001101111011110100110111101111010011011110111101000011000011100110011110000110  
01111000100100100110111101111011100100001100001110

长度为:133

原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%

此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性

赫夫曼编码是无损处理方案

注意事项

最佳实践-数据压缩(创建赫夫曼树)

将给出的一段文本,比如 "i like like  like java do you like a java"  , 根据前面的讲的赫夫曼编码原理,对其进行数  据 压 缩 处 理  ,形 式 如  :

1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110

步骤 1:

根据赫夫曼编码压缩数据的原理,需要创建 "i like like like java do you like a java" 对应的赫夫曼树

思路:前面已经分析过了,而且我们已然讲过了构建赫夫曼树的具体实现。

public static Node createHuffManTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //首先从小到大排序 list
            Collections.sort(nodes);
            //    找到list中最小的子树
            Node leftnode = nodes.get(0);
            //找到倒数第二小的
            Node rightnode = nodes.get(1);
            Node parent = new Node(null, leftnode.wight + rightnode.wight);
            parent.left = leftnode;
            parent.right = rightnode;
            //    删除两个被处理过的子树
            nodes.remove(leftnode);
            nodes.remove(rightnode);
            //    之后将parent 加入到list
            //   这样遍历到最后只剩下一个节点 就是我们需要的赫夫曼树
            nodes.add(parent);
        }
        return nodes.get(0);
    }

最佳实践-数据压缩(生成赫夫曼编码和赫夫曼编码后的数据)

我们已经生成了 赫夫曼树, 下面我们继续完成任务

生成赫夫曼树对应的赫夫曼编码 , 如下表:

=01  a=100 d=11000 u=11001  e=1110  v=11011  i=101 y=11010 j=0010 k=1111 l=000 o=0011

使用赫夫曼编码来生成赫夫曼编码数据  ,即按照上面的赫夫曼编码,将"i like  like like  java do you like  a java"

字符串生成对应的编码数据, 形式如下:

1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

思路:前面已经分析过了,而且我们讲过了生成赫夫曼编码的具体实现。

/* 生成赫夫曼树对应的赫夫曼编码
     * 思路 :
     * 1. 将赫夫曼编码存放在map<byte,string>的形式的map里
     * 2。在生成赫夫曼编码表示,需要去拼接一些路径  定一个一个 stringbuilder 存放叶子节点的路径
     * */
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //存放叶子节点的路径的 stringbuilder
    static StringBuilder stringBuilder = new StringBuilder();
    //为了调用方便 重载getcode
    public static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //  处理左子树
        getCodes(root.left, "0", stringBuilder);
        //处理右子树
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将传入的node节点的所有子节点的赫夫曼编码得到,并且放入huffmanCodes集合中
     * @date: 2022/2/12 15:07
     * @return: void
     * @param node          传入的节点
     * @param code          路径,左子节点是 0 右子节点事 1
     * @param stringBuilder 用于拼接路径
     */
    public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        //将code 加入到 string builder1
        stringBuilder1.append(code);
        if (node != null) {
            //    如果为null 不处理
            //判断是否为叶子结点
            if (node.data == null) {
                //如果data不为空那么代表非叶子节点
                //   向左继续递归
                getCodes(node.left, "0", stringBuilder1);
                //    向右边递归
                getCodes(node.right, "1", stringBuilder1);
            } else {
                //如果进入到这里说明是一个叶子结点
                //    存入到 huffmanCodes这个集合中
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }
    }

最佳实践-数据解压(使用赫夫曼编码解码)

使用赫夫曼编码来解码数据,具体要求是

  1. 前面我们得到了赫夫曼编码和对应的编码  byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77  , -57, 6, -24, -14, -117, -4, -60, -90, 28]
  2. 现在要求使用赫夫曼编码, 进行解码,又重新得到原来的字符串"i like like like java do you like a java"
  3. 思路:解码过程,就是编码的一个逆向操作。
/**
     * @author 冷环渊 Doomwatcher
     * @context: 将一个byte 转成 一个二进制的字符串
     * @date: 2022/2/12 23:14
     * @param flag 标志是否需要不高位,如果是ture 表示需要补高位,如果是false表示不需要
     * @param b 传入的 byte
     * @return: java.lang.String 返回的b 对应的二进制的字符串(注意事按照补码返回)
     */
    public static String byteToBitString(boolean flag, byte b) {
        //使用变量保存 b
        int temp = b;
        //如果是正数我们还需要补高位
        if (flag) {
            //按位与 256 1 0000 0000| 00000 0001 => 1 0000 0001
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }
  /**
     * @author 冷环渊 Doomwatcher
     * @context: 完成对数据的解压
     * 思路:
     * 1. 其实这就是我们之前压缩思路的逆向,
     * 2.我们先需要将 byte数组形式的转成二进制的心态,
     * 3. 之后转成赫夫曼编码,之后转换成字符
     * @date: 2022/2/12 21:49
     * @param huffmanBytes 赫夫曼编码对应的byte数组
     * @param huffmanCodes 赫夫曼编码表
     * @return: void
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        //1. 先得到huffmancodebytes 对应的 二进制字符串,如 1010100010111
        StringBuilder stringBuilder = new StringBuilder();
        //将byte 数组转成二进制字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        //System.out.println("赫夫曼字节数组解码二进制=>" + stringBuilder.toString());
        //    按照置顶的赫夫曼编码把字符串进行解码
        //    把赫夫曼编码进行转换 a ->100 100->a
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> stringByteEntry : huffmanCodes.entrySet()) {
            map.put(stringByteEntry.getValue(), stringByteEntry.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) {
                //取出一个 ‘1’或者‘0’,i不动 让 count移动直到匹配到一个字符,递增取出
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b == null) {
                    //  说明没有匹配到
                    count++;
                } else {
                    //匹配到就退出循环
                    flag = false;
                }
            }
            list.add(b);
            //匹配到之后 i 直接移动步长为count位,就可以继续匹配了,
            i += count;
        }
        //当for循环结束后我们的list存放了所有的字符
        //    之后把list 中的数据放入byte[]并且返回
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }

最佳实践-文件压缩

我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压, 具体要求:

给你一个图片文件,要求对其进行无损压缩, 看看压缩效果如何。

思路:读取文件-> 得到赫夫曼编码表 -> 完成压缩

/**
     * @author 冷环渊 Doomwatcher
     * @context: 编写方法 完成对压缩文件的解压
     * @date: 2022/2/13 0:33
     * @param zipFile 准备解压的文件路径
     * @param dstFile 将文件解压到什么路径
     * @return: void
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义对象输入流
        ObjectInputStream ois = null;
        //输出流
        OutputStream os = null;
        try {
            //    创建文件输入流
            is = new FileInputStream(zipFile);
            //    创建对象输入流
            ois = new ObjectInputStream(is);
            byte[] huffmanbytes = (byte[]) ois.readObject();
            //    读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //    解码
            byte[] bytes = decode(huffmanCodes, huffmanbytes);
            //将byte 数组写入目标文件
            os = new FileOutputStream(dstFile);
            //    写数据到fstFile文件
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

最佳实践-文件解压(文件恢复)

具体要求:将前面压缩的文件,重新恢复成原来的文件。

思路:读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)

/**
     * @author 冷环渊 Doomwatcher
     * @context: 编写方法 完成对压缩文件的解压
     * @date: 2022/2/13 0:33
     * @param zipFile 准备解压的文件路径
     * @param dstFile 将文件解压到什么路径
     * @return: void
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义对象输入流
        ObjectInputStream ois = null;
        //输出流
        OutputStream os = null;
        try {
            //    创建文件输入流
            is = new FileInputStream(zipFile);
            //    创建对象输入流
            ois = new ObjectInputStream(is);
            byte[] huffmanbytes = (byte[]) ois.readObject();
            //    读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //    解码
            byte[] bytes = decode(huffmanCodes, huffmanbytes);
            //将byte 数组写入目标文件
            os = new FileOutputStream(dstFile);
            //    写数据到fstFile文件
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

代码汇总

package com.hyc.DataStructure.huffmanCode;
import java.io.*;
import java.util.*;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.huffmanCode
 * @className: huffmanCodeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/9 19:06
 * @version: 1.0
 */
public class huffmanCodeDemo {
    public static void main(String[] args) {
//        压缩文件测试
//        String srcfile = "D:\\JavaEngineer\\algorithm\\code\\DataStructure\\src.bmp";
//        String dstfile = "D:\\JavaEngineer\\algorithm\\code\\DataStructure\\srcdst.zip";
//        zipFile(srcfile, dstfile);
//        解压文件测试
        String zipfile = "D:\\\\JavaEngineer\\\\algorithm\\\\code\\\\DataStructure\\\\srcdst.zip";
        String dstFile = "D:\\\\JavaEngineer\\\\algorithm\\\\code\\\\DataStructure\\\\src1.bmp";
        unZipFile(zipfile, dstFile);
/*        String content = "i like like like java do you like a java";
        byte[] contentbytes = content.getBytes();
        System.out.println("压缩之前的长度 =>" + contentbytes.length); // 40
        byte[] huffmanCodesBytes = huffmanZip(contentbytes);
        System.out.println("压缩之后的长度 =>" + huffmanCodesBytes.length);
        byte[] decode = decode(huffmanCodes, huffmanCodesBytes);
        System.out.println("输出解码之后的字符串" + new String(decode));*/
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 编写方法 完成对压缩文件的解压
     * @date: 2022/2/13 0:33
     * @param zipFile 准备解压的文件路径
     * @param dstFile 将文件解压到什么路径
     * @return: void
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义对象输入流
        ObjectInputStream ois = null;
        //输出流
        OutputStream os = null;
        try {
            //    创建文件输入流
            is = new FileInputStream(zipFile);
            //    创建对象输入流
            ois = new ObjectInputStream(is);
            byte[] huffmanbytes = (byte[]) ois.readObject();
            //    读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //    解码
            byte[] bytes = decode(huffmanCodes, huffmanbytes);
            //将byte 数组写入目标文件
            os = new FileOutputStream(dstFile);
            //    写数据到fstFile文件
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 文件压缩
     * @date: 2022/2/13 0:17
     * @param srcFile 传入的希望压缩的文件的全路径
     * @param dstFile 压缩之后需要输出的文件路径
     * @return: void
     */
    public static void zipFile(String srcFile, String dstFile) {
        //    创建文件输出流
        //    创建文件输入流
        FileInputStream is = null;
        FileOutputStream os = null;
        ObjectOutputStream oos = null;
        try {
            is = new FileInputStream(srcFile);
            //    创建一个和源文件大小一样的byte数组 当做缓冲区
            byte[] bytes = new byte[is.available()];
            //    读取文件
            is.read(bytes);
            //获取到文件对应的赫夫曼编码
            byte[] huffmanBytes = huffmanZip(bytes);
            //    创建文件的输出流,存放压缩文件
            os = new FileOutputStream(dstFile);
            //    创建一个和文件输出流关联的objoutputstream
            oos = new ObjectOutputStream(os);
            //把赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //这里我们用对象流的方式写入赫夫曼编码,目的是为了回复文件的时候使用
            oos.writeObject(huffmanCodes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                is.close();
                os.close();
                oos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 完成对数据的解压
     * 思路:
     * 1. 其实这就是我们之前压缩思路的逆向,
     * 2.我们先需要将 byte数组形式的转成二进制的心态,
     * 3. 之后转成赫夫曼编码,之后转换成字符
     * @date: 2022/2/12 21:49
     * @param huffmanBytes 赫夫曼编码对应的byte数组
     * @param huffmanCodes 赫夫曼编码表
     * @return: void
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        //1. 先得到huffmancodebytes 对应的 二进制字符串,如 1010100010111
        StringBuilder stringBuilder = new StringBuilder();
        //将byte 数组转成二进制字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        //System.out.println("赫夫曼字节数组解码二进制=>" + stringBuilder.toString());
        //    按照置顶的赫夫曼编码把字符串进行解码
        //    把赫夫曼编码进行转换 a ->100 100->a
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> stringByteEntry : huffmanCodes.entrySet()) {
            map.put(stringByteEntry.getValue(), stringByteEntry.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) {
                //取出一个 ‘1’或者‘0’,i不动 让 count移动直到匹配到一个字符,递增取出
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b == null) {
                    //  说明没有匹配到
                    count++;
                } else {
                    //匹配到就退出循环
                    flag = false;
                }
            }
            list.add(b);
            //匹配到之后 i 直接移动步长为count位,就可以继续匹配了,
            i += count;
        }
        //当for循环结束后我们的list存放了所有的字符
        //    之后把list 中的数据放入byte[]并且返回
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将一个byte 转成 一个二进制的字符串
     * @date: 2022/2/12 23:14
     * @param flag 标志是否需要不高位,如果是ture 表示需要补高位,如果是false表示不需要
     * @param b 传入的 byte
     * @return: java.lang.String 返回的b 对应的二进制的字符串(注意事按照补码返回)
     */
    public static String byteToBitString(boolean flag, byte b) {
        //使用变量保存 b
        int temp = b;
        //如果是正数我们还需要补高位
        if (flag) {
            //按位与 256 1 0000 0000| 00000 0001 => 1 0000 0001
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }
    /**
     *
     * @author 冷环渊 Doomwatcher
     * @context: 封装 赫夫曼编码压缩
     * @date: 2022/2/12 20:12
     * @param bytes
     * @return: byte[]
     */
    public static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        Node huffManTreeroot = createHuffManTree(nodes);
        Map<Byte, String> codes = getCodes(huffManTreeroot);
        byte[] huffmanCodeBytes = zip(bytes, codes);
        return huffmanCodeBytes;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 编写一个方法,将字符串转成对应的 Byte[] 数组,通过生成的哈夫曼编码表,返回一个赫夫曼编码压缩后的Byte[]
     * 举例子: string content = i like like like java do you like java
     * 返回的字符串应该是一大串 八位的byte
     * 比如 huffmanCodeBytes[0] = 10101000(补码) => byte[推导 推成反码 10101000 -1 => 10100111(反码)] 原码就是符号位不变,其他取反 [11011000]
     * @date: 2022/2/12 15:35
     * @param bytes        原始字符串对应的byte
     * @param huffmanCodes 生成赫夫曼编码的map
     * @return: java.lang.Byte[]
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //  首先利用 huffmanCode是将 bytes 转成赫夫曼编码的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        //System.out.println(stringBuilder);
        //    将对应的字符串 转成 byte[]数组
        //    返回 数组 huffmancodeBytes的长度
        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>的形式的map里
     * 2。在生成赫夫曼编码表示,需要去拼接一些路径  定一个一个 stringbuilder 存放叶子节点的路径
     * */
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //存放叶子节点的路径的 stringbuilder
    static StringBuilder stringBuilder = new StringBuilder();
    //为了调用方便 重载getcode
    public static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //  处理左子树
        getCodes(root.left, "0", stringBuilder);
        //处理右子树
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将传入的node节点的所有子节点的赫夫曼编码得到,并且放入huffmanCodes集合中
     * @date: 2022/2/12 15:07
     * @return: void
     * @param node          传入的节点
     * @param code          路径,左子节点是 0 右子节点事 1
     * @param stringBuilder 用于拼接路径
     */
    public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        //将code 加入到 string builder1
        stringBuilder1.append(code);
        if (node != null) {
            //    如果为null 不处理
            //判断是否为叶子结点
            if (node.data == null) {
                //如果data不为空那么代表非叶子节点
                //   向左继续递归
                getCodes(node.left, "0", stringBuilder1);
                //    向右边递归
                getCodes(node.right, "1", stringBuilder1);
            } else {
                //如果进入到这里说明是一个叶子结点
                //    存入到 huffmanCodes这个集合中
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }
    }
    //前序遍历
    public static void PreOrder(Node node) {
        if (node != null) {
            node.PreOrder();
        } else {
            System.out.println("空树无法遍历");
        }
    }
    /**
     *
     * @author 冷环渊 Doomwatcher
     * @context: 用来生成每一个节点的出现次数的list集合
     * @date: 2022/2/10 2:40
     * @param bytes 存放每一个字母的数组
     * @return: java.util.List<com.hyc.DataStructure.huffmanCode.Node>  返回一个带着字母出现权重的list
     */
    public static List<Node> getNodes(byte[] bytes) {
        //    创建一个 arraylist
        ArrayList<Node> nodes = new ArrayList<>();
        //    遍历bytes 统计每一个bytes 出现的次数 用 map 来统计
        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;
    }
    public static Node createHuffManTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //首先从小到大排序 list
            Collections.sort(nodes);
            //    找到list中最小的子树
            Node leftnode = nodes.get(0);
            //找到倒数第二小的
            Node rightnode = nodes.get(1);
            Node parent = new Node(null, leftnode.wight + rightnode.wight);
            parent.left = leftnode;
            parent.right = rightnode;
            //    删除两个被处理过的子树
            nodes.remove(leftnode);
            nodes.remove(rightnode);
            //    之后将parent 加入到list
            //   这样遍历到最后只剩下一个节点 就是我们需要的赫夫曼树
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}
class Node implements Comparable<Node> {
    //用于存放字符的ascll值
    Byte data;
    //出现的次数 权重
    int wight;
    Node left;
    Node right;
    public Node(Byte data, int wight) {
        this.data = data;
        this.wight = wight;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", wight=" + wight +
                '}';
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.PreOrder();
        }
        if (this.right != null) {
            this.right.PreOrder();
        }
    }
    @Override
    public int compareTo(Node o) {
        return this.wight - o.wight;
    }
}

赫夫曼编码压缩文件注意事项

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

二叉排序树

先看一个需求:

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

使用数组

数组未排序, 优点:直接在数组尾添加,速度快。 缺点:查找速度慢.

数组排序,优点:可以使用二分查找,查找速度快,缺点:为了保证数组有序,在添加新数据时,找到插入位

置后,后面的数据需整体移动,速度慢。

链式存储-链表

不管链表是否有序,查找速度都慢,添加数据速度比数组快,不需要数据整体移动。

二叉排序树介绍

二叉排序树:BST:  (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当 前节点的值小,右子节点的值比当前节点的值大。

特别声明

特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点

比如针对前面的数据  (7, 3, 10, 12, 5, 1, 9) ,对应的二叉排序树为:

二叉排序树创建和遍历

一个数组创建成对应的二叉排序树,并使用中序遍历二叉排序树,比如:  数组为 Array(7,  3, 10, 12, 5, 1, 9) , 创

建成对应的二叉排序树为 :

二叉排序树的删除

二叉排序树的删除情况比较复杂,有下面三种情况需要考虑

  1. 删除叶子节点 (比如:2, 5, 9, 12)
  2. 删除只有一颗子树的节点 (比如:1)
  3. 删除有两颗子树的节点. (比如:7, 3,10 )

对删除结点的各种情况的思路分析:

第一种情况:  删除叶子节点  (比如:2,  5, 9, 12)

思路:

  1. 需求先去找到要删除的结点 targetNode
  2. 找到 targetNode 的 父结点 parent
  3. 确定 targetNode 是 parent 的左子结点 还是右子结点
  4. 根据前面的情况来对应删除

左子结点 parent.left = null

右子结点 parent.right = null;

第二种情况: 删除只有一颗子树的节点 比如 1

思路 :

  1. 需求先去找到要删除的结点 targetNode
  2. 找到 targetNode 的 父结点 parent
  3. 确定 targetNode 的子结点是左子结点还是右子结点
  4. targetNode 是 parent 的左子结点还是右子结点
  5. 如果 targetNode 有左子结点
  1. 如果 targetNode 是 parent 的左子结点  parent.left =  targetNode.left;
  2. 如果  targetNode  是 parent  的右子结点  parent.right  = targetNode.left;
  1. 如果 targetNode 有右子结点
  1. 如果 targetNode 是 parent 的左子结点  parent.left = targetNode.right
  2. 如果  targetNode  是 parent  的右子结点  parent.right  = targetNode.right

情况三  : 删除有两颗子树的节点. (比如:7, 3,10 )

思路  :

  1. 需求先去找到要删除的结点 targetNode
  2. 找到 targetNode 的 父结点 parent
  3. 从 targetNode 的右子树找到最小的结点
  4. 用一个临时变量,将 最小结点的值保存 temp = 11
  5. 删除该最小结点
  6. targetNode.value = temp

二叉排序树代码实现

package com.hyc.DataStructure.binarysorttree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.binarysorttree
 * @className: BinarySortDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/15 16:33
 * @version: 1.0
 */
public class BinarySortDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        //    中序要遍历
        binarySortTree.infixOrder();
        //    测试删除节点
        binarySortTree.delNode(2);
        binarySortTree.delNode(7);
        binarySortTree.delNode(3);
        binarySortTree.delNode(12);
        binarySortTree.delNode(5);
        binarySortTree.delNode(1);
        binarySortTree.delNode(9);
        binarySortTree.delNode(10);
        System.out.println("删除节点后");
        //    中序要遍历
        binarySortTree.infixOrder();
    }
}
class BinarySortTree {
    private Node root;
    //查找要删除的节点
    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.searchParent(value);
        }
    }
    //删除节点方法
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //    需要先去找到要删除的节点,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 minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else {
                //    删除有一颗子树
                //    如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    //判断 parent 的非空判断
                    if (parent != null) {
                        //    如果targetNode是Parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            //targentNode 是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 {
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
 
            }
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 返回的以node为根节点的二叉树的最小节点值
     * 删除node 为根节点的二叉排序树的最小节点
     * @date: 2022/2/17 22:19
     * @param node 传入的节点 (当前二叉排序树树的根节点)
     * @return: int 返回的以node为根节点的二叉排序树的最小节点值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //    循环查找左节点 就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这个target就指向了最小的节点
        //删除最小节点
        delNode(target.value);
        return target.value;
    }
    //    添加节点的方法
    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;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 找到想要查到要删除的节点
     * @date: 2022/2/17 14:15
     * @param value 想要删除的节点的值
     * @return: com.hyc.DataStructure.binarysorttree.Node 如果找到了就返回节点,如果没找到那就返回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);
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 查找要删除节点的父节点
     * @date: 2022/2/17 14:23
     * @param value value 要找的节点值
     * @return: com.hyc.DataStructure.binarysorttree.Node 返回的事要删除的节点
     */
    public Node searchParent(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.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                //向右子树递归查找
                return this.right.searchParent(value);
            } else {
                //没有找到
                return null;
            }
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //    判断传入接待你值是否大于当前节点
        if (node.value < this.value) {
            //如果当前节点左子节点为null
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            //    判断节点如果大于当前节点的值
            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();
        }
    }
}

平衡二叉树(AVL 树)

给你一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST), 并分析问题所在. :

  1. 左子树全部为空,从形式上看,更像一个单链表.
  2. 插入速度没有影响
  3. 查询速度明显降低(因为需要依次比较), 不能发挥 BST  的优势,因为每次还需要比较左子树,其查询速度比

解决方案-平衡二叉树(AVL)

基本介绍

  1. 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为 AVL 树, 可以保证查询效率较高。
  2. 具有以下特点:它是一  棵空树或它的左右两个子树的高度差的绝对值不超过  1,并且左右两个子树都是一棵  平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
  3. 举例说明, 看看下面哪些 AVL 树, 为什么?

应用案例-单旋转(左旋转)

给你一个数列,创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}

左旋转代码

//左旋转方法
    public void leftRotate() {
        // 创建新节点 以当前节点的值
        Node newnode = new Node(value);
        //    把新节点的左子树这只成当前节点的左子树
        newnode.left = left;
        //    把新节点的右子树设置成当前节点的右子树的左子树
        newnode.right = right.left;
        //把当前节点的值 替换成右子节点的值
        value = right.value;
        //    把当前节点右子树设置成下一个节点的右子树
        right = right.right;
        //    把当前节点的左子树设置成新的节点
        left = newnode;
    }

应用案例-单旋转(右旋转)

给你一个数列,创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}

右旋转代码

//右旋转方法
    public void rightRotate() {
        Node newnode = new Node(value);
        newnode.right = right;
        newnode.left = left.right;
        value = left.value;
        left = left.left;
        right = newnode;
    }

应用案例-双旋转

前面的两个数列,进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下,单旋转  不能完成平衡二叉树的转换。比如数列

int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到,并没有转成 AVL 树.

int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到,并没有转成 AVL 树

  1. 当符号右旋转的条件时
  2. 如果它的左子树的右子树高度大于它的左子树的高度
  3. 先对当前这个结点的左节点进行左旋转
  4. 在对当前结点进行右旋转的操作即可

代码汇总

package com.hyc.DataStructure.AVL;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.AVL
 * @className: avlTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/18 23:30
 * @version: 1.0
 */
public class avlTreeDemo {
    public static void main(String[] args) {
        //左旋转demo实例
        //int[] arr = {4, 3, 6, 5, 7, 8};
        //右旋转demo实例
        int[] arr = {10, 12, 8, 9, 7, 6};
        //int[] arr = {10, 11, 7, 6, 8, 9};
        //创建一个 AVLTree对象
        AVLTree avlTree = new AVLTree();
        //添加结点
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }
        //遍历
        System.out.println("中序遍历");
        avlTree.infixOrder();
        System.out.println("在平衡处理~~");
        System.out.println("树的高度=" + avlTree.getRoot().height()); //3
        System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
        System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
        System.out.println("当前的根结点=" + avlTree.getRoot());//8
    }
}
class AVLTree {
    private Node root;
    public Node getRoot() {
        return root;
    }
    public void setRoot(Node root) {
        this.root = root;
    }
    //查找要删除的节点
    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.searchParent(value);
        }
    }
    //删除节点方法
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //    需要先去找到要删除的节点,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 minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else {
                //    删除有一颗子树
                //    如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    //判断 parent 的非空判断
                    if (parent != null) {
                        //    如果targetNode是Parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            //targentNode 是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 {
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 返回的以node为根节点的二叉树的最小节点值
     * 删除node 为根节点的二叉排序树的最小节点
     * @date: 2022/2/17 22:19
     * @param node 传入的节点 (当前二叉排序树树的根节点)
     * @return: int 返回的以node为根节点的二叉排序树的最小节点值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //    循环查找左节点 就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这个target就指向了最小的节点
        //删除最小节点
        delNode(target.value);
        return target.value;
    }
    //    添加节点的方法
    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;
    }
    //左旋转方法
    public void leftRotate() {
        // 创建新节点 以当前节点的值
        Node newnode = new Node(value);
        //    把新节点的左子树这只成当前节点的左子树
        newnode.left = left;
        //    把新节点的右子树设置成当前节点的右子树的左子树
        newnode.right = right.left;
        //把当前节点的值 替换成右子节点的值
        value = right.value;
        //    把当前节点右子树设置成下一个节点的右子树
        right = right.right;
        //    把当前节点的左子树设置成新的节点
        left = newnode;
    }
    //右旋转方法
    public void rightRotate() {
        Node newnode = new Node(value);
        newnode.right = right;
        newnode.left = left.right;
        value = left.value;
        left = left.left;
        right = newnode;
    }
    //返回左子树的高度
    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;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 找到想要查到要删除的节点
     * @date: 2022/2/17 14:15
     * @param value 想要删除的节点的值
     * @return: Node 如果找到了就返回节点,如果没找到那就返回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);
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 查找要删除节点的父节点
     * @date: 2022/2/17 14:23
     * @param value value 要找的节点值
     * @return: Node 返回的事要删除的节点
     */
    public Node searchParent(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.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                //向右子树递归查找
                return this.right.searchParent(value);
            } else {
                //没有找到
                return null;
            }
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //    判断传入接待你值是否大于当前节点
        if (node.value < this.value) {
            //如果当前节点左子节点为null
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            //    判断节点如果大于当前节点的值
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        //    当前添加玩一个节点之后  判断( 右子树的高度 - 左子树的高度 >1 )就代表需要左旋转
        if (rightHeight() - leftHeight() > 1) {
            //如果他的右子树的左子树高度大于它的右子树的右子树的高度
            if (right != null && right.leftHeight() > right.leftHeight()) {
                //    先对右子节点,进行右旋转
                right.rightRotate();
                leftHeight();
            } 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();
        }
    }
}


Java数据结构与算法-java数据结构与算法(六)https://developer.aliyun.com/article/1469494

目录
相关文章
|
4天前
|
机器学习/深度学习 算法 存储
[数据结构]——算法的时间复杂度和空间复杂度
[数据结构]——算法的时间复杂度和空间复杂度
|
2天前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
6 0
|
2天前
|
Java
JAVA数据结构刷题 -- 二叉树进阶
JAVA数据结构刷题 -- 二叉树进阶
9 0
|
2天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
8 0
|
3天前
|
存储 自然语言处理 Java
数据结构-Java Map 和 Set-2
数据结构-Java Map 和 Set
6 0
|
3天前
|
Java
数据结构-Java Map 和 Set-1
数据结构-Java Map 和 Set
10 0
|
3天前
|
存储 搜索推荐 算法
C语言数据结构算法,常用10种排序实战
插入排序(Insertion Sort) 希尔排序(Shell Sort) 选择排序(Selection Sort) 冒泡排序(Bubble Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 基数排序(Radix Sort)
8 1
C语言数据结构算法,常用10种排序实战
|
4天前
|
存储 Java 索引
【JAVA学习之路 | 进阶篇】浅谈数据结构
【JAVA学习之路 | 进阶篇】浅谈数据结构
|
5天前
|
算法 Java
Java中CAS算法的集中体现:Atomic原子类库,你了解吗?
【5月更文挑战第15天】Java中CAS算法的集中体现:Atomic原子类库,你了解吗?
18 1
|
8天前
|
算法 搜索推荐 Java
滚雪球学Java(33):数组算法大揭秘:应用案例实战分享
【5月更文挑战第8天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
35 8
滚雪球学Java(33):数组算法大揭秘:应用案例实战分享