构造哈夫曼树的算法_哈夫曼树的应用数据结构

构造哈夫曼树的算法_哈夫曼树的应用数据结构一、什么是赫夫曼树给定n个权值作为n个叶子节点,构造一课二叉树,若该树的带权路径长度和(wpl)达到最小,称这样的二叉树为最优二叉树,也就是赫夫曼树。要理解这句话,我们需要了解几个关键词:路径:

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、什么是赫夫曼树

给定n个权值作为n个叶子节点,构造一课二叉树,若该树的带权路径长度和(wpl)达到最小,称这样的二叉树为最优二叉树,也就是赫夫曼树

要理解这句话,我们需要了解几个关键词:

  • 路径:从一个节点往下一个节点之间的通路。若根节点层数为1,则根节点通往L层的节点路径长度为L-1
  • 带权路径:权可以理解为节点值,而从根节点到某节点之间的路径长度与该点的权的成绩称为带权路径长度

举个例子:

image-20200717165237484

如上图所示,节点13到根节点的路径长度是2,而权是13,所以带权路径长度就是2*13=26,同理,节点7的带权路径长度是14,8是16,3是6,最终该树的带权路径长度之和(wpl)就是26+14+16+6=62。

image-20200717165733984

而该树与上图有相同的叶子节点,但是wpl却是13+16+21+9=59,这是拥有这几个相同叶子节点的树里面wpl最小的,所以这颗树就是一颗赫夫曼树。

我们不难看出,赫夫曼树最大的特点:权越大的节点越靠近根节点

二、如何构建赫夫曼树

举个例子,我们要将{6,1,3,7,13,8,29}这一串数列组建为赫夫曼树

  1. 首先,我们对齐从小到大排序,得到{1,3,6,7,8,13,29}

  2. 取出1和3,并以两节点之和4为根节点组建树

    image-20200717172110379

  3. 取出6,并与4之和10为根节点构建树

    image-20200717172201798

  4. 取出7,并与10之和17为根节点构建树

    image-20200717172314477

  5. 重复以上步骤最终得到赫夫曼树

image-20200717172440901

三、代码实现

首先先写一个节点类:

/**
 * @Author:CreateSequence
 * @Date:2020-07-17 17:31
 * @Description:赫夫曼树使用的节点
 */
public class Node implements Comparable<Node> {

    int val;
    Node left;
    Node right;

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

    /**
     * 父节点的构造方法
     * @param left
     * @param right
     */
    public Node(Node left, Node right) {
        this.left = left;
        this.right = right;
        this.val = left.val + right.val;
    }

    @Override
    public String toString() {
        return "val=" + val;
    }

    /**
     * 实现排序接口,从大到小
     * @param o
     * @return
     */
    @Override
    public int compareTo(Node o) {
        return -(this.val - o.val);
    }
}

实现一个构造赫夫曼树的方法:

/**
 * @Author:CreateSequence
 * @Date:2020-07-17 17:37
 * @Description:赫夫曼树
 */
public class HuffmanTree {
    /**
     * 创建赫夫曼树
     * @param arr
     */
    public static List<Node> createHuffmanTree(int[] arr){
        //将数组元素拆分成节点
        List<Node> nodes = new ArrayList<>();
        for (int i : arr) {
            nodes.add(new Node(i));
        }

        //构建树
        while (nodes.size() > 1) {
            //排序
            Collections.sort(nodes);

            //取出最小的两个数构建树
            Node left = nodes.get(nodes.size() - 1);
            Node right = nodes.get(nodes.size() - 2);
            Node parant = new Node(left, right);

            //删除两个节点
            nodes.remove(left);
            nodes.remove(right);

            //将根节点添加至集合
            nodes.add(parant);
        }

        return nodes;
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170804.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • java之Scanner详解「建议收藏」

    java之Scanner详解「建议收藏」1.包:importjava.util.Scanner2.使用方法:Scannerreader=newScanner(System.in);  然后reader对象调用下列方法(函数),读取用户在命令行输入的各种数据类型:   nextByte(),nextDouble(),nextFloat,nextInt(),nextLine(),nextLong(),next

  • vim设置(非常全面),即.vimrc文件的配置

    vim设置(非常全面),即.vimrc文件的配置1.在终端下使用vim进行编辑时,默认情况下,编辑的界面上是没有显示行号、语法高亮度显示、智能缩进等功能的。为了更好的在vim下进行工作,需要手动设置一个配置文件:.vimrc。在启动vim时,当前用户根目录下的.vimrc文件会被自动读取,该文件可以包含一些设置甚至脚本,所以,一般情况下把.vimrc文件创建在当前用户的根目录下比较方便,即创建的命令为:$vi~/.vimrc

  • android 倒计时控件_安卓倒计时

    android 倒计时控件_安卓倒计时CountDownTimer构造函数:CountDownTimer(longmillisInFuture,longcountDownInterval)millisInfuture:要倒计时的总时间,单位ms。countDownInterval:要倒计时的间隔时间,单位ms。CountDownTimer是个抽象类,在实际运用中我们会去构造一个匿名实现类对象来进行处理…

  • 单隐层前馈神经网络网络构造_前馈型神经网络常用于

    单隐层前馈神经网络网络构造_前馈型神经网络常用于这篇博客主要介绍神经网络基础,单隐层前馈神经网络与反向传播算法。神经网络故名思议是由人的神经系统启发而得来的一种模型。神经网络可以用来做分类和回归等任务,其具有很好的非线性拟合能力。接下来我们就来详细介绍一下但隐层前馈神经网络。首先我们来看一下神经元的数学模型,如下图所示:可以看到为输入信号,而神经元最终输出为,由此我们可以看到,单个神经元是多输入单输出的。但是从上图我们可以看到,…

    2022年10月30日
  • 常用sql语句整理:mysql

    常用sql语句整理:mysql

    2021年10月10日
  • Nacos整合SpringCloud(配置中心、注册中心)[通俗易懂]

    Nacos整合SpringCloud(配置中心、注册中心)[通俗易懂]1.什么是Nacos?Nacos是阿里巴巴开源的一个更易于构建云原生应用的动态服务发现、配置管理和服务管理平台。2.Nacos配置中心整合2.1启动NacosServer并添加配置1.下载地址:直接下载:NacosServer下载页源码构建:Github项目页面2.启动Linux/Unix/Mac操作系统,执行命令shstartup.sh-ms…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号