[java]-算法与数据结构-第十章-树结构

文章目录

十、树结构
- 1. 基础部分
- - 1）引出
  - 2）常用术语
  - - 树
- 2. 二叉树
- - 1）概念
  - 2）遍历
  - 3）查找
  - 4）删除
- 3. 顺序存储二叉树
- - 1）概念
  - 2）遍历
- 4. 线索化二叉树
- - 1）概念
  - 2）图解
  - 3）实现
  - 4）遍历
- 5. 堆排序
- - 1）概念
  - 2）思想
  - 3）图解
  - 4）代码
- 6. 赫夫曼树
- - 1）概念
  - 2）重要概念
  - 3）图解
  - 4）代码
- 7. 赫夫曼编码
- - 1）概念
  - 2）图解
  - 3）代码

十、树结构 1. 基础部分 1）引出

数组存储方式的分析
- 优点:通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
- 缺点:如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

链式存储方式的分析
- 优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。
- 缺点:在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)
  在这里插入图片描述
树存储方式的分析
能提高数据存储，读取的效率，比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

2）常用术语树

节点
根节点
父节点
组节点
叶子节点（没有子节点的节点）
节点的权（节点的值）
路径（从root 节点找到该节点的路线）
层
子树
树的高度（最大层数和）
森林：多棵子树构成森林

2. 二叉树 1）概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树
二叉树的子节点分为左节点和右节点。
如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1, n为层数，则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

2）遍历

说明：

前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，再输出父节点，再遍历右子树
后序遍历：先遍历左子树，再遍历右子树，最后输出父节点

小结:看输出父节点的顺序，就确定是前序，中序还是后序

遍历步骤：

创建二叉树
前序遍历
- 先输出当前节点(初始的时候是root节点)
- 如果左子节点不为空,则递归继续前序遍历
- 如果右子节点不为空，则递归继续前序遍历
中序遍历
- 如果当前节点的左子节点不为空,则递归中序遍历
- 输出当前节点
- 如果当前节点的右子节点不为空，则递归中序遍历
后序遍历
- 如果当前节点的左子节点不为空,则递归后序遍历
- 如果当前节点的右子节点不为空,则递归后序遍历
- 输出当前节点

代码：

public class 二叉树 {
    public static void main(String[] args) {

        BinaryTree binaryTree = new BinaryTree();
        HeroNode node1 = new HeroNode(1, "A");
        HeroNode node2 = new HeroNode(2, "B");
        HeroNode node3 = new HeroNode(3, "C");
        HeroNode node4 = new HeroNode(4, "D");
        HeroNode node5 = new HeroNode(5, "E");
        binaryTree.setRoot(node1);
        HeroNode root = binaryTree.getRoot();
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node5);
        node3.setRight(node4);
        System.out.println("---------前序遍历---------");
        binaryTree.preOrder();  // 1,2,3,4
        System.out.println("---------中序遍历---------");
        binaryTree.infixOrder(); // 2,1,3,4
        System.out.println("---------后序遍历---------");
        binaryTree.postOrder(); // 2,4,3,1

    }
}

BinaryTree

// 二叉树
class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public HeroNode getRoot() {
        return root;
    }

    // 前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

}

HeroNode

// node
class HeroNode {
    private int NO;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int NO, String name) {
        super();
        this.NO = NO;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "NO=" + NO +
                ", name='" + name + ''' +
                '}';
    }

    public int getNO() {
        return NO;
    }

    public void setNO(int NO) {
        this.NO = NO;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    // 前序遍历
    public void preOrder() {
        // 1. 先输出父节点
        System.out.println(this);
        // 2. 递归左子树
        if (this.left != null) {
            this.left.preOrder();
        }
        // 3. 递归右子树
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    // 中序遍历
    public void infixOrder() {
        // 1. 递归左子树
        if (this.left != null) {
            this.left.infixOrder();
        }
        // 2. 输出父节点
        System.out.println(this);
        // 3. 向右子树遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }


    // 后序遍历
    public void postOrder() {
        // 1. 递归左子树
        // 2. 向右子树遍历
        // 3. 输出父节点
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
}

3）查找

代码

    // 前序查找
    public HeroNode preSearch(int value) {
        // 1. 比较当前节点是不是
        if (this.getNO() == value) {
            return this;
        }
        // 2. 判断左节点
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preSearch(value);
        }
        if (resNode != null) {
            return resNode;
        }
        // 3. 判断右节点
        if (this.right != null) {
            resNode = this.right.preSearch(value);
        }
        return resNode;
    }

    // 中序查找
    public HeroNode infixSearch(int value) {

        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixSearch(value);
        }
        if (resNode != null) {
            return resNode;
        }
        // 2. 判断当前节点
        if (value == this.NO) {
            return this;
        }
        // 3. 向右
        if (this.right != null) {
            resNode = this.right.infixSearch(value);
        }
        return resNode;
    }

    // 后序查找
    public HeroNode postSearch(int value) {

        // 1. 向左遍历
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postSearch(value);
        }
        if (resNode != null) {
            return resNode;
        }
        // 2. 向右
        if (this.right != null) {
            resNode = this.right.postSearch(value);
        }
        if (resNode != null) {
            return resNode;
        }
        // 3. 判断当前节点
        if (value == this.NO) {

            return this;
        }
        return null;
    }

4）删除

要求

如果删除的节点是叶子节点，则删除该节点

如果删除的节点是非叶子节点，则删除该子树.

测试，删除掉5号叶子节点和3号子树.

HeroNode

    // 删除
    public void delete(int NO) {
        // 1. 左节点
        if (this.left != null && this.left.getNO() == NO) {
            this.left = null;
            return;
        }
        // 2. 右节点
        if (this.right != null && this.right.getNO() == NO) {
            this.right = null;
            return;
        }
        // 3. 递归删除
        if(this.left != null){
            this.left.delete(NO);
        }
        if(this.right != null){
            this.right.delete(NO);
        }

    }

BinaryTree

    // 删除
    public void delete(int no){
        if(this.root == null){
            System.out.println("此树为空");
            return;
        }else {
            if(this.root.getNO() == no){
                this.root = null;
            }else {
                this.root.delete(no);
            }
        }
    }

3. 顺序存储二叉树 1）概念

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组,看右面的示意图。
特点
- 顺序二叉树通常只考虑完全二叉树
- 第n个元素的左子节点为 2*n +1;
- 第n个元素的右子节点为 2*n +2;
- 第n个元素的父节点为（n-1）/2；

2）遍历

代码

public class 数组二叉树 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        arrayBinaryTree.preOrder();
    }
}

class ArrayBinaryTree {
    private int[] arr; // 存储数据节点的数组

    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }


    public void preOrder() {
        this.preOrder(0);
    }

    // 顺序存储
    // 前序  index 为数组下标
    public void preOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组二叉树为空");
            return;
        }
        // 输出当前元素
        System.out.println(arr[index]);
        // 向左递归
        if ((index * 2 + 1) < arr.length) {
            preOrder(2 * index + 1);
        }
        // 向右边递归
        if ((index * 2 + 2) < arr.length) {
            preOrder(2 * index + 2);
        }
    }
}

4. 线索化二叉树 1）概念

n个结点的二叉链表中含有n+1【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索")
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
一个结点的前一个结点，称为前驱结点
—个结点的后一个结点，称为后继结点

2）图解

说明:当线索化二叉树后，Node节点的属性left和righ，有如下情况:

left指向的是左子树，也可能是指向的前驱节点.比如节点 ileft指向的左子树,而⑩节点的 left指向的就是前驱节点.
right指向的是右子树，也可能是指向后继节点，比如①节点right指向的是右子树，而⑩节点的right指向的是后继节点.

3）实现

public class 线索二叉树 {
    public static void main(String[] args) {
        NewHeroNode node1 = new NewHeroNode(1, "A");
        NewHeroNode node2 = new NewHeroNode(3, "B");
        NewHeroNode node3 = new NewHeroNode(6, "C");
        NewHeroNode node4 = new NewHeroNode(8, "D");
        NewHeroNode node5 = new NewHeroNode(10, "E");
        NewHeroNode node6 = new NewHeroNode(14, "F");

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;

        ThreeNodes threeNodes = new ThreeNodes();
        threeNodes.setRoot(node1);

        System.out.println(node5.getLeft());
        System.out.println(node5.getRight() );
        node1.infixOrder();


    }

}

// 实现线索化二叉树
class NewHeroNode {

    public int NO;
    public String name;
    public NewHeroNode left;
    public NewHeroNode right;
    public int leftType;
    public int rightType;


    public NewHeroNode(int NO, String name) {
        super();
        this.NO = NO;
        this.name = name;
    }

    // 前序遍历
    public void preOrder() {
        // 1. 先输出父节点
        System.out.println(this);
        // 2. 递归左子树
        if (this.left != null) {
            this.left.preOrder();
        }
        // 3. 递归右子树
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    // 中序遍历
    public void infixOrder() {
        // 1. 递归左子树
        if (this.left != null) {
            this.left.infixOrder();
        }
        // 2. 输出父节点
        System.out.println(this);
        // 3. 向右子树遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    // 后序遍历
    public void postOrder() {
        // 1. 递归左子树
        // 2. 向右子树遍历
        // 3. 输出父节点
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    // 前序查找
    public NewHeroNode preSearch(int value) {
        // 1. 比较当前节点是不是
        if (this.getNO() == value) {
            return this;
        }
        // 2. 判断左节点
        NewHeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preSearch(value);
        }
        if (resNode != null) {
            return resNode;
        }
        // 3. 判断右节点
        if (this.right != null) {
            resNode = this.right.preSearch(value);
        }
        return resNode;
    }

    // 中序查找
    public NewHeroNode infixSearch(int value) {

        NewHeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixSearch(value);
        }
        if (resNode != null) {
            return resNode;
        }
        // 2. 判断当前节点
        if (value == this.NO) {
            return this;
        }
        // 3. 向右
        if (this.right != null) {
            resNode = this.right.infixSearch(value);
        }
        return resNode;
    }

    // 后序查找
    public NewHeroNode postSearch(int value) {

        // 1. 向左遍历
        NewHeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postSearch(value);
        }
        if (resNode != null) {
            return resNode;
        }
        // 2. 向右
        if (this.right != null) {
            resNode = this.right.postSearch(value);
        }
        if (resNode != null) {
            return resNode;
        }
        // 3. 判断当前节点
        if (value == this.NO) {

            return this;
        }
        return null;
    }

    // 删除
    public void delete(int NO) {
        // 1. 左节点
        if (this.left != null && this.left.getNO() == NO) {
            this.left = null;
            return;
        }
        // 2. 右节点
        if (this.right != null && this.right.getNO() == NO) {
            this.right = null;
            return;
        }
        // 3. 递归删除
        if (this.left != null) {
            this.left.delete(NO);
        }
        if (this.right != null) {
            this.right.delete(NO);
        }

    }
}

class ThreeNodes {
    public NewHeroNode pre = null;

    public NewHeroNode root = null;


    // node 为当前需要线索化的节点
    public void threadedNodes(NewHeroNode node) {
        if (node == null) {
            return;
        }
        // 1. 线索化左子树
        threadedNodes(node.getLeft());
        // 2. 线索化当前节点
        // 1) 先梳理当前节点的前驱节点
        if (node.getLeft() == null) {
            // 让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            // 修改当前节点的左指针的类型
            node.setLeftType(1);
        }
        // 2) 处理后置节点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        // 每次处理完一个节点，当前节点为下一个节点的前驱节点
        pre = node;

        // 3. 线索化右子树
        threadedNodes(node.getRight());
    }

    public NewHeroNode getRoot() {
        return root;
    }

    public void setRoot(NewHeroNode root) {
        this.root = root;
         threadedNodes(root);
    }
}

4）遍历

代码

 // 遍历
    public void threadList() {
        // 定义一个变量存储当前节点
        NewHeroNode node = root;
        while (node != null) {
            // 循环找到 leftType == 1 的结点,前驱节点
            // 当 leftType == 1 时，说明该节点是按照线索化处理后的有效节点
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            // 打印当前节点
            System.out.println(node);
            // 如果当前节点的右指针，指向的是后续节点，就一直输出
            while (node.getRightType() == 1){
                // 获取到当前节点的后续节点
                node = node.getRight();
                System.out.println(node);
            }
            // 替换遍历的节点
            node = node.getRight();

        }
    }

5. 堆排序 1）概念

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

对堆中的结点按层进行编号，映射到数组中就是下面这样
例如：arr[1] ≥ arr[2 * 1 + 1] && arr[1] ≥ arr[2 * 1 + 2] === 45 ≥ 20 && 45 ≥ 25

小堆顶举例

2）思想

将待排序序列构建成一个大顶堆
此时，整个序列的最大值就是堆顶的根节点
将其与末尾的元素进行交换，此时末尾就是最大值
将剩余的 n- 1个元素重新构造堆，重复上面步骤。

3）图解

构造初始堆，将给定无序序列构造成一个大顶堆，
此时从最后一个非叶子结点开始（叶子结点自然不用调整，第一个非叶子结点 arr.length/2 -1 = 5/2-1 = 1，也就是下面的6结点）从左到右，从上到下进行调整。
找到第三个非叶子结点4，由于9最大，1交换位置
继续调整

将顶对元素与末尾元素进行交换，使得末尾元素最大，然后继续调整，再将堆顶元素与末尾元素交换，得到第二大元素，如此反复循环。

4）代码

   public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);
    }

    // 堆排序的方法
    public static void heapSort(int arr[]) {
        

        // 1. 构建大 顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));
        // 2. 将堆顶元素与末尾元素进行交换, 将最大元素沉到数组末端
        int temp = 0;
        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));
    }

    // 讲一个数组调整成一个大顶堆
    // 功能：完成将 以 i 对应的非叶子节点的数调整成大顶堆
    // 举例：arr = {4,6,8,5,9} i = 1,length = 5

    // arr 待调整的数组
    // i 非叶子结点在数组中的索引
    // length 对多少个元素进行调整
    public static void adjustHeap(int arr[], int i, int length) {
        int temp = arr[i]; // 取出当前元素 -->非叶子元素
        // 1. 开始调整
        // 左子节点， k 是 i的 左子节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            // k+1 > length 不比了
            if (k + 1 < length && arr[k] < arr[k + 1]) { // 说明 左子节点 < 右子节点
                k++; // k指向 右子节点

            }
            // k此时为左结点 或者 右结点
            if (arr[k] > temp) { // 子节点 > 父节点
                arr[i] = arr[k]; // 父节点 变为 子节点
                i = k; // 非叶子结点 继续循环
            } else break;
        }
        // for循环结束后, 已经将 以 i为父节点的数的最大值，放在了最前面。
        arr[i] = temp;


    }

6. 赫夫曼树 1）概念

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

2）重要概念

路径和路径长度：

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。

通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
结点的权及带权路径长度：

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

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

例如：2 * 13 = 26；
树的带权路径长度：

树的带权路径长度规定为所有叶子节点的带权路径长度之和，记为 WPL(weighted path length),权值越大的结点离根节点越近的二叉树才是最优二叉树。
WPL最小的就是赫夫曼树

3）图解

从小到大进行排序，将每一个数据，每个数据都是节点，每个节点可以看成最简单的二叉树
取出根节点权值最小的两颗二叉树
组成一颗新的二叉树，该新的二叉树的根节点的权值是前面两颗二叉树的根节点权值的和
再将这颗新的二叉树，以根节点的权值大小再次匹配，不断重复.

4）代码

代码

public class 赫夫曼树 {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node root = createHeffmanTree(arr);
        preNode(root);
    }

    // 创建赫夫曼树
    public static Node createHeffmanTree(int[] arr) {
        // 1. 遍历 arr 数组
        // 2. 将每一个构建成node
        // 3. 将每一个放入 arrayList中
        ArrayList nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        // 4. 排序 小 --> 大
        // 循环处理
        while (nodes.size() > 1) {
            Collections.sort(nodes);

            // 5. 取出权值最小的两个二叉树
            Node left = nodes.get(0);
            Node right = nodes.get(1);

            // 6. 构建新的二叉树
            Node parent = new Node(left.value + right.value);
            parent.left = left;
            parent.right = right;

            // 7. 从 arrayList中删除处理过的二叉树
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);
            System.out.println(nodes);
        }
        return nodes.get(0);
    }

    // 前序遍历
    public static void preNode(Node root){
        if(root == null){
            System.out.println("值为空");
        }else {
            root.preOrder();
        }
    }
}
// 创建节点类


class Node implements Comparable {
    int value; // 权
    Node left;  // 左子节点
    Node right; // 右子节点

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

    // 前序遍历
    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if(this.right != null){
            this.right.preOrder();
        }
    }

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

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }
}

7. 赫夫曼编码 1）概念

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

2）图解

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DSRiQoz7-1651491300720)(https://secure2.wostatic.cn/static/i92Yt13Bex8adYwZJEP5mb/image.png)]
根据赫夫曼树，给各个字符规定编码，向左的路径为 0，向右的路径为1。

o:1000 u: 10010 d:100110 y: 100111 a : 110 k:1110 e: 1111 j:0000 v:0001 l:001 :01
按照上面的赫夫曼编码，我们的i like like like java do you like a java字符串对应的编码为(注意这里我们使用的无损压缩)
101``01``001101111011110100110111101111010011011110111101000010000110011001111000011001111000100100100110111011011100100001100001110
长度为：133

原来长度为 359，压缩了 62.9%

此编码满足前缀编码，即字符的编码不能是其他字符编码的前缀，不会造成匹配的多义性，赫夫曼编码是无损的处理方式。
注意：

这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼树编码也不一样，但是WPL是一样的，生成的长度都是一样的，都是最小的，

3）代码

Node类

class Node2 implements Comparable {
    Byte data;
    int weight;
    Node2 left;
    Node2 right;

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

    // 前序遍历
    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(Node2 o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node2{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
}

创建节点

private static List getNodes(byte[] bytes) {
        // 1. 创建一个 ArrayList
        ArrayList nodes = new ArrayList<>();
        // 2. 存储灭一个byte出现的次数
        HashMap map = new HashMap<>();
        for (byte by : bytes) {
            //说明map中没有这个字符，我们将其加入到map中
            //说明这个字符已经存在，我们让其进行总数加1
            map.merge(by, 1, Integer::sum);
        }
        System.out.println(map);

        for (Map.Entry entry : map.entrySet()) {
            nodes.add(new Node2(entry.getKey(), entry.getValue()));
        }
        return nodes;

    }

创建赫夫曼树

public static Node2 createHeffmanTree(List nodes) {

        // 4. 排序 小 --> 大
        // 循环处理
        while (nodes.size() > 1) {
            Collections.sort(nodes);

            // 5. 取出权值最小的两个二叉树
            Node2 left = nodes.get(0);
            Node2 right = nodes.get(1);

            // 6. 构建新的二叉树
            Node2 parent = new Node2(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;

            // 7. 从 arrayList中删除处理过的二叉树
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);

        }
        return nodes.get(0);
    }

创建赫夫曼编码

    public static Map getCodes(Node2 node2) {
        getCodes(node2, "", stringBuilder);
        return huffmanCodes;
    }

    private static void getCodes(Node2 node, String code, StringBuilder stringBuilder) {
        StringBuilder st = new StringBuilder(stringBuilder);
        //将code加入st
        st.append(code);
        if (node != null) {
            if (node.data == null) {//非叶子节点,叶子节点的data域是存在值的
                //递归处理
                //向左递归
                getCodes(node.left, "0", st);
                //向右递归
                getCodes(node.right, "1", st);
            } else {
                //说明找到一个叶子节点
                //就表示找到某个叶子节点的最后
                huffmanCodes.put(node.data, st.toString());
            }
        }
    }

解析赫夫曼编码，压缩

private static byte[] zip(byte[] bytes, Map huffmanCodes) {
        // 1. 将 bytes 转成 heffman编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        // 2. 遍历 bytes 数组
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        int len = (stringBuilder.length() + 7) / 8;
        // 创建存储压缩后的byte数组
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < stringBuilder.length(); i += 8) { // 8位对应一个 byte
            String strByte;
            if (i + 8 > stringBuilder.length()) {
                // 不够 8 位
                strByte = stringBuilder.substring(i);
            } else strByte = stringBuilder.substring(i, i + 8);
            // 将 strByte 转成 一个byte,放入
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }

解压数据

  private static byte[] deCode(Map huffmanCodes, byte[] huffmanCodesBytes) {
        // 1. 将 huffmanCodesBytes  [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
        //    重新转成字符串（huffman编码对应的二进制字符串）
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanCodesBytes.length; i++) {
            // 判断是不是最后一个字节
            boolean flag = (i == huffmanCodesBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, huffmanCodesBytes[i]));
        }
        // 3. 把字符串按照指定的赫夫曼编码进行解码
        HashMap map = new HashMap<>();
        for (Map.Entry entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        // 4. 存放 byte
        ArrayList list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag) {
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b != null) {
                    flag = false;

                } else {
                    count++;
                }
            }
            list.add(b);
            i += count;
        }
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < list.size(); i++) {
            bytes[i] = list.get(i);
        }
        return bytes;

    }

压缩文件

private static void zipFile(String srcFile, String dstFile) throws IOException {
        FileInputStream inputStream = new FileInputStream(srcFile);
        byte[] bytes = new byte[inputStream.available()];
        // 读取文件
        inputStream.read(bytes);
        // 压缩完成
        byte[] huffmanZipBytes = huffmanZip(bytes);
        // 输出文件,存放压缩文件
        OutputStream outputStream = new FileOutputStream(dstFile);
        ObjectOutputStream oos = new ObjectOutputStream(outputStream);
        // 写入压缩数组
        oos.writeObject(huffmanZipBytes);
        // 写入赫夫曼编码
        oos.writeObject(huffmanCodes);
        // 写入完毕
        inputStream.close();
        oos.close();
        outputStream.close();
    }

解压文件

private static void unzipFile(String zipFile, String dstFile) throws IOException, ClassNotFoundException {
        FileInputStream inputStream = new FileInputStream(zipFile);
        ObjectInputStream ooin = new ObjectInputStream(inputStream);
        byte[] bytes;
        // 读取文件
        bytes = (byte[]) ooin.readObject();
        Map huffmanCodes = (Map) ooin.readObject();
        // 解压
        byte[] deCode = deCode(huffmanCodes, bytes);
        // 输出文件,存放压缩文件
        OutputStream outputStream = new FileOutputStream(dstFile);
        // 写入压缩数组
        outputStream.write(deCode);
        // 写入完毕
        ooin.close();
        inputStream.close();
        outputStream.close();
    }

公共方法

    // 5. 将前面的方法封装起来,便于我们的调用
    private static byte[] huffmanZip(byte[] bytes) {
        // 1. 合并
        List nodes = getNodes(bytes);
        // 2. 生成赫夫曼树
        Node2 root = createHeffmanTree(nodes);
        // 3. 生成赫夫曼编码
        Map codes = getCodes(root);
        // 4. 生成赫夫曼编码处理后的数据
        byte[] zipBytes = zip(bytes, huffmanCodes);
        return zipBytes;
    }
    
        // 将 byte 转成二进制的字符串
    private static String byteToBitString(boolean flag, byte b) {
        int temp = b;
        // 如果是正数，还存在补高位的问题
        if (flag) { // 标识是否需要高位
            temp |= 256; // temp 1 --> 000;
        }

        String string = Integer.toBinaryString(temp); // 返回的是 temp 对应的二进制的补码
        if (flag) {
            return string.substring(string.length() - 8);
        } else {
            return string;
        }

    }

    // 前缀遍历
    public static void preOrder(Node2 root) {
        root.preOrder();
    }

[java]-算法与数据结构-第十章-树结构

Java相关栏目本月热门文章