• 数据结构和算法——树结构

    二叉树

    又叫二叉排序树。

    节点是数量为，2^{n}-1，n为层数。

    满二叉树：所有的叶子节点都在最后一层。

    完全二叉树：如果所有叶子节点都在最后一层和倒数第二层，而且每个叶子节点都有左右子节点。

    完全二叉树
    完全二叉树

    前序遍历

    1、先输出当前节点（初始是root节点）。

    2、如果左子节点不为空，则递归继续前序遍历。

    3、如果右子节点不为空，则递归继续前序遍历。

    1. class HeroNode {
    2.     private int no;
    3.     private String name;
    4.     private HeroNode left, right;
    5. }
    1.     public HeroNode preOrderSearch(int no) {
    2.         if (this.no == no) {
    3.             return this;
    4.         }
    5.         HeroNode resNode;
    6.         if (this.left != null) {
    7.             resNode = this.left.preOrderSearch(no);
    8.             if (resNode != null) {
    9.                 return resNode;
    10.             }
    11.         }
    12.         if (this.right != null) {
    13.             resNode = this.right.preOrderSearch(no);
    14.             if (resNode != null) {
    15.                 return resNode;
    16.             }
    17.         }
    18.         return null;
    19.     }

    中序遍历

    1、如果当前节点的左子节点不为空，则递归中序遍历。

    2、输出当前节点。

    3、如果当前节点的右子节点不为空，则递归中序遍历。

    1.     public HeroNode infixOrderSearch(int no) {
    2.         HeroNode resNode;
    3.         if (this.left != null) {
    4.             resNode = this.left.infixOrderSearch(no);
    5.             if (resNode != null) {
    6.                 return resNode;
    7.             }
    8.         }
    9.         if (this.no == no) {
    10.             return this;
    11.         }
    12.         if (this.right != null) {
    13.             resNode = this.right.infixOrderSearch(no);
    14.             if (resNode != null) {
    15.                 return resNode;
    16.             }
    17.         }
    18.         return null;
    19.     }

    后序遍历

    左右中

    1、如果当前节点的左子节点不为空，则递归后序遍历。

    2、如果当前节点的右子节点不为空，则递归后序遍历。

    3、输出当前节点。

    1.     public HeroNode postOrderSearch(int no) {
    2.         HeroNode resNode;
    3.         if (this.left != null) {
    4.             resNode = this.left.postOrderSearch(no);
    5.             if (resNode != null) {
    6.                 return resNode;
    7.             }
    8.         }
    9.         if (this.right != null) {
    10.             resNode = this.right.postOrderSearch(no);
    11.             if (resNode != null) {
    12.                 return resNode;
    13.             }
    14.         }
    15.         if (this.no == no) {
    16.             return this;
    17.         }
    18.         return null;
    19.     }

    二叉树节点的删除，如果是中间节点，则整个中间节点都删除。

    1.     public void delNode(int no) {
    2.         if (this.no == no) {
    3.             return;
    4.         }
    5.         if (this.left != null) {
    6.             if (this.left.no == no) {
    7.                 this.left = null;
    8.             } else {
    9.                 this.left.delNode(no);
    10.             }
    11.         }
    12.         if (this.right != null) {
    13.             if (this.right.no == no) {
    14.                 this.right = null;
    15.             } else {
    16.                 this.right.delNode(no);
    17.             }
    18.         }
    19.     }

    顺序存储二叉树

    顺序二叉树通常是完全二叉树。

    第n(n是下标)个元素的左子节点为 2 * n + 1

    第n个元素的右子节点为 2 * n + 2

    第n个元素的父节点为 (n - 1) / 2

    堆排序用到顺序存储二叉树的结构。

    线索化二叉树

    充分的利用到了叶子节点的空指针。

    1. class HeroNode {
    2.     private int no;
    3.     private String name;
    4.     private HeroNode left, right;
    5.     private int leftType; // 0 指向的是左子树 1指向前驱节点
    6.     private int rightType; // 0 指向的是右子树 1指向后继节点
    7. }

     对线索二叉树进行中序线索化的方法

    1.     public void threadedNodes(HeroNode node) {
    2.         if (node == null) {
    3.             return;
    4.         }
    5.         threadedNodes(node.getLeft()); // 先线索化左子树
    6.         // 再线索化当前节点
    7.         if (node.getLeft() == null) { // 前驱
    8.             node.setLeft(pre);
    9.             node.setLeftType(1);
    10.         }
    11.         if (pre != null && pre.getRight() == null) { // 后继
    12.             pre.setRight(node);
    13.             pre.setRightType(1);
    14.         }
    15.         pre = node;
    16.         threadedNodes(node.getRight()); // 最后线索化右子树
    17.     }

    线索化二叉树的中序遍历

    1.  class ThreadedBinaryTree {
    2.     private HeroNode root;
    3.     private HeroNode pre = null; // 指向前驱节点
    4.     public void threadedList() {
    5.         HeroNode node = root;
    6.         while (node != null) {
    7.             while (node.getLeftType() == 0) { // 到左下角
    8.                 node = node.getLeft();
    9.             }
    10.             System.out.println(node);
    11.             while (node.getRightType() == 1) {
    12.                 node = node.getRight();
    13.                 System.out.println(node);
    14.             }
    15.             node = node.getRight();
    16.         }
    17.     }
    18. }

    什么是大顶堆，什么是小顶堆？ 

    每个节点的值都小于等于其左右孩子节点的值，称为小顶堆。反之是大顶堆。

    大顶堆的特点：arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2]

    小顶堆的特点：arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2]

    i 是下标

    堆排序：数据结构和算法——排序算法-CSDN博客

    赫夫曼树

    路径长度等于层数-1；

    节点的权就是节点的值；

    节点的带权路径长度为：从根节点到该节点之间的路径长度与该节点的权的乘积；

    树的带权路径长度(WPL)为：所有叶子节点的带权路径长度之和；

    赫夫曼树是带权路径长度(WPL)最短的树，权值越大的节点离根节点越近；

    这不是赫夫曼树WPL=13*2+7*2+8*2+3*2=62
    这是赫夫曼树WPL=13*1+2*2+7*3+3*3=59

    如何构建一棵赫夫曼树？

    1）将数组从小到大排序，每个数据都是一个节点，每个节点都是一棵二叉树树；

    2）取出根节点权值最小的两棵二叉树；

    3）组成一棵新的二叉树，新二叉树的根节点的权值是前两棵二叉树根节点权值的和。

    4）再将新二叉树放到数组中。不断重复1-2-3-4的步骤，直到数组只剩下最后一个元素。

    通过数组构建赫夫曼树

    1. public class HuffmanTree {
    2.     public static void main(String[] args) {
    3.         int[] arr = {13, 7, 8, 3, 29, 6, 1}; // {1, 3, 6, 7, 8, 13, 29}
    4.         Node root = createHuffmanTree(arr);
    5.         preOrder(root);
    6.     }
    7.  
    8.     // 数组 to 赫夫曼树
    9.     public static Node createHuffmanTree(int[] arr) {
    10.         List list = new ArrayList<>();
    11.         for (int value : arr) { // int[] to ArrayList
    12.             list.add(new Node(value));
    13.         }
    14.         while (list.size() > 1) {
    15.             Collections.sort(list);
    16.             // 1、取出最小的两个数
    17.             Node leftNode = list.get(0); // 取出权值最小的二叉树
    18.             Node rightNode = list.get(1); // 取出权值第二小的二叉树
    19.             // 2、构建一棵新树
    20.             Node parent = new Node(leftNode.value + rightNode.value);
    21.             parent.left = leftNode;
    22.             parent.right = rightNode;
    23.             // 3、从ArrayList里删掉掉leftNode和rightNode
    24.             list.remove(leftNode);
    25.             list.remove(rightNode);
    26.             // 4、新树加到原数组中
    27.             list.add(parent);
    28.         }
    29.         return list.get(0);
    30.     }
    31.  
    32.     public static void preOrder(Node root) {
    33.         if (root != null) {
    34.             root.preOrder();
    35.         } else {
    36.             System.out.println("空树不能遍历");
    37.         }
    38.     }
    39. }
    40.  
    41.  
    42. class Node implements Comparable {
    43.     int value; // 节点的权值
    44.     Node left, right;
    45.  
    46.     public Node(int value) {
    47.         this.value = value;
    48.     }
    49.  
    50.     // 前序遍历
    51.     public void preOrder() {
    52.         System.out.println(this);
    53.         if (this.left != null) {
    54.             this.left.preOrder();
    55.         }
    56.         if (this.right != null) {
    57.             this.right.preOrder();
    58.         }
    59.     }
    60.  
    61.     @Override
    62.     public String toString() {
    63.         return "Node{" +
    64.                 "value=" + value +
    65.                 '}';
    66.     }
    67.  
    68.     @Override
    69.     public int compareTo(Node node) {
    70.         return this.value - node.value;
    71.     }
    72. }

    赫夫曼编码

    也称为可变字长编码(每个字符用来表示的二进制位长度不确定)，把字符串发放到赫夫曼树里，可以对数据进行压缩和解压，压缩率可以达到20%~90%。是无损压缩，每次构建的赫夫曼树有可能不同；

    1. public class HuffmanCode {
    2.     public static void main(String[] args) {
    3.         String content = "i like like like java do you like a java";
    4.         // 10100
    5.         byte[] contentBytes = content.getBytes(); // oldString to ascii 例如：171717
    6.         // 1、压缩
    7.         byte[] huffmanZip = huffmanZip(contentBytes);
    8.  
    9.         // 2、解压
    10.         byte[] sourceBytes = decode(huffmanCodes, huffmanZip);
    11.         String oldString = new String(sourceBytes);
    12.     }
    13.  
    14.     /**
    15.      * 将byte转成二进制的字符串
    16.      *
    17.      * @param flag 是否需要删除高位
    18.      * @param b    十进制
    19.      * @return 二进制
    20.      */
    21.     private static String bytesToBitString(boolean flag, byte b) {
    22.         int temp = b;
    23.         if (flag) {
    24.             temp |= 256;
    25.             String str = Integer.toBinaryString(temp);
    26.             return str.substring(str.length() - 8);
    27.         } else {
    28.             String str = Integer.toBinaryString(temp);
    29.             return str;
    30.         }
    31.     }
    32.  
    33.     /**
    34.      * 解压
    35.      *
    36.      * @param huffmanCodes 赫夫曼对应的编码表
    37.      * @param huffmanBytes 压缩赫夫曼码
    38.      * @return oldString
    39.      */
    40.     private static byte[] decode(Map huffmanCodes, byte[] huffmanBytes) {
    41.         // 1、转成101格式
    42.         StringBuilder stringBuilder1 = new StringBuilder();
    43.         for (int i = 0; i < huffmanBytes.length - 1; i++) {
    44.             stringBuilder1.append(bytesToBitString(true, huffmanBytes[i]));
    45.         } // 最后一个不需要补0
    46.         stringBuilder1.append(bytesToBitString(false, huffmanBytes[huffmanBytes.length - 1]));
    47.         // 2、对照赫夫曼编码表转成oldString
    48.         HashMap map = new HashMap<>(); // 反转map
    49.         for (Map.Entry entry : huffmanCodes.entrySet()) {
    50.             map.put(entry.getValue(), entry.getKey());
    51.         }
    52.         List list = new ArrayList<>();
    53.         for (int i = 0; i < stringBuilder1.length(); i++) {
    54.             int count = 1;
    55.             boolean flag = true;
    56.             Byte b = null;
    57.             while (flag) {
    58.                 String key = stringBuilder1.substring(i, i + count);
    59.                 b = map.get(key);
    60.                 if (b == null) { // 没有找到
    61.                     count++;
    62.                 } else {
    63.                     flag = false;
    64.                 }
    65.             }
    66.             list.add(b);
    67.             i += count - 1;
    68.         }
    69.         byte[] b = new byte[list.size()];
    70.         for (int i = 0; i < b.length; i++) {
    71.             b[i] = list.get(i);
    72.         }
    73.         return b;
    74.     }
    75.  
    76.     /**
    77.      * oldString to huffmanZip
    78.      *
    79.      * @param bytes 原始数组
    80.      * @return 压缩后的数组
    81.      */
    82.     private static byte[] huffmanZip(byte[] bytes) {
    83.         List nodes = getNodes(bytes); // 每个字符各出现了多少次 例如：105->9次
    84.         Node root = createHuffmanTree(nodes); // 生成赫夫曼树
    85.         Map huffmanCodes = getCodes(root); // 生成对应赫夫曼编码 例如：32->01
    86.         byte[] huffmanCodeBytes = zip(bytes, huffmanCodes); // 压缩 例如：-88,-65,-56
    87.         return huffmanCodeBytes;
    88.     }
    89.  
    90.     /**
    91.      * 压缩，将字符串对应的byte[]数组，转换成压缩后的byte[]
    92.      *
    93.      * @param bytes        原始的byte[]数组
    94.      * @param huffmanCodes 赫夫曼编码表
    95.      * @return 返回压缩后的byte[]数组
    96.      */
    97.     private static byte[] zip(byte[] bytes, Map huffmanCodes) {
    98.         StringBuilder stringBuilder1 = new StringBuilder();
    99.         for (byte b : bytes) {
    100.             stringBuilder1.append(huffmanCodes.get(b));
    101.         }
    102.         int len;
    103.         if (stringBuilder1.length() % 8 == 0) {
    104.             len = stringBuilder1.length() / 8;
    105.         } else {
    106.             len = stringBuilder1.length() / 8 + 1;
    107.         }
    108.         byte[] huffmanCodeBytes = new byte[len];
    109.         int index = 0; // 第几个byte
    110.         for (int i = 0; i < stringBuilder1.length(); i += 8) { // 每8位对应一个byte，所以步长是8
    111.             String strByte;
    112.             if (i + 8 < stringBuilder1.length()) {
    113.                 strByte = stringBuilder1.substring(i, i + 8);
    114.             } else { // 最末尾的
    115.                 strByte = stringBuilder1.substring(i);
    116.             }
    117.             huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
    118.             index++;
    119.         }
    120.         return huffmanCodeBytes;
    121.     }
    122.  
    123.     // 赫夫曼编码表Map 32(空格)->01
    124.     static Map huffmanCodes = new HashMap<>();
    125.     static StringBuilder stringBuilder = new StringBuilder();
    126.  
    127.     private static Map getCodes(Node root) {
    128.         if (root == null) {
    129.             return null;
    130.         }
    131.         getCodes(root.left, "0", stringBuilder); // 生成赫夫曼编码
    132.         getCodes(root.right, "1", stringBuilder); // 生成赫夫曼编码
    133.         return huffmanCodes;
    134.     }
    135.  
    136.     /**
    137.      * 将传入的node节点的所有叶子节点的赫夫曼编码得到，并放入到huffmanCodes集合
    138.      *
    139.      * @param node          根节点
    140.      * @param code          路径 左子节点0 右子节点1
    141.      * @param stringBuilder 用于拼接路径
    142.      */
    143.     private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    144.         StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    145.         stringBuilder2.append(code);
    146.         if (node != null) {
    147.             if (node.data == null) { // 非叶子节点，没有内容，只有权值
    148.                 getCodes(node.left, "0", stringBuilder2);
    149.                 getCodes(node.right, "1", stringBuilder2);
    150.             } else { // 叶子节点
    151.                 huffmanCodes.put(node.data, stringBuilder2.toString());
    152.             }
    153.         }
    154.     }
    155.  
    156.     private static void preOrder(Node root) {
    157.         if (root != null) {
    158.             root.preOrder();
    159.         } else {
    160.             System.out.println("赫夫曼树为空");
    161.         }
    162.     }
    163.  
    164.     private static List getNodes(byte[] bytes) {
    165.         ArrayList nodes = new ArrayList<>();
    166.         HashMap counts = new HashMap<>();
    167.         for (byte b : bytes) {
    168.             Integer count = counts.get(b);
    169.             if (count == null) {
    170.                 counts.put(b, 1);
    171.             } else {
    172.                 counts.put(b, count + 1);
    173.             }
    174.         }
    175.         for (Map.Entry entry : counts.entrySet()) {
    176.             nodes.add(new Node(entry.getKey(), entry.getValue()));
    177.         }
    178.         return nodes;
    179.     }
    180.  
    181.     private static Node createHuffmanTree(List nodes) {
    182.         while (nodes.size() > 1) {
    183.             Collections.sort(nodes);
    184.             Node leftNode = nodes.get(0);
    185.             Node righNode = nodes.get(1);
    186.             Node parentNode = new Node(null, leftNode.value + righNode.value);
    187.             parentNode.left = leftNode;
    188.             parentNode.right = righNode;
    189.             nodes.add(parentNode);
    190.             nodes.remove(leftNode);
    191.             nodes.remove(righNode);
    192.         }
    193.         return nodes.get(0);
    194.     }
    195. }
    196.  
    197. class Node implements Comparable {
    198.     Byte data;
    199.     int value; // 权值
    200.     Node left, right;
    201.  
    202.     public Node(Byte key, Integer value) {
    203.         this.data = key;
    204.         this.value = value;
    205.     }
    206.  
    207.     void preOrder() {
    208.  
    209.     }
    210.  
    211.     @Override
    212.     public int compareTo(Node node) {
    213.         return this.value - node.value;
    214.     }
    215.  
    216.     @Override
    217.     public String toString() {
    218.         return "Node{" +
    219.                 "data=" + data +
    220.                 ", value=" + value +
    221.                 '}';
    222.     }
    223. }

    如何用赫夫曼树压缩文件？

    1. import java.io.*;
    2. import java.util.*;
    3.  
    4. public class HuffmanCode2 {
    5.     public static void main(String[] args) {
    6.         String srcFile = "d:\\Users\\JJH\\Desktop\\1.jpg";
    7.         String descFile = "d:\\Users\\JJH\\Desktop\\download.zip";
    8.         // 1、文件的压缩，写入目标路径
    9.         zipFile(srcFile, descFile);
    10.  
    11.         String descFile2 = "d:\\Users\\JJH\\Desktop\\2.jpg";
    12.         // 2、文件的解压
    13.         unZipFile(descFile, descFile2);
    14.     }
    15.  
    16.     public static void unZipFile(String zipFile, String destFile) {
    17.         // 文件输入流
    18.         InputStream is = null;
    19.         // 对象输入流
    20.         ObjectInputStream ois = null;
    21.         // 文件输出流
    22.         OutputStream os = null;
    23.         try {
    24.             // 文件输入流
    25.             is = new FileInputStream(zipFile);
    26.             ois = new ObjectInputStream(is);
    27.             // 文件读取出来的二进制数
    28.             byte[] huffmanBytes = (byte[]) ois.readObject();
    29.             // 文件读取出来的赫夫曼编码表
    30.             Map huffmanCodes = (Map) ois.readObject();
    31.             // 定义文件输出流
    32.             os = new FileOutputStream(destFile);
    33.             // 1、解压
    34.             byte[] decode = decode(huffmanCodes, huffmanBytes);
    35.             // 2、写入文件
    36.             os.write(decode);
    37.         } catch (Exception e) {
    38.             throw new RuntimeException(e);
    39.         } finally {
    40.             try {
    41.                 if (ois != null) {
    42.                     ois.close();
    43.                 }
    44.                 if (os != null) {
    45.                     os.close();
    46.                 }
    47.                 if (is != null) {
    48.                     is.close();
    49.                 }
    50.             } catch (IOException e) {
    51.                 throw new RuntimeException(e);
    52.             }
    53.         }
    54.     }
    55.  
    56.     /**
    57.      * 解压
    58.      *
    59.      * @param huffmanCodes 赫夫曼对应的编码表
    60.      * @param huffmanBytes 压缩赫夫曼码
    61.      * @return oldString
    62.      */
    63.     private static byte[] decode(Map huffmanCodes, byte[] huffmanBytes) {
    64.         // 1、转成101格式
    65.         StringBuilder stringBuilder1 = new StringBuilder();
    66.         for (int i = 0; i < huffmanBytes.length - 1; i++) {
    67.             stringBuilder1.append(bytesToBitString(true, huffmanBytes[i]));
    68.         } // 最后一个需要补0，例如最后一个数是113的情况
    69.         stringBuilder1.append(bytesToBitString(false, huffmanBytes[huffmanBytes.length - 1]));
    70.         // 2、对照赫夫曼编码表转成oldString
    71.         HashMap map = new HashMap<>(); // 反转map
    72.         for (Map.Entry entry : huffmanCodes.entrySet()) {
    73.             map.put(entry.getValue(), entry.getKey());
    74.         }
    75.         List list = new ArrayList<>();
    76.         for (int i = 0; i < stringBuilder1.length(); ) {
    77.             int count = 1;
    78.             boolean flag = true;
    79.             Byte b = null;
    80.             while (flag) {
    81.                 String key = stringBuilder1.substring(i, i + count);
    82.                 b = map.get(key);
    83.                 if (b == null) { // 没有找到
    84.                     count++;
    85.                 } else {
    86.                     flag = false;
    87.                 }
    88.             }
    89.             list.add(b);
    90.             i += count;
    91.         }
    92.         byte[] b = new byte[list.size()];
    93.         for (int i = 0; i < b.length; i++) {
    94.             b[i] = list.get(i);
    95.         }
    96.         return b;
    97.     }
    98.  
    99.     /**
    100.      * 将byte转成二进制的字符串
    101.      *
    102.      * @param flag 是否需要删除高位
    103.      * @param b    十进制
    104.      * @return 二进制
    105.      */
    106.     private static String bytesToBitString(boolean flag, byte b) {
    107.         int temp = b;
    108.         if (flag) { // 不要补0的情况
    109.             /**
    110.              * 00001111 和
    111.              * 1111
    112.              */
    113.             temp |= 256;
    114.             String str = Integer.toBinaryString(temp);
    115.             return str.substring(str.length() - 8);
    116.         } else { // 要补零的情况
    117.             temp |= 256;
    118.             String str = Integer.toBinaryString(temp);
    119.             return str.substring(str.length() - 8);
    120.         }
    121.     }
    122.  
    123.     /**
    124.      * 文件的压缩
    125.      *
    126.      * @param srcFile  源路径
    127.      * @param destFile 目标路径
    128.      */
    129.     public static void zipFile(String srcFile, String destFile) {
    130.         FileInputStream is = null;
    131.         FileOutputStream os = null;
    132.         ObjectOutputStream oos = null;
    133.         try {
    134.             // 1、创建输入流
    135.             is = new FileInputStream(srcFile);
    136.             // 创建一个和源文件大小一样的byte[]
    137.             byte[] b = new byte[is.available()];
    138.             is.read(b);
    139.             byte[] huffmanZip = huffmanZip(b);
    140.             // 2、创建输出流
    141.             os = new FileOutputStream(destFile);
    142.             oos = new ObjectOutputStream(os); // 对象输出流
    143.             oos.writeObject(huffmanZip);
    144.             // 还要把赫夫曼编码写入压缩文件
    145.             oos.writeObject(huffmanCodes);
    146.         } catch (FileNotFoundException e) {
    147.             throw new RuntimeException(e);
    148.         } catch (IOException e) {
    149.             throw new RuntimeException(e);
    150.         } finally {
    151.             try {
    152.                 if (oos != null) {
    153.                     oos.close();
    154.                 }
    155.                 if (os != null) {
    156.                     os.close();
    157.                 }
    158.                 if (is != null) {
    159.                     is.close();
    160.                 }
    161.             } catch (IOException e) {
    162.                 throw new RuntimeException(e);
    163.             }
    164.         }
    165.     }
    166.  
    167.     /**
    168.      * oldString to huffmanZip
    169.      *
    170.      * @param bytes 原始数组
    171.      * @return 压缩后的数组
    172.      */
    173.     private static byte[] huffmanZip(byte[] bytes) {
    174.         List nodes = getNodes(bytes); // 每个字符各出现了多少次 例如：105->9次
    175.         Node root = createHuffmanTree(nodes); // 生成赫夫曼树
    176.         Map huffmanCodes = getCodes(root); // 生成对应赫夫曼编码 例如：32->01
    177.         byte[] huffmanCodeBytes = zip(bytes, huffmanCodes); // 压缩 例如：-88,-65,-56
    178.         return huffmanCodeBytes;
    179.     }
    180.  
    181.     private static List getNodes(byte[] bytes) {
    182.         ArrayList nodes = new ArrayList<>();
    183.         HashMap counts = new HashMap<>();
    184.         for (byte b : bytes) {
    185.             Integer count = counts.get(b);
    186.             if (count == null) {
    187.                 counts.put(b, 1);
    188.             } else {
    189.                 counts.put(b, count + 1);
    190.             }
    191.         }
    192.         for (Map.Entry entry : counts.entrySet()) {
    193.             nodes.add(new Node(entry.getKey(), entry.getValue()));
    194.         }
    195.         return nodes;
    196.     }
    197.  
    198.     private static Node createHuffmanTree(List nodes) {
    199.         while (nodes.size() > 1) {
    200.             Collections.sort(nodes);
    201.             Node leftNode = nodes.get(0);
    202.             Node righNode = nodes.get(1);
    203.             Node parentNode = new Node(null, leftNode.value + righNode.value);
    204.             parentNode.left = leftNode;
    205.             parentNode.right = righNode;
    206.             nodes.add(parentNode);
    207.             nodes.remove(leftNode);
    208.             nodes.remove(righNode);
    209.         }
    210.         return nodes.get(0);
    211.     }
    212.  
    213.     static StringBuilder stringBuilder = new StringBuilder();
    214.     static Map huffmanCodes = new HashMap<>();
    215.  
    216.     private static Map getCodes(Node root) {
    217.         if (root == null) {
    218.             return null;
    219.         }
    220.         getCodes(root.left, "0", stringBuilder); // 生成赫夫曼编码
    221.         getCodes(root.right, "1", stringBuilder); // 生成赫夫曼编码
    222.         return huffmanCodes;
    223.     }
    224.  
    225.     /**
    226.      * 将传入的node节点的所有叶子节点的赫夫曼编码得到，并放入到huffmanCodes集合
    227.      *
    228.      * @param node          根节点
    229.      * @param code          路径 左子节点0 右子节点1
    230.      * @param stringBuilder 用于拼接路径
    231.      */
    232.     private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    233.         StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    234.         stringBuilder2.append(code);
    235.         if (node != null) {
    236.             if (node.data == null) { // 非叶子节点，没有内容，只有权值
    237.                 getCodes(node.left, "0", stringBuilder2);
    238.                 getCodes(node.right, "1", stringBuilder2);
    239.             } else { // 叶子节点
    240.                 huffmanCodes.put(node.data, stringBuilder2.toString());
    241.             }
    242.         }
    243.     }
    244.  
    245.     /**
    246.      * 压缩，将字符串对应的byte[]数组，转换成压缩后的byte[]
    247.      *
    248.      * @param bytes        原始的byte[]数组
    249.      * @param huffmanCodes 赫夫曼编码表
    250.      * @return 返回压缩后的byte[]数组
    251.      */
    252.     private static byte[] zip(byte[] bytes, Map huffmanCodes) {
    253.         // 1001
    254.         StringBuilder stringBuilder1 = new StringBuilder();
    255.         for (byte b : bytes) {
    256.             stringBuilder1.append(huffmanCodes.get(b));
    257.         }
    258.         int len;
    259.         if (stringBuilder1.length() % 8 == 0) {
    260.             len = stringBuilder1.length() / 8;
    261.         } else {
    262.             len = stringBuilder1.length() / 8 + 1;
    263.         }
    264.         byte[] huffmanCodeBytes = new byte[len];
    265.         int index = 0; // 第几个byte
    266.         for (int i = 0; i < stringBuilder1.length(); i += 8) { // 每8位对应一个byte，所以步长是8
    267.             String strByte;
    268.             if (i + 8 < stringBuilder1.length()) {
    269.                 strByte = stringBuilder1.substring(i, i + 8);
    270.             } else { // 最末尾的
    271.                 strByte = stringBuilder1.substring(i);
    272.             }
    273.             huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
    274.             index++;
    275.         }
    276.         return huffmanCodeBytes;
    277.     }
    278. }

    二叉排序树

    1、左子节点小于当前节点，右子节点大于当前节点；

    2、尽量避免相同节点，相同节点可以放在左边或者右边；

    如果树不平衡怎么办？

    平衡二叉树就是对此的优化；

    平衡二叉树

    一棵树的左右两棵子树的高度差的绝对值不超过1；

    左旋转

    1、创建一个新节点newNode，值等于当前节点的值；

    2、把新节点的左子树设置为当前节点的左子树；

    3、把新节点的右子树设置为当前节点右子树的左子树；

    4、把当前节点(root)的值换为右子节点的值；

    5、把当前节点的右子树设置为右子树的右子树；

    6、把当前节点的左子树设置为新节点； 

    右旋转

    1、创建新节点，以当前根节点的值
    2、把新节点的右子节点设置为当前节点的右子节点
    3、把新节点的左子节点设置为当前节点的左子节点的右子节点
    4、把当前节点的值设置为左子节点的值
    5、当前节点左子节点设置位当前节点左子节点的左子节点
    6、当前节点的右子节点设置为新节点

    在添加新节点时旋转

    1. package org.example.tree.avl;
    2.  
    3. public class AVLTreeDemo {
    4.     public static void main(String[] args) {
    5. //        int[] arr = {4, 3, 6, 5, 7, 8};
    6. //        int[] arr = {10,11,7,6,8,9};
    7.         int[] arr = {2, 1, 6, 5, 7, 3};
    8.         AVLTree avlTree = new AVLTree();
    9.         for (int i = 0; i < arr.length; i++) {
    10.             avlTree.add(new Node(arr[i]));
    11.         }
    12.     }
    13. }
    14.  
    15. class AVLTree {
    16.     private Node root;
    17.  
    18.     public Node getRoot() {
    19.         return root;
    20.     }
    21.  
    22.     // 查找要删除的节点
    23.     public Node search(int val) {
    24.         if (root == null) {
    25.             return null;
    26.         } else {
    27.             return root.search(val);
    28.         }
    29.     }
    30.  
    31.     // 查找要删除的节点的父节点
    32.     public Node searchParent(int val) {
    33.         if (root == null) {
    34.             return null;
    35.         } else {
    36.             return root.searchParent(val);
    37.         }
    38.     }
    39.  
    40.     /**
    41.      * 1、删除叶子节点
    42.      * 2、删除有一棵子树的节点
    43.      * 左子节点还是右子节点？
    44.      * 3、删除有两课子树的节点
    45.      * 右子节点的最小左子节点
    46.      */
    47.     public void delNode(int val) {
    48.         if (root == null) {
    49.             return;
    50.         } else {
    51.             Node targetNode = search(val);
    52.             if (targetNode == null) {
    53.                 return; //没找到
    54.             }
    55.             if (root.left == null && root.right == null) {
    56.                 // 树只有一个节点
    57.                 root = null;
    58.                 return;
    59.             }
    60.             Node parent = searchParent(val);
    61.             // 1、删除叶子节点
    62.             if (targetNode.left == null && targetNode.right == null) {
    63.                 // 判断ta rgetNode是parent的左子节点还是父子节点
    64.                 if (parent.left != null && parent.left == targetNode) {
    65.                     // 删除的是左子节点
    66.                     parent.left = null;
    67.                 } else if (parent.right != null && parent.right == targetNode) {
    68.                     // 删除的是右子节点
    69.                     parent.right = null;
    70.                 }
    71.             } else if (targetNode.left != null && targetNode.right != null) {
    72.                 // 2、删除有两棵子节点的节点
    73.                 // 从target的右子节点找最小的节点
    74.                 int min = delRightTreeMin(targetNode.right);
    75.                 targetNode.val = min;
    76.             } else {
    77.                 // 3、删除只有一个子节点的节点
    78.                 if (targetNode.left != null) {
    79.                     // target只有左子节点
    80.                     if (parent != null) {
    81.                         if (parent.left.val == val) {
    82.                             // target是父节点的左子节点
    83.                             parent.left = targetNode.left;
    84.                         } else if (parent.right.val == val) {
    85.                             // target是父节点的右子节点
    86.                             parent.right = targetNode.left;
    87.                         }
    88.                     } else {
    89.                         // target是根节点
    90.                         root = targetNode.left;
    91.                     }
    92.                 } else {
    93.                     if (parent != null) {
    94.                         // target只有右子节点
    95.                         if (parent.left.val == val) {
    96.                             // target是父节点的左子节点
    97.                             parent.left = targetNode.right;
    98.                         } else {
    99.                             // target是父节点的右子节点
    100.                             parent.right = targetNode.right;
    101.                         }
    102.                     } else {
    103.                         // target是根节点
    104.                         root = targetNode.right;
    105.                     }
    106.  
    107.                 }
    108.             }
    109.         }
    110.     }
    111.  
    112.     // 删除右子节点的最左子节点并返回
    113.     public int delRightTreeMin(Node node) {
    114.         Node target = node;
    115.         while (target.left != null) {
    116.             target = target.left;
    117.         }
    118.         int val = target.val;
    119.         delNode(val);
    120.         return val;
    121.     }
    122.  
    123.     public void add(Node node) {
    124.         if (root == null) {
    125.             root = node;
    126.         } else {
    127.             root.add(node);
    128.         }
    129.     }
    130.  
    131.     /*public void infixOrder() {
    132.         if (root != null) {
    133.             root.infixOrder();
    134.         } else {
    135.             System.out.println("二叉排序树为空，不能遍历");
    136.         }
    137.     }*/
    138.  
    139. }
    140.  
    141. class Node {
    142.     int val;
    143.     Node left, right;
    144.  
    145.     public Node(int val) {
    146.         this.val = val;
    147.     }
    148.  
    149.     public int leftHeight() {
    150.         if (left == null) {
    151.             return 0;
    152.         }
    153.         return left.height();
    154.     }
    155.  
    156.     public int rightHeight() {
    157.         if (right == null) {
    158.             return 0;
    159.         }
    160.         return right.height();
    161.     }
    162.  
    163.     // 以该节点为根节点的树的高度
    164.     public int height() {
    165.         return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    166.     }
    167.  
    168.     // 查找要删除的节点
    169.     public Node search(int val) {
    170.         if (val == this.val) {
    171.             return this;
    172.         } else if (val < this.val) {
    173.             if (this.left == null) {
    174.                 return null; // 找不到
    175.             } else {
    176.                 return this.left.search(val);
    177.             }
    178.         } else {
    179.             if (this.right == null) {
    180.                 return null; // 找不到
    181.             } else {
    182.                 return this.right.search(val);
    183.             }
    184.         }
    185.     }
    186.  
    187.     // 查找要删除的节点的父节点
    188.     public Node searchParent(int val) {
    189.         // 如果当前节点是要删除的节点的父节点
    190.         if (this.left != null && this.left.val == val ||
    191.                 this.right != null && this.right.val == val) {
    192.             return this;
    193.         } else {
    194.             if (val < this.val && this.left != null) {
    195.                 return this.left.searchParent(val);
    196.             } else if (val > this.val && this.right != null) {
    197.                 return this.right.searchParent(val);
    198.             }
    199.             return null;
    200.         }
    201.     }
    202.  
    203.     public void add(Node node) {
    204.         if (node == null) {
    205.             return;
    206.         }
    207.         if (node.val < this.val) {
    208.             if (this.left == null) {
    209.                 this.left = node;
    210.             } else {
    211.                 this.left.add(node);
    212.             }
    213.         }
    214.         if (node.val > this.val) {
    215.             if (this.right == null) {
    216.                 this.right = node;
    217.             } else {
    218.                 this.right.add(node);
    219.             }
    220.         }
    221.         // 添加完节点后，是否需要旋转
    222.         if (rightHeight() - leftHeight() > 1) {
    223.             if (right != null && right.leftHeight() > right.rightHeight()) {
    224.                 // 左旋转
    225.                 right.rightRotate();
    226.             }
    227.             // 左旋转
    228.             leftRotate();
    229.             return;
    230.         }
    231.         if (leftHeight() - rightHeight() > 1) {
    232.             if (left != null && left.leftHeight() < left.rightHeight()) {
    233.                 // 左旋转
    234.                 left.leftRotate();
    235.             }
    236.             // 右旋转
    237.             rightRotate();
    238.         }
    239.     }
    240.  
    241.     private void leftRotate() {
    242.         // 创建新节点，以当前根节点的值
    243.         Node newNode = new Node(val);
    244.         // 把新节点的左子节点设置为当前节点的左子节点
    245.         newNode.left = left;
    246.         // 把新节点的右子节点设置为当前节点的右子节点的左子节点
    247.         newNode.right = right.left;
    248.         // 把当前节点的值设置为右子节点的值
    249.         val = right.val;
    250.         // 把当前节点的右子节点设置为当前节点的右子节点的右子节点
    251.         right = right.right;
    252.         // 把当前节点的左子节点设置为新节点
    253.         left = newNode;
    254.     }
    255.  
    256.     private void rightRotate() {
    257.         // 创建新节点，以当前根节点的值
    258.         Node newNode = new Node(val);
    259.         // 把新节点的右子节点设置为当前节点的右子节点
    260.         newNode.right = right;
    261.         // 把新节点的左子节点设置为当前节点的左子节点的右子节点
    262.         newNode.left = left.right;
    263.         // 把当前节点的值设置为左子节点的值
    264.         val = left.val;
    265.         // 把当前节点的左子节点设置为当前节点的左子节点的左子节点
    266.         left = left.left;
    267.         // 把当前节点的右子节点设置为新节点
    268.         right = newNode;
    269.     }
    270.  
    271.     /*public void infixOrder() {
    272.         if (this.left != null) {
    273.             this.left.infixOrder();
    274.         }
    275.         System.out.println(this);
    276.         if (this.right != null) {
    277.             this.right.infixOrder();
    278.         }
    279.     }*/
    280.  
    281.     @Override
    282.     public String toString() {
    283.         return "Node{" +
    284.                 "val=" + val +
    285.                 '}';
    286.     }
    287. }

    多叉树

    多叉树的存在是为了减少树的高度，以减少IO的次数；

    B树

    一个节点的大小通常是4K，这样每个节点只需要一次IO就可以完全载入；

    B树的阶：节点的最多子节点的个数，例如23树的阶就是3；

    文件系统和和数据库系统的设计者采用预读原理，将一个节点的大小设置为一个页(一个页通常是4K)，这样每个节点就只需要1次IO就可以完全载入；

    将树的度M设置为1024；

    2-3树

    2-3树是最简单的B树；

    2-3树的所有叶子节点都在同一层；

    三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点，二节点同理；

    2-3树是由二节点和三节点构成的树；

    2-3-4树

    B+树

    B+树和B树的区别：B+树的所有数据都放在叶子节点；

    B*树

    参考视频：【尚硅谷】数据结构与算法（Java数据结构与算法）_哔哩哔哩_bilibili

  • 相关阅读:
    NPDP考什么？难度大不大？
    如何在Python中实现安全的密码存储与验证
    C++_重载_指针_引用
    pytorch 保存和加载模型
    MySQL篇—事务和隔离级别介绍
    C++使用二维码识别库Zbar识别二维码图像
    【Android】ViewRootImpl、WindowManagerGlobal和WindowManager之间的关系
    ROS Bridge 笔记（01）— apt 安装、源码编译安装、安装依赖、运行显示
    硬件管理平台 - 公共项目搭建（Nancy部分）
    线性判别分析的多分类情况
  • 原文地址：https://blog.csdn.net/m0_58961367/article/details/133832293