赫夫曼树(最优二叉树)_用赫夫曼算法画最优二元树怎么排序-程序员宅基地

技术标签: 算法  二叉树  霍夫曼树  

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

术语

  1. 路径和路径长度:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路更多中分支的数目称为路径长度
  2. 若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-12)结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积
  3. 树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL(weighted pathlength),权值越大的结点离根结点越近的二叉树才是最优二叉树。4
  4. WPL最小的就是赫夫曼树

解题思想

构成赫夫曼树的步骤:
5. 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
6. 取出根节点权值最小的两颗二叉树
7. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
8. 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树

public static Node createHuffmanTree(int[] arr) {
    

   List<Node> nodes = new ArrayList<Node>();
   for (int value : arr) {
    
      nodes.add(new Node(value));
   }

   while (true){
    
      if (nodes.size() <= 1){
    
         break;
      }
      //1. 先排序
      Collections.sort(nodes);

      //2.取出最小的2的结点
      Node leftNode = nodes.get(0);
      Node rightNode = nodes.get(1);

      //3构建一颗新的二叉树
      Node parent = new Node(leftNode.value + rightNode.value);
      parent.left = leftNode;
      parent.right = rightNode;


      nodes.remove(leftNode);
      nodes.remove(rightNode);

      nodes.add(parent);
   }

   return nodes.get(0);
   
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45904404/article/details/118862882

智能推荐

【Java 进阶】File类知识详解、绝对路径和相对路径的区别-程序员宅基地

文章浏览阅读2.1k次。File 类笔记,供自己方便查看0.看看绝对路径和相对路径是啥哈绝对路径:从盘符开始的路径,这是一个完整的路径。相对路径:相对于项目目录的路径,这是一个便捷的路径,开发中经常使用。天涯海角找到你和只能在眼前找到你的区别public class FilePath { public static void main(String[] args) { // D盘下的bbb.java文件 File f = new File("D:\\bbb.java");

R语言:使用rvest包抓取新浪财经A股交易数据-程序员宅基地

文章浏览阅读6.6k次,点赞6次,收藏48次。R语言网络爬虫工具中比较常用的包有RCurl、XML、rvest等,本文以新浪财经频道A股交易数据的抓取为例简单总结一下rvest包的用法。  首先介绍一下我们要抓取的对象,我们以“中信证券(600030)”为例,抓取其日度交易数据。url地址为http://vip.stock.finance.sina.com.cn/corp/go.php/vMS_FuQuanMarketHistory/st

沙普利算法java实现_Java实现婚姻稳定匹配Gale- Shapley算法-程序员宅基地

文章浏览阅读761次。稳定匹配算法是美国数学家 David Gale 和 Lloyd Shapley在1962年提出的一种寻找稳定婚姻的策略。这种匹配方式的特点在于:不管需要匹配的总人数有多少、不管他们各自的偏好如何,只要男女人数相等,并且男女双方每个人都能在心中给对方打分,那么应用这种策略后总能得到一个稳定的婚姻搭配。有N男N女需要寻找结婚对象,并假设他们的性取向全部正常——即婚姻的搭配方式只有男&女这一种。..._java盖尔沙普利稳定匹配算法分享

python中format函数用法简书_Python str.format() 使用-程序员宅基地

文章浏览阅读123次。1. Basic usage>>> print('{} {}'.format('hello','world'))hello world>>> print('{1} {1} and {0}'.format('hello','world'))world world and hello>>> print('{a} {tom} {a}'.format(tom='hello',a='world')) #可..._str.format()函数取位数

app.use和app.get,app.post区别_app.use 和 app.get-程序员宅基地

文章浏览阅读1.2k次。express中,express的实例app:app.use(path,callback)中的callback既可以是router对象又可以是函数app.get(path,callback)中的callback只能是函数给app.get(app.post、app.put同理)赋个路由对象是不行的,其实,可以将app.get()看作app.use的特定请求(get)的简要写法var express = require('express');var app = express();app_app.use 和 app.get

2-2 MongoDB 之聚合函数查询统计-educoder上面的习题笔记_mongodb里显示第2-3个文档信息-程序员宅基地

文章浏览阅读2.3k次。目录第一关:3-1-1聚合管道操作符将文档定制第二关:3-1-2 聚合管道操作符将文档第三关:3-1-3聚合表达式对文档数据进行统计多管道练习题:MapReduce查询:_mongodb里显示第2-3个文档信息

随便推点

spark sql 原理以及解析_sparksql提交的原理-程序员宅基地

文章浏览阅读1k次。前三节,我们从spark底层的RDD角度去剖析了整个Spark 程序的执行逻辑,以及一些原理性的东西,当然我们在使用的时候要是直接使用Spark Core的编程语法也可以,在此基础上Spark 还提供了基于SQL的编程语法,也就是Spark-Sql,本文章从以下几个方面去分析Spark-SqlSpark Sql 简介 Spark Sql 执行原理 Catalyst整体执行流程介绍..._sparksql提交的原理

springboot中怎么获取多例(prototype)-程序员宅基地

文章浏览阅读3k次。平时我们使用springboot注入的类,默认是单例的。所以需要在注入的时候声明是原型模式(prototype)@Component@Scope("prototype")public class User1 { private String name; public String getName() { return name; } public void setName(String name) { this.name =

tomcat关闭时报Catalina.stop: java.net.ConnectException: 拒绝连接 (Connection refused)的错误-程序员宅基地

文章浏览阅读3.6w次。tomcat修改server.xml的端口为80后启动,无法正常访问tomcat页面的页面,修改回来用8080端口依旧无法正常打开,关闭tomcat后报Catalina.stop: java.net.ConnectException: 拒绝连接 (Connection refused)的错误,首先查看是否80端口被占用了。# lsof -i :8080或者# netstat -an..._java.net.connectexception: 拒绝连接

adaboost算法以及sklearn实现_sklearn adaboost-程序员宅基地

文章浏览阅读2.1k次,点赞2次,收藏12次。Adaboost分类器非集成的机器学习算法就像古代皇帝一样,一个人说了算;集成学习算法类似于现在的国会,需要听取在会所有人的意见。Adaboost是一个集成学习算法,下面将会对算法进行拆解,以使我们明白Adaboost的内部原理。Adboost算法核心内容可以划分为两个问题:(1)如何构建弱分类器;(2)如何组合这些弱分类器。其中(1)又可以细化为:1)使用哪种模型作为..._sklearn adaboost

android数据库加密之—sqlcipher,作为Android程序员都应掌握-程序员宅基地

文章浏览阅读438次。实现增删改查方法package com.ddv.www.sqlcipher.dbhelper;import android.content.ContentValues;import android.content.Context;import android.util.Log;import net.sqlcipher.Cursor;import net.sqlcipher.SQLException;import net.sqlcipher.database.SQLiteDatabase;.

K-d tree-程序员宅基地

文章浏览阅读263次。在计算机科学中,k-d树(k-dimensional的缩写)是一种空间划分数据结构,用于组织k维空间中的点。k-d树是几种应用程序的有用数据结构,例如涉及多维搜索关键字的搜索(例如范围搜索和最近邻居搜索)。k-d树是二进制空间划分树的一种特殊情况。...