哈夫曼树基本原理

2023-05-16

首先我们看看基本定义
哈夫曼树的学术定义为,带权路径长度最短的二叉树,即节点具有两个属性:
1、权值,可以看作节点表达出的数值大小,或者变换的表示为概率大小
2、路径,可以看作由根节点到达当前节点的分支数,左分支和右分支具有不同意义
带权路径长度即为权值与路径乘积的累加,所以哈夫曼树首先是一棵二叉树,其次通过调整二叉树节点位置,使得带权路径长度最小。
综上也就是把每个节点合并为根节点的左右节点,且每次选择合并时要使得根节点最小。哈夫曼树是从根部往下走越来越小

 A

 

此图片较好说明了生成步骤可以参考理解

 直接上代码

#include<iostream>
#include <vector>
#include<queue>
#include <functional>
using namespace std;
struct node
{
	int data;
	node*ltree;
	node*rtree;
	node()
	{
		ltree = rtree = NULL;
	}
	node(int data)
	{
		this->data = data;
		ltree = rtree = NULL;
	}
};
struct Huffmantree 
{
	node *root;
	Huffmantree(){
		root = NULL;
	}
	Huffmantree(int weight){ root = new node(weight); }
	Huffmantree(vector<Huffmantree>&nodes)
	{
		Huffmantree tmp;
		priority_queue<Huffmantree, vector<Huffmantree>, greater<Huffmantree>>q(nodes.begin(), nodes.end());
		for (int i = 1; i<nodes.size();i++)
		{
			tmp.root = new node;
			tmp.root->ltree = q.top().root; q.pop();
			tmp.root->rtree = q.top().root; q.pop();
			tmp.root->data = tmp.root->ltree->data + tmp.root->rtree->data;
			q.push(tmp);
		}
		root = q.top().root;
	}
	bool operator >(const Huffmantree &t)const{
		return this->root->data > t.root->data;
	}
	void print()
	{
		rprint(root, 0);
	}
	void rprint(node *r,int depth)
	{
		for (int i = 0; i < depth;i++)
		{
			cout << " ";
		}
		if (!r)
		{
			cout << "[/]"<< endl;
		}
		else
		{
			
				cout << r->data << endl;					
		
				rprint(r->ltree, depth + 1);
			
			
				rprint(r->rtree, depth + 1);
			
			
		}
	}
};

void main()
{
	int nv, weight;
	cin >> nv;
	vector<Huffmantree>nodes;
	for (int i = 0; i < nv;i++)
	{
		cin >> weight;
		nodes.emplace_back(weight);
	}
	Huffmantree ht(nodes);
	ht.print();
	system("pause");
}

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

哈夫曼树基本原理 的相关文章

  • 【蓝桥日记⑥】2013第四届省赛(软件类)JavaA组@答案解析

    蓝桥日记 2013第四届省赛 xff08 软件类 xff09 JavaA组 64 答案解析 文章目录 蓝桥日记 2013第四届省赛 xff08 软件类 xff09 JavaA组 64 答案解析1 世界末的星期2 振兴中华3 梅森素数4 颠倒
  • 《长日将尽》事业禁锢了自我,然`长日终将尽,告别有晴天

    长日将尽 事业禁锢了自我 xff0c 然 96 长日终将尽 xff0c 告别有晴天 石黑一雄 xff0c 日裔英国小说家 xff0c 1954年生于日本长崎 与奈保尔 拉什迪并成为 英国文坛移民三雄 主要作品有 远山淡影 浮世画家 长日将尽
  • 《雪国》像憧憬未曾见过的爱恋,美则美矣

    雪国 像憧憬未曾见过的爱恋 xff0c 美则美矣 川端康成 xff08 1899 1972 xff09 日本作家 生于大阪 新感觉派 1968年以 敏锐的感受 xff0c 高超的叙事技巧 xff0c 表现日本人的精神实质 获诺贝尔文学奖 代
  • linux编译安装aria2,远程下载设置

    系统 xff1a centos 最新aria2下载 aria2 github 1 下载并解压最新的aria2 cd wget https github com aria2 aria2 releases download release 1
  • 《金阁寺》金阁美之于幻想,我用摧毁它来成就其美

    金阁寺 金阁美之于幻想 xff0c 我用摧毁它来成就其美 三岛由纪夫 xff08 1925 1970 xff09 日本当代小说家 剧作家 记者 电影制作人和电影演员 xff0c 右翼分子 主要作品有 金阁寺 鹿鸣馆 丰饶之海 等 曾3次获诺
  • 《春琴抄》庭有枇杷树,今已亭亭如盖矣~

    春琴抄 庭有枇杷树 xff0c 今已亭亭如盖矣 谷崎润一郎 xff08 1886年7月24日 xff5e 1965年7月30日 xff09 xff0c 日本近代小说家 xff0c 唯美派文学主要代表人物之一 xff0c 源氏物语 现代文的译
  • windows系统管理_windows server 2016网络参数配置

    网络参数配置 要将安装好的操作系统接入到网络中 xff0c 首先需要做的是为操作系统配置 IP 地址等参数 Windows 2016 支持 IPV4 以及 IPV6 两种网络协议 IPV4 IPV6 DNS概述 IPV4介绍 网际协议版本4
  • mysql linux 配置文件和日志默认路径

    配置文件 etc my cnf 日志 var log mysqld log
  • sqlite:微信数据库

    文章目录 一 安装java1 下载安装文件2 配置环境变量3 安装成功测试 二 本地备份数据库三 获取数据库密码四 从数据库中导出需要的数据1 导数据2 表格对应数据 一 安装java 1 下载安装文件 Java SE Developmen
  • postgresql和mysql之间比较

    一 事务隔离之间的比较 事务隔离级别postgresqlmysql读未提交无法读脏数据有读已提交快照实现快照实现可重复读有 xff0c 无幻读 xff0c 发生冲突时 xff0c 牺牲其中一个事务已实现 xff0c 有幻读 xff0c 悲观
  • 计算机中的左移和右移

    左移和右移都是位运算的概念 我们知道计算机是基于二进制保存数据的 xff0c 因此左移和右移的概念十分重要 本文约定是32位的机器 左移 丢弃最高位 xff0c 0补最低位 左移是把一个数按照二进制每位向左移动若干位 xff0c 在c语言中
  • AJAX中的跨域(CORS) 问题 (更新于2023.02.04)

    目录 预检请求 实例讲解 2023 02 04 更新 此文章在介绍跨域加载的同时 xff0c 也解决了在使用axios post 时如下跨域加载失败问题 xff1a from origin 39 null 39 has been block
  • OpenStack Zun组件详解

    什么是ZUN xff1f Zun是Openstack中提供容器管理服务的组件 xff0c 于2016年6月建立 Zun的目标是提供统一的Openstack API用于启动和管理容器 xff0c 支持多种容器技术 Zun原来称为Higgins
  • Ubuntu配置全局系统代理(常用工具配置)

    Ubuntu配置全局系统代理 xff08 常用工具 xff09 问题描述解决方法配置系统代理终端部分配置配置apt代理配置curl wget pip代理git相关代理的设置配置docker代理 问题描述 公司电脑网络规则做了限制 xff0c
  • Deepin中使用Windows字体

    本方案适用与Windows与Deepin 双系统的用户 xff08 以及所有Win与Linux双系统 xff09 只需要把Windows下 Windows Fonts的文件夹 复制到 Deepin下 usr share fonts 额外项
  • 无线攻击 --Fern WiFi Cracker(图形化无线密码破解工具 )

    文章目录 一 用法概述1 1 概述1 2 优点1 3 缺点 二 WiFi破解实验2 1 操作环境2 2 操作过程 一 用法概述 1 1 概述 Fern WiFi Cracker是一个使用Python编程语言和Python Qt GUI库编写
  • node 连接数据库进行增删改查

    导入模块 const mysql 61 require 34 mysql 34 建立 const db 61 mysql createPool host 34 127 0 0 1 34 user 34 root 34 password 34
  • Linux 虚拟机和主机互通 [万能方法]

    VMware Linux 虚拟机和主机互通 万能方法 前言 xff1a 诸如以下问题 xff0c 解决问题的思路都是一样的 xff0c 看完此文后都能找到答案 xff1a 主机为何 ping 不通 虚拟机 xff1f 请检查是否在同一网段
  • 洛谷 P2651 添加括号III

    思路 xff1a a1肯定是分子 xff0c a2肯定是分母 xff0c 只要确认a1a3a4 a2是否是整数 只要确认a1a3a4 a2是否是整数 每次将a2 61 a2 gcd a2 ai i 61 1 3 4 5 即可约分 span
  • Win10系统重装教程(纯净版)

    文章目录 一 提示二 制作系统u盘1 官网下载工具2 选择 立即下载工具 xff0c 然后选择 运行 3 选择 为另一台电脑创建安装介质 xff0c 然后选择 下一步 4 选择对应的Windows版本 xff0c 然后点击 下一步 5 选择

随机推荐

  • Web安全—CSRF漏洞利用(pikachu)

    Web安全 CSRF漏洞利用 前言 xff1a 此篇文章主要记录pikachu靶场漏洞中三种模式的CSRF漏洞的利用 xff0c 此处不对基本原理进行过多赘述 xff0c 基础可参考文章 xff1a Web安全 跨站请求伪造攻击 xff08
  • 1034: 字典序最小的子序列(单调队列)

    题目描述 PIPI有一个字符串S xff0c 现在它想刁难刁难一下聪明的你 xff0c 首先它给你一个整数K xff0c 要你找出字典序最小的字符串T xff0c 并且字符串T满足 xff1a T由S的子序列构成 xff08 如S 61 a
  • Ubuntu server 18.04配置lftp过程libtinfo.so.6 error解决方法

    基本情况 服务器型号 xff1a DELL PowerEdge T440 系统版本 xff1a ubuntu 18 04 4 live server amd64 iso 配置lftp 按如下命令安装 xff1a sudo apt get u
  • (RPA)手把手——正则表达式基本使用(二)

    艺赛旗 RPA9 0全新首发免费下载 点击下载 http www i search com cn index html from 61 line1 重复次数 后面跟着元字符 43 or 的 用来指定匹配子模式的次数 这些元字符在不同的情况下
  • Python序列类型的切片

    序列类型的切片 在字符串 列表 元组三种序列类型中的切片方法一致 xff0c 都是使用变量名 43 开始索引值 结束索引值 xff1a 步长 的方式 xff0c 若是步长省略则步长默认为1 步长 xff0c 顾名思义就是一步有多长 xff0
  • 当url中出现“#“号时,“#“及其后面的字符串都会被忽略

    url中出现 34 号时 xff0c 34 及后面参数为null 解决方法 xff1a 传参就用escape 函数转义 原理 xff1a 当url中出现 34 号时 xff0c 及其后面的字符串都会被忽略 xff0c 不会被发送到服务器 x
  • springboot项目打成jar包后,放在linux系统上运行时出现文件空指针等问题

    场景 xff1a 使用springboot搭建Fabric java sdk的客户端项目 xff0c 需要将Fabric网络生成的密钥和证书的文件夹拷贝到项目的资源目录或者config包下 xff0c 在配置文件中配置各种证书的路径 xff
  • Ubuntu常见问题解决

    Ubuntu常见问题解决 1 ubuntu系统上安装qt5 12后无法调试运行 原因 xff1a 缺少gcc g 43 43 make libgl1 sudo apt span class token operator span get i
  • vscode 配置 copilot(最牛逼的AI智能提示)

    copilot github 如果绑定了学校邮箱 申请免费资格 https link zhihu com target 61 https 3A github com features copilot signup vscode 更新到最新版
  • OpenCV4.7+VS2019环境变量配置

    OpenCV4 7 43 VS2019配置 1 下载OpenCV并解压安装2 配置环境 xff08 1 xff09 配置环境变量 xff08 2 xff09 将系统改成x64 xff08 3 xff09 配置包含目录 xff08 4 xff
  • win10下mysql的下载、安装以及SSL配置超详解教程

    mysql 5 7 28 winx64的下载 安装以及SSL配置教程 1 下载mysql 压缩文件2 安装教程3 安装mysql 5 7 28 winx643 1 解压缩3 2 配置my ini文件3 3 配置环境变量3 4 安装 open
  • java获取jar包中的文件资源

    java获取jar包中的文件资源 一 问题示例1 1 项目开发时1 2 打包成jar后 二 解决方案2 1 解决方法2 2 实现 问题描述 xff1a 我们常常在代码中读取一些资源文件 比如图片 xff0c 音乐 xff0c 文本等等 在单
  • week12-作业(动态规划)

    C 必做题 3 东东每个学期都会去寝室接受扫楼的任务 xff0c 并清点每个寝室的人数 每个寝室里面有ai个人 1 lt 61 i lt 61 n 从第i到第j个宿舍一共有sum i j 61 a i 43 43 a j 个人 这让宿管阿姨
  • 自动写代码?Copilot尝鲜及其奇技淫巧

    自动写代码 Copilot尝鲜及其奇技淫巧 博主在同学那里了解到Copilot这个神奇的项目 xff0c 听说能自动帮你写代码 xff0c 顿时来了性质 xff0c 从现在起 xff0c 我不再写代码 xff0c 我要搭载Copilot起飞
  • 两台MAC时间机器的备份和系统恢复

    背景 xff1a 一台mbp16寸 xff08 2019 xff09 xff0c 系统为最新的12 2 1 xff0c 本文命名为A 一台mba13寸 xff08 2020 xff09 xff0c 系统为10 15 7 xff0c 本文命名
  • 个人深度学习工作站配置ssh&xrdp&vnc远程连接

    最近实验室买了台服务器主要用于跑深度学习 xff0c 买过来只有一台主机 xff0c 所有的东西都需要自己配置 xff0c 经过半个月了踩坑 xff0c 将自己配置成功的案例写下来 xff0c 有相关需求的小伙伴可以参考一下 xff1a 主
  • 程序员必须掌握的核心算法

    程序员必须掌握的核心算法 一 算法最最基础 1 时间复杂度 2 空间复杂度 一般最先接触的就是时间复杂度和空间复杂度的学习了 xff0c 这两个概念以及如何计算 xff0c 是必须学的 xff0c 也是必须最先学的 xff0c 主要有最大复
  • MFC实现计算器

    MFC实现计算器 简易计算器实现加减乘除等功能 xff0c 可以使用小数点 1 首先添加计算器按钮界面 2 设置好各个变量 xff0c 注意添加变量时要选择value 3 双击各个button按键依次添加功能 话不多说直接上代码 Mcoun
  • 关于图算法的整理DFS,BFS,Dijkstra,Prim代码

    图 邻接矩阵与邻接表 xff08 两者皆可用来表示有向图和无向图 xff09 创建一个基类graph pragma once include lt iostream gt include lt vector gt include lt ma
  • 哈夫曼树基本原理

    首先我们看看基本定义 哈夫曼树的学术定义为 xff0c 带权路径长度最短的二叉树 xff0c 即节点具有两个属性 xff1a 1 权值 xff0c 可以看作节点表达出的数值大小 xff0c 或者变换的表示为概率大小 2 路径 xff0c 可