美文网首页
二叉树的应用—哈夫曼树

二叉树的应用—哈夫曼树

作者: 梦在原点 | 来源:发表于2019-08-28 17:03 被阅读0次

带权路径长度

  • 路径长度:路径上所经历的边的个数
  • 结点的权:结点被赋予的数值

树的带权路径长度: 树中所有叶节点的带权路径之和

公式及计算如下

哈夫曼树:也成为最优二叉树,就是含n的带权叶子结点的树之中带权路径长度最小的二叉树。在上面的两个树中第二棵树就是一颗哈夫曼树。

构造哈夫曼树,只需按照步骤一步一步来即可
哈夫曼树在构造的时候没有规定左右子树,所以其不唯一

哈夫曼树的构造方法

哈夫曼树的性质

哈夫曼树的应用
编码:对于一个字符串序列,用二进制数来表示每一个字符

固定长度编码
可变长度编码,因为会产生歧义,不可应用
使用哈夫曼树构造的过程如下
字母对应的数字是指字母出现的次数
按照规则构造出来的哈夫曼树,左0,右1
这样构造出来的编码不会产生歧义,且长度变短了

相关文章

  • 题型

    树 二叉树相关计算二叉树的三种遍历序列 前/后序+中序序列构造树 哈夫曼树 哈夫曼树的构造哈夫曼编码带权路径长度压...

  • 哈夫曼编码

    一、概念:哈夫曼树,即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。在计算机信息处理中,“哈夫曼编码”...

  • 哈夫曼树

    数据结构——哈夫曼树 哈夫曼树又被称为最优二叉树,是指一类带权路径长度最小的二叉树,哈夫曼树的遍历不是唯一的,因为...

  • 数据结构与算法-哈弗曼编码

    1. 概念 哈夫曼树,即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。 在计算机信息处理中,“哈夫曼编...

  • 数据结构(五):哈夫曼树(Huffman Tree)

    哈夫曼树 哈夫曼树(或者赫夫曼树、霍夫曼树),指的是一种满二叉树,该类型二叉树具有一项特性,即树的带权路径长最小,...

  • 二叉树的创建和哈夫曼编码

    二叉树的创建 哈夫曼树

  • 哈夫曼树与哈夫曼编码

    哈夫曼树哈夫曼树又称最优二叉树,是一种带权路径最短的二叉树。对于给定的n个叶子结点,在构建哈夫曼树时只需要遵循一个...

  • 哈夫曼编码

    实验目的: (1) 掌握二叉树的定义; (2) 掌握哈夫曼树和哈夫曼编码算法的实现。 实验内容: 实现一个哈夫曼编...

  • 构造哈夫曼树和对每个字符进行编码

    必备知识 哈夫曼树也称为最优二叉树。 哈夫曼树并不唯一,但带权路径长度一定是相同的。 哈夫曼树中,左子树值必须小于...

  • 数据结构-哈夫曼树(python实现)

    好,前面我们介绍了一般二叉树、完全二叉树、满二叉树,这篇文章呢,我们要介绍的是哈夫曼树。哈夫曼树也叫最优二叉树,与...

网友评论

      本文标题:二叉树的应用—哈夫曼树

      本文链接:https://www.haomeiwen.com/subject/ebdmectx.html