数据结构-非线性结构-树形结构:有序树 ->二叉树 ->哈夫曼树 / 霍夫曼树(Huffman Tree)【根据所有叶子节点的权值构造出的 -> 带权值路径长度最短的二叉树,权值较大的结点离根较近】

本文主要是介绍数据结构-非线性结构-树形结构:有序树 ->二叉树 ->哈夫曼树 / 霍夫曼树(Huffman Tree)【根据所有叶子节点的权值构造出的 -> 带权值路径长度最短的二叉树,权值较大的结点离根较近】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
哈夫曼树概念:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。

哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

一、相关概念

二叉树:每个节点最多有2个子树的有序树,两个子树分别称为左子树、右子树。有序的意思是:树有左右之分,不能颠倒

叶子节点:一棵树当中没有子结点的结点称为叶子结点,简称“叶子”

路径和路径长度:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。

结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积

树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和

树的高度:树中结点的最大层次。包含n个结点的二叉树的高度至少为log2 (n+1)

二、哈夫曼树的构造算法

  1. { W 1 , W 2 , W 3 … W n } \{W_1,W_2,W_3 \dots W_n\} {W1,W2,W3Wn}看成n棵树的森林
  2. 在森林中选择两个根节点权值最小的树进行合并,作为一颗新树的左右子树,新树的根节点权值为左右子树的和
  3. 删除之前选择出的子树,把新树加入森林
  4. 重复2-3步骤,直到森林只有一棵树为止,概树就是所求的哈夫曼树

注意:哈夫曼树并不唯一,但带权路径长度一定是相同的。

三、哈夫曼树的构造过程

  1. 8个结点的权值大小如下:
    在这里插入图片描述
  2. 从19,21,2,3,6,7,10,32中选择两个权小结点。选中2,3。同时算出这两个结点的和5。

在这里插入图片描述

  1. 从19,21,6,7,10,32,5中选出两个权小结点。选中5,6。同时计算出它们的和11。

在这里插入图片描述

  1. 从19,21,7,10,32,11中选出两个权小结点。选中7,10。同时计算出它们的和17。
    【这时选出的两个数字都不是已经构造好的二叉树里面的结点,所以要另外开一棵二叉树;或者说,如果两个数的和正好是下一步的两个最小数的其中的一个,那么这个树直接往上生长就可以了,如果这两个数的和比较大,不是下一步的两个最小数的其中一个,那么就并列生长。】
    在这里插入图片描述

  2. 从19,21,32,11,17中选出两个权小结点。选中11,17。同时计算出它们的和28。
    在这里插入图片描述

  3. 从19,21,32,28中选出两个权小结点。选中19,21。同时计算出它们的和40。另起一颗二叉树。
    在这里插入图片描述

  4. 从32,28, 40中选出两个权小结点。选中28,32。同时计算出它们的和60。

在这里插入图片描述

  1. 从 40, 60中选出两个权小结点。选中40,60。同时计算出它们的和100。 好了,此时哈夫曼树已经构建好了。
    在这里插入图片描述

可见:

  1. 权重越大,距离根节点越近
  2. 叶子的个数为n,构造哈夫曼树中新增的节点的个数为n-1

四、哈夫曼编码

在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符。

例如,需传送的报文为AFTER DATA EAR ARE ART AREA,这里用到的字符集为A,E,R,T,F,D,各字母出现的次数为{8,4,5,3,1,1}。现要求为这些字母设计编码。要区别6个字母,最简单的二进制编码方式是等长编码,固定采用3位二进制,可分别用000、001、010、011、100、101A,E,R,T,F,D进行编码发送

但是很明显,上述的编码的方式并不是最优的,即整理传送的字节数量并不是最少的。

为了提高数据传送的效率,同时为了保证【前缀编码】,可以使用哈夫曼树生成哈夫曼编码解决问题。【任一字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码

可用字符集中的每个字符作为叶子结点生成一棵编码二叉树,为了获得传送报文的最短长度,可将每个字符的出现频率作为字符结点的权值赋予该结点上,显然字使用频率越小权值越小,权值越小叶子就越靠下,于是频率小编码长,频率高编码短,这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度

因此,求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点,由字符出现频率作为其权值所产生的哈夫曼树的问题。

利用哈夫曼树来设计二进制的前缀编码,

  • 既满足【前缀编码】的条件
  • 又保证报文编码总长最短

下图中label1 .... label6分别表示A,E,R,T,F,D左节点用1表示,右节点用0表示

在这里插入图片描述

这篇关于数据结构-非线性结构-树形结构:有序树 ->二叉树 ->哈夫曼树 / 霍夫曼树(Huffman Tree)【根据所有叶子节点的权值构造出的 -> 带权值路径长度最短的二叉树,权值较大的结点离根较近】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1128827

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

自定义类型:结构体(续)

目录 一. 结构体的内存对齐 1.1 为什么存在内存对齐? 1.2 修改默认对齐数 二. 结构体传参 三. 结构体实现位段 一. 结构体的内存对齐 在前面的文章里我们已经讲过一部分的内存对齐的知识,并举出了两个例子,我们再举出两个例子继续说明: struct S3{double a;int b;char c;};int mian(){printf("%zd\n",s

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In