- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
公式:
Wk: 第k个叶子的节点权值 。
Lk: 根节点到第k个叶子的节点长度 。
例如下列二叉树:
如上图可看出:1、 最后两个树的带权路径长度相同且也是最小的, 所以可看作哈夫曼树 。
2、 权值最小的节点越靠下,越大越靠近根节点 。
(1)、 在{2,3,5,8}这几个节点看作叶子节点(即后面没有子节点) 。
。
(2)、 在这几个节点中选出权值最小和次小的两个节点。构成一个新二叉树(最小为左字节的、次小为右子节点),新二叉树的权值为这两个权值之和. 。
(3)、删除已经使用过的节点。将新创建的节点加入到还没被使用过的节点集合中,找出最小和次小的节点权值。又构成一颗新的二叉树.
(4)、重复(2)的操作 。
。
(5)、重复上面操作:删除已使用的节点,将新的节点加入未使用节点的集合中,发现只有一个节点,其权值为18.则此哈夫曼树创建完成,根节点权值为18. 。
代码如下:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 构造哈夫曼树
*/
public class test1 {
public static void main(String[] args) {
int[] arr={2,3,5,8};
//调用自定义的哈夫曼树方法,生成哈夫曼树
hafmantree(arr);
}
/**
* ,构造哈夫曼数方法
*
* @param arry
*/
public static void hafmantree(int[] arry) {
//创建集合用于存放节点值
List<Node> nlis = new ArrayList<Node>();
//遍历集合
for (int value : arry) {
//将每个数组元素看作Node节点对象,并存入list集合内
nlis.add(new Node(value));
}
/*
由于集合中存入的是一个个的Node对象,而Node对象已经被我们声明成了按照从小到大的可排序对象。
所以这里我们为可以通过Collections工具类中的sort方法进行排序
*/
//循环条件:只有一个节点,即最终根节点
while (nlis.size() > 1) {
Collections.sort(nlis);
//查看集合中还未被使用的节点
System.out.println(nlis);
//到了这里说明集合中的所有节点(权值)都是按照从小到大的顺序
//获取最小的节点值(二叉树左节点):子节点
Node lileft = nlis.get(0);
//获取第2小的节点值(二叉树右节点):子节点
Node lireght = nlis.get(1);
/*创建新的Node节点对象(二叉树):
此节点对象是最小的两个节点之和所生成的最新的节点。三个节点可以看成一个二叉树,即:
根节点(insternode对象)、左子节点(lileft.value)、右子节点(lireght.value)
*/
Node insternode = new Node(lileft.value + lireght.value);
//此二叉树的左节点
insternode.left = lileft;
//此二叉树的右节点
insternode.right = lireght;
//删除已经被处理过的节点
nlis.remove(lileft);
nlis.remove(lireght);
//将最新的节点加入到list集合中
nlis.add(insternode);
//重新对最新的list数组进行排序
Collections.sort(nlis);
}
//查看最终根节点
System.out.println(nlis);
}
}
/**
* ,构造哈夫曼数节点类,
* 此类也可以看成一个二叉树:根节点(Node对象)、左节子点(left)、右字节点(right)
* 实现Comparable接口:说明此类是可通过Collections工具类排序的,
*/
class Node implements Comparable<Node> {
int value; //每个节点的值(权值)
Node left; //每个二叉树的左指向节点
Node right; //每个二叉树的右指向节点
//构造方法,这里只需要初始化value实例变量,用于对象的赋值,而 left 与 right 本身就是此对象,可直接用于value赋值
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//支持从小到大排序
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}
结果:
这里是对一段字符串进行哈夫曼编码,所以需要先处理字符串 。
在哈夫曼树的基础上,规定了路径编码.
遍历已经创建好了的哈夫曼树,从它的根节点遍历次树到叶子节点, 左子路径编码:0 、右子路径编码:1 。
import java.util.*;
/**
* 构造哈夫曼数+生成哈夫曼编码,编程实现。
*/
public class test1 {
public static void main(String[] args) {
//需要转换为哈夫曼编码的字符串
String valus="asdsgddbhj ,sjsh";
//将字符串存以node对象存入list集合中
List<Node> list = ListAndNode(valus);
//生成哈夫曼树
Node node = HFMTree(list);
//得到哈夫曼编码
HFMTable(node,"",andindex);
System.out.println(yezijied); //{32=1010, 97=1011, 98=1100, 115=01, 100=111, 103=1101, 104=001, 106=100, 44=000}
}
/*
第四步:
创建哈夫曼编码表:将叶子节点以0、1表示。0===》向左子节点走。1===》向右子节点走
yezijied:存放叶子节点对应的哈夫曼编码。此集合作业与全局
andindex:拼接编码。(拼接对应的0或1,形参最终的哈夫曼编码)
*/
static Map<Byte,String> yezijied=new HashMap<>();
static StringBuilder andindex=new StringBuilder();
/**
*
* @param node:节点
* @param index:路径表示:左路径为0.右路劲为1
* @param sub:拼接路径,使其成为对应叶子节点的哈夫曼码
*/
public static void HFMTable(Node node,String index,StringBuilder sub){
//
StringBuilder gitindex=new StringBuilder(sub);
//拼接路径
gitindex.append(index);
//如果节点为空就不需要处理
if (node!=null) {
//如果当前节点不是叶子节点
if (node.value == null) {
//如果节点不为空就递归其左边节点。并设置向左为0
HFMTable(node.left, "0", gitindex);
//如果节点不为空就递归其右边节点。并设置向右为1
HFMTable(node.right, "1", gitindex);
} else {
//为叶子节点就将其存入map集合中
yezijied.put(node.value, gitindex.toString());
}
}
}
/*
第三步:
@param nodes:已经存入list集合中的Node节点
创建字符串的哈夫曼树结构
*/
public static Node HFMTree(List<Node> nodes){
//循环条件:节点数必须大于1.如果等于1就是一个节点(根节点),没有分支
while (nodes.size()>1){
//排序list集合,根据权值(节点个数)从小到大排序
Collections.sort(nodes);
/*
创建一个二叉树:
feiyezijied:根节点
nodeleft:左子节点
noderight:右子节点
*/
//得到权值最小的两个节点.这两个节点分别可看作左右两个子节点
Node nodeleft = nodes.get(0);
Node noderight = nodes.get(1);
//创建新的Node对象:这可以想象为两个叶子节点生成的根节点,
// 由于哈夫曼数的原理,需要编码的值是叶子节点,而叶子节点上的父节点只是通过叶子节点虚拟创建的节点,
// 是为了形成一整颗完整的树。所以它是没有字符串原始值,,其可用两个字节的权值之和标记
Node feiyezijied=new Node(null,nodeleft.quanzhi+noderight.quanzhi);
//Node对象的左字节点
feiyezijied.left=nodeleft;
//Node对象的右字节点
feiyezijied.right=noderight;
//删除原集合中的以使用的节点对象.即上面已经每次获得的集合中两个最小的节点
nodes.remove(nodeleft);
nodes.remove(noderight);
//将新创建的Node节点加入list集合中
nodes.add(feiyezijied);
//重新对list集合排序
Collections.sort(nodes);
}
//返回最终根节点
return nodes.get(0);
}
/*
第二步:
@param valus:传入需要编码的字符串,将其变成节点
将需要编码的字符串,每个原始值(ASCIIM码)以节点(Node)对象形式传入list集合中。
而节点对象Node初始化了value与quanzhi,所以节点对象是包括这两个值,所以将每个节点对象当作一个map.
设k=value、v=quanzhi
*/
public static List<Node> ListAndNode(String valus){
//将字符对象存入byte数组。
byte[] bytes = valus.getBytes();
//创建List集合
List<Node> nodes=new ArrayList<>();
//创建Map集合
Map<Byte,Integer> node=new HashMap<>();
//遍历bytes数组,得到每个字符串的原始值
for (byte by:bytes){
//先试着通过传入的第一个k获取v
Integer index = node.get(by);
//如果map集合中此原始值对应的个数还没有
if (index==null){
node.put(by,1);
}else {
node.put(by,index+1);
}
}
//遍历map集合,并将每次遍历的元素,以Node对象的形式存入list集合
for (Map.Entry<Byte,Integer> n:node.entrySet()){
nodes.add(new Node(n.getKey(),n.getValue()));
}
//最后返回此list集合
return nodes;
}
}
/*
第一步:
节点类:其本身可可看作一个概念性的二叉树
Node对象本身可看作是一个二叉树的根节点
实现Comparable接口:泛型规定此接口作用与此Node节点,说明此类是可排序的,通过' Collections.sort()'
*/
class Node implements Comparable<Node>{
Byte value; //原始值:字符本身的ASCIIM码。因为一段字符串中有许多相同的字符,但相同字符却对应这一个ASCIIM码
int quanzhi; //此字符value在一段字符串中出现的次数
Node left; //Node对象看作是二叉树的根节点,那么这就是此二叉树的左子节点
Node right; //Node对象看作是二叉树的根节点,那么这就是此二叉树的右边子节点
//构造器初始化 value 、quanzhi。
public Node(Byte value, int quanzhi) {
this.value = value;
this.quanzhi = quanzhi;
}
//重写toString:因为我们需要拿到这两个值
@Override
public String toString() {
return "Node{" +
"value=" + value +
", quanzhi=" + quanzhi +
'}';
}
//实现Comparable接口中的方法:手动设置排序规则
@Override
public int compareTo(Node o) {
//设置为通过权值从小到大排序
return this.quanzhi-o.quanzhi;
}
//前序遍历
public void qxbl(){
//先输出当前节点,也就是根节点
System.out.println(this);
//如果左子节点不是null节点,就递归遍历输出左子节点.null表示不是叶子节点
if (this.left!=null){
this.left.qxbl();
}
//同样递归右子节点
if (this.right!=null){
this.right.qxbl();
}
}
}
最后此篇关于贪心算法-构造哈夫曼数及生成哈夫曼编码,编程实现的文章就讲到这里了,如果你想了解更多关于贪心算法-构造哈夫曼数及生成哈夫曼编码,编程实现的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
背景: 我最近一直在使用 JPA,我为相当大的关系数据库项目生成持久层的轻松程度给我留下了深刻的印象。 我们公司使用大量非 SQL 数据库,特别是面向列的数据库。我对可能对这些数据库使用 JPA 有一
我已经在我的 maven pom 中添加了这些构建配置,因为我希望将 Apache Solr 依赖项与 Jar 捆绑在一起。否则我得到了 SolarServerException: ClassNotF
interface ITurtle { void Fight(); void EatPizza(); } interface ILeonardo : ITurtle {
我希望可用于 Java 的对象/关系映射 (ORM) 工具之一能够满足这些要求: 使用 JPA 或 native SQL 查询获取大量行并将其作为实体对象返回。 允许在行(实体)中进行迭代,并在对当前
好像没有,因为我有实现From for 的代码, 我可以转换 A到 B与 .into() , 但同样的事情不适用于 Vec .into()一个Vec . 要么我搞砸了阻止实现派生的事情,要么这不应该发
在 C# 中,如果 A 实现 IX 并且 B 继承自 A ,是否必然遵循 B 实现 IX?如果是,是因为 LSP 吗?之间有什么区别吗: 1. Interface IX; Class A : IX;
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我正在阅读标准haskell库的(^)的实现代码: (^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 a -> b ->a expo x0
我将把国际象棋游戏表示为 C++ 结构。我认为,最好的选择是树结构(因为在每个深度我们都有几个可能的移动)。 这是一个好的方法吗? struct TreeElement{ SomeMoveType
我正在为用户名数据库实现字符串匹配算法。我的方法采用现有的用户名数据库和用户想要的新用户名,然后检查用户名是否已被占用。如果采用该方法,则该方法应该返回带有数据库中未采用的数字的用户名。 例子: “贾
我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象,并且我有一个二维数组来保存两个给定顶点
我目前正在 ika 中开发我的 Python 游戏,它使用 python 2.5 我决定为 AI 使用 A* 寻路。然而,我发现它对我的需要来说太慢了(3-4 个敌人可能会落后于游戏,但我想供应 4-
我正在寻找 Kademlia 的开源实现C/C++ 中的分布式哈希表。它必须是轻量级和跨平台的(win/linux/mac)。 它必须能够将信息发布到 DHT 并检索它。 最佳答案 OpenDHT是
我在一本书中读到这一行:-“当我们要求 C++ 实现运行程序时,它会通过调用此函数来实现。” 而且我想知道“C++ 实现”是什么意思或具体是什么。帮忙!? 最佳答案 “C++ 实现”是指编译器加上链接
我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack 我试图让我的 C++ 版本打印
在很多情况下,我需要在 C# 中访问合适的哈希算法,从重写 GetHashCode 到对数据执行快速比较/查找。 我发现 FNV 哈希是一种非常简单/好/快速的哈希算法。但是,我从未见过 C# 实现的
目录 LRU缓存替换策略 核心思想 不适用场景 算法基本实现 算法优化
1. 绪论 在前面文章中提到 空间直角坐标系相互转换 ,测绘坐标转换时,一般涉及到的情况是:两个直角坐标系的小角度转换。这个就是我们经常在测绘数据处理中,WGS-84坐标系、54北京坐标系
在软件开发过程中,有时候我们需要定时地检查数据库中的数据,并在发现新增数据时触发一个动作。为了实现这个需求,我们在 .Net 7 下进行一次简单的演示. PeriodicTimer .
二分查找 二分查找算法,说白了就是在有序的数组里面给予一个存在数组里面的值key,然后将其先和数组中间的比较,如果key大于中间值,进行下一次mid后面的比较,直到找到相等的,就可以得到它的位置。
我是一名优秀的程序员,十分优秀!