哈夫曼树

简介: 哈夫曼树也称最优二叉树,含有n个带权叶子结点带权路径长度最小的二叉树。

java实现哈夫曼树


哈夫曼树:

给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。


哈夫曼树基本术语解释

1、路径和路径长度
在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。 记为WPL=(W1 L1+W2L2+W3 L3+...+WnLn)
3、树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为 WPL



java代码实现:

//哈夫曼树     二叉树的应用
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};

        Node node = huffmanTree(arr);
        preOrderNode(node);

    }

    /**
     * 把数组转化成哈夫曼树
     *
     * @param arr 带转化的数组
     */
    public static Node huffmanTree(int[] arr) {
        //首先把数组中的各个元素 存入到Node类的value中
        List<Node> nodes = new ArrayList<Node>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }

        while (nodes.size() > 1) {

            //根据value的大小进行排序,因为Node类已经继承了Compareable所以可以直接全部排序
            Collections.sort(nodes);

            //挑选集合中的前两个树开始组成哈夫曼树

            //获取二叉树最小的结点
            Node reftNode = nodes.get(0);
            //获取二叉树第二小的结点
            Node rightNode = nodes.get(1);
            Node parent = new Node(reftNode.value + rightNode.value);
            parent.reft = reftNode;
            parent.right = rightNode;
            nodes.remove(reftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    //前序遍历的方法   需要传入根节点
    public static void preOrderNode(Node root) {
        if (root == null) {
            System.out.println("为空遍历失败~");
            return;
        } else {
            root.preOrderNode();
        }
    }


}


class Node implements Comparable<Node> {
    int value;
    Node reft;
    Node right;

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

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

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

    @Override
    public int compareTo(Node node) {
        //这个排完序是 从小到大。   -(this.value-node.value)这样子排完序后是从大到小。
        return this.value - node.value;
    }
}
目录
相关文章
|
NoSQL Devops 程序员
devops| redis 数据量暴涨进行数据清理实战
redis 作为程序员的 「瑞士军刀」, 在现有业务中扮演着重要的角色. 为了避免触雷, 「保卫世界和平」, 对 redis 数据进行分析并清理.
234 0
devops| redis 数据量暴涨进行数据清理实战
|
6天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1143 3
|
5天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
728 11
|
15天前
|
人工智能 运维 安全
|
4天前
|
机器学习/深度学习 物联网
Wan2.2再次开源数字人:Animate-14B!一键实现电影角色替换和动作驱动
今天,通义万相的视频生成模型又又又开源了!Wan2.2系列模型家族新增数字人成员Wan2.2-Animate-14B。
344 10
|
6天前
|
弹性计算 Kubernetes jenkins
如何在 ECS/EKS 集群中有效使用 Jenkins
本文探讨了如何将 Jenkins 与 AWS ECS 和 EKS 集群集成,以构建高效、灵活且具备自动扩缩容能力的 CI/CD 流水线,提升软件交付效率并优化资源成本。
324 0
|
13天前
|
人工智能 异构计算
敬请锁定《C位面对面》,洞察通用计算如何在AI时代持续赋能企业创新,助力业务发展!
敬请锁定《C位面对面》,洞察通用计算如何在AI时代持续赋能企业创新,助力业务发展!