首页 > 其他分享 >赫夫曼树HuffmanTree

赫夫曼树HuffmanTree

时间:2023-05-11 14:24:05浏览次数:37  
标签:List public HuffmanNode 二叉树 HuffmanTree root 节点 夫曼

赫夫曼树HuffmanTree

1. 基本概念

  • 路径:在树中,从一个节点到另外一个节点之间的分支构成这两个节点之间的路径;
  • 路径长度:路径上的分支数称为路径长度;
    • 若规定根节点的层数为1,则从根节点到第L层节点的路径长度为L - 1;
  • 节点的权:对树中的节点赋一个具有某种含义的数值,则该数值称为该节点的权;
  • 节点的带权路径长度:从根节点到该节点之间的路径长度与该节点的权的乘积(根节点到该节点路径长度l × 该节点权值w);
  • 树的带权路径长度(WPL)所有叶子节点带权路径长度之和,记为WPL(Weighted Path Length);
  • WPL最小的二叉树就是Huffman Tree。因此权值越大的节点离根节点越近的二叉树才是最优二叉树
哈夫曼树.png

2. Huffman Tree基本介绍

  • 给定n个权值作为n个叶子节点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最短,则称这样的树为最优二叉树,也即哈夫曼树/赫夫曼树(Huffman Tree);
  • Huffman Tree是带权路径长度最短的树,也即权值较大的节点应离根节点较近

3. 构建Huffman Tree思路分析

  • 给定一个数列{13,7,8,3,29,6,1},构建成赫夫曼树
  • 将数列中的每个元素构建成Node节点,并将所有Node放入List中
  • 开始循环重复下面步骤,直至List中只剩下一个元素,即只剩下赫夫曼树的root节点
    • 对List从小到大排序,将List中的每一个节点都看作是一棵最简单的二叉树
    • 取出根节点权值最小的两棵二叉树(也即权值最小的两个节点
    • 组成一棵新的二叉树,新的二叉树的根节点的权值前面两棵二叉树根节点权值之和
    • List中删除已经处理过的节点,并将新的二叉树的根节点权值加入List
  • 返回List中唯一剩余的节点,即Huffman Tree的root节点,得到一棵Huffman Tree
赫夫曼树创建过程.png

4. 代码实现

package com.datastructure;

import java.util.*;

/**
 * @author SnkrGao
 * @create 2023-05-11 12:33
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};

        HuffmanNode root = createHuffmanTree(arr);

        List<Integer> resList = new ArrayList<>();
        List<List<Integer>> resList2 = new ArrayList<>();
        System.out.println("前序遍历:");
        resList = preorderTraversal(root,resList);
        System.out.println(resList);

        System.out.println("层序遍历:");
        resList2 = levelorderTraversal(root);
        System.out.println(resList2);

    }

    /**
     * 构建哈夫曼树
     * @param arr 用于构建哈夫曼树的数组
     * @return 返回创建好的Huffman Tree的root节点
     */
    public static HuffmanNode createHuffmanTree(int[] arr) {
        // 遍历arr数组,对arr的每一个元素构建成节点并放入List中
        List<HuffmanNode> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new HuffmanNode(value));
        }

        while (nodes.size() > 1) {
            // 对List排序
            Collections.sort(nodes);

            // 取出根节点权值最小的两个节点
            HuffmanNode leftNode = nodes.get(0);
            HuffmanNode rightNode = nodes.get(1);

            // 构建一棵新的二叉树
            HuffmanNode parent = new HuffmanNode(leftNode.getNo() + rightNode.getNo());
            parent.setLeft(leftNode);
            parent.setRight(rightNode);

            // 从List中删除处理过的两个节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 将新构建的二叉树的根节点parent放入List
            nodes.add(parent);
        }

        // 返回Huffman Tree的root节点
        return nodes.get(0);
    }

    public static List<Integer> preorderTraversal(HuffmanNode root, List<Integer> list) {
        if (root == null) {
            System.out.println("哈夫曼树为空!");
            return new ArrayList<>();
        }
        list.add(root.getNo());
        if (root.getLeft() != null) {
            list = preorderTraversal(root.getLeft(), list);
        }
        if (root.getRight() != null) {
            list = preorderTraversal(root.getRight(), list);
        }
        return list;
    }

    public static List<List<Integer>> levelorderTraversal(HuffmanNode root) {
        if (root == null) {
            System.out.println("哈夫曼树为空!");
            return new ArrayList<>();
        }

        List<List<Integer>> resList = new ArrayList<>();
        Queue<HuffmanNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            List<Integer> levelList = new ArrayList<>();

            for (int i = 0; i < queueSize; i++) {
                HuffmanNode tmpNode = queue.poll();
                levelList.add(tmpNode.getNo());
                if (tmpNode.getLeft() != null) {
                    queue.offer(tmpNode.getLeft());
                }
                if (tmpNode.getRight() != null) {
                    queue.offer(tmpNode.getRight());
                }
            }
            resList.add(levelList);
        }

        return resList;
    }
}

/**
 * 为了让HuffmanNode节点对象支持Collections集合排序
 * 让HuffmanNode实现Comparable接口
 */
class HuffmanNode implements Comparable<HuffmanNode>{
    private int no;
    private HuffmanNode left;
    private HuffmanNode right;

    public HuffmanNode(int no) {
        this.no = no;
    }

    // 重写compareTo方法
    @Override
    public int compareTo(HuffmanNode o) {
        // 排序规则:表示从小到大排序
        return this.no - o.no;
    }

    @Override
    public String toString() {
        return "HuffmanNode{" +
                "no=" + no +
                '}';
    }

    public int getNo() {
        return no;
    }

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

    public HuffmanNode getLeft() {
        return left;
    }

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

    public HuffmanNode getRight() {
        return right;
    }
}

5. 补充知识

在java中,ComparableComparator都是用来进行元素排序的,但二者有着本质上的区别:

  • 用法不同

    • Comparable接口只有一个compareTo方法,实现Comparable接口并重写compareTo方法,就可以实现某个类的排序,其支持Collections.sort和Arrays.sort

      • compareTo方法仅接受一个参数,即要比较的对象。排序规则是用当前对象与要比较的对象进行比较,并返回一个int类型的值。从小到大排序的规则是:当前对象值 - 要比较对象值;从大到小排序的规则是:要比较对象值 - 当前对象值。
      Comparable_compareTo.png
      • 注意:如果自定义对象没有实现Comparable接口,则不能使用Collections.sort方法进行排序
    • Comparator的排序方法是compare,compare方法接收两个参数,排序规则与compareTo类似。

      Comparator_compare.png
      • Comparator除了可以通过创建自定义比较器外,还可以通过匿名内部类的方式,更快速、便捷地完成自定义比较器的功能。
      Comparator_compare匿名内部类.png
  • 运用场景不同

    • 使用Comparable必须要修改原有的类,在该类中实现Comparable接口并重写compareTo方法,因此Comparable更像是“对内”进行排序的接口
    • Comparator的使用则不同,无需修改原有的类。即使是对第三方提供的类,仍然可以通过创建新的自定义比较器Comparator实现对其的排序功能。也即通过Comparator接口可以实现和原有类的解耦,所以Comparator可以看作是“对外”提供排序的接口

标签:List,public,HuffmanNode,二叉树,HuffmanTree,root,节点,夫曼
From: https://www.cnblogs.com/SnkrGao/p/17390874.html

相关文章

  • C/C++交通咨询系统设计哈夫曼编码问题[2023-05-11]
    C/C++交通咨询系统设计哈夫曼编码问题[2023-05-11]题目三、交通咨询系统设计最短路径问题设计要求及分析:设计一个交通咨询系统,能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费、最少时间等问题。对于不同咨询要求,可输出城市间的路程、所需时间......
  • 数据结构之哈夫曼树与哈夫曼编码
    一、背景编码是信息处理的基础(重新表示信息)。普通的编码是等长编码,例如7位的ASCIL编码,对出现频率不同的字符都使用相同的编码长度。但其在传输和存储等情况下编码效率不高。可使用不等长编码,来压缩编码:高频字符编码长度更短,低频字符编码长度更长。 [例]将百分制的考试成......
  • 4月12日数据结构,线索二叉树,哈夫曼树,哈夫曼编码
    线索二叉树与以往的二叉树略有不同,普通二叉树在访问到叶子结点的时候会返回,往往递归的效率并不高,有时还可能有栈溢出的风险,但是线索二叉树在访问到叶子结点的时候因为没有左右孩子,所以他左边存放他前驱的指针。右边存放后继的指针,是指从一个非线性结构变成了一个可以线性访问的的......
  • 哈夫曼编码
    基本术语:路径和路径长度:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点    到第L层结点的路径长度为L-1。结点的权及带权路径长度:若将树......
  • 霍夫曼编码详解
    本专栏包含信息论与编码的核心知识,按知识点组织,可作为教学或学习的参考。markdown版本已归档至【Github仓库:​​information-theory​​】,需要的朋友们自取。或者公众号【AI......
  • 哈夫曼树的构造
       1哈夫曼树的概念在许多应用中经常将树中的节点赋予一个权值,从根节点到该节点之间的路径长度与该节点上的权值的乘积称为该节点的带权路径长度(WPL),树中所有叶子节......
  • 哈夫曼树
    1.定义1.1哈夫曼树哈夫曼树是一种最基本的压缩编码方法。对于如图所示的两棵二叉树,每个叶子节点都带有权值:从树中一个结点到另一个结点之间的分支构成两个结点之间的......
  • 6.5用二叉树实现哈夫曼编码
       莫尔斯编码是根据日常文本中各字符出现频率决定表示各字符的编码的数据长度。不过,该编码体系,对AAAAAABBCDDEEEEEEF这样的特殊文并不是最合适的。在莫尔斯编码中,E......
  • 6.4通过莫尔斯编码来看哈夫曼算法的基础
       哈夫曼算法是哈夫曼(D.A.Huffman)于1952年提出来的压缩算法。日本人比较常用的压缩软件LHA,使用的就是哈夫曼算法。   文本文件是由不同类型的字符组合而成的......
  • 6.6 夫曼算法能够大幅提升压缩比率
    通过图6-5的步骤2可以发现,在用枝条连接数据时,我们是从出现频率较低的数据开始的,这就意味着出现频率越低的数据到达根部的枝条数就越多。而枝条数越多,编码的位数也就随之增......