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

构造哈夫曼树的算法_哈夫曼树的应用数据结构一、什么是赫夫曼树给定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)


相关推荐

  • oracle dba和sysdba的区别

    oracle dba和sysdba的区别之前老是把dba和sysdba混为一体,今天看到论坛在讨论两者的区别,特记录如下:SYSDBA不是权限,当用户以SYSDBA身份登陆数据库时,登陆用户都会变成SYS。sysdba身份登陆可以打开,

  • 图像质量评价方法PSNR+SSIM&&评估指标SROCC,PLCC

    图像质量评价方法PSNR+SSIM&&评估指标SROCC,PLCCupdate:2018-04-07今天发现ssim的计算里面有高斯模糊,为了快速计算,先对每个小块进行计算,然后计算所有块的平均值。可以参考源代码实现,而且代码实现有近似的在里面!matlab中中图

  • windbg调试dump文件_dump是什么文件夹

    windbg调试dump文件_dump是什么文件夹使用WinDbg分析Windowsdump文件

  • JVM的4种垃圾回收算法、垃圾回收机制与总结[通俗易懂]

    JVM的4种垃圾回收算法、垃圾回收机制与总结[通俗易懂]JVM的4种垃圾回收算法、垃圾回收机制与总结-知乎https://zhuanlan.zhihu.com/p/54851319JVM的4种垃圾回收算法、垃圾回收机制与总结一、垃圾回收算法1.标记清除标记-清除算法将垃圾回收分为两个阶段:标记阶段和清除阶段。在标记阶段首先通过根节点(GCRoots),标记所有从根节点开始的对象,未被标记的对象就是未被引用的垃圾对象。然后,在清除阶段,清除所有未被标记的对象。适用场合:…

    2022年10月10日
  • ssd硬盘数据怎么恢复_硬盘数据转移到另一个硬盘

    ssd硬盘数据怎么恢复_硬盘数据转移到另一个硬盘英特尔(Intel)SSD数据恢复概览现在,英特尔SSD是目前市面上最受欢迎的SSD硬盘之一,这都归功于它的几个优点。例如:快速的读取和写入速度、计算性能的增强、高级的加密标准(AES)等等。尽管有这些优秀的硬盘特性,还是无法避免在一切情境下资料丢失的问题。为什么硬盘中的资料会丢失?可能有以下几种原因:包括意外删除、格式化、病毒攻击、电源激增、操作系统崩溃或者说在一些情况下导致SSD不可独、初始化或坏掉。当意外发生之时,能否成功从IntelSSD硬盘中恢复数据?是的,当然可以!在你将新数据写入

  • 旁路由Openwrt设置

    旁路由Openwrt设置旁路由Openwrt设置完成!

发表回复

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

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