当前位置: 首页 > 知识库问答 >
问题:

霍夫曼二叉树必须是正确的吗?

文建业
2023-03-14

我能找到的所有霍夫曼编码示例都有偶数个字符可以使用。如果是奇数个字符,添加到树中的最后一个内部节点可以只有一个子节点吗?还是我必须添加某种NULL节点,以便所有内部节点都只有两个子节点?

如果是后者,这似乎令人困惑,因为我不确定如何为char设置NULL值(因为所有值都被用作有效的ASCII代码)。

共有1个答案

华宇
2023-03-14

chars的奇数是没有问题的。但这不会导致只有一个子节点的内部节点。

  /\
 /  \
a    ×
    / \
   b   c

树的构造方式确保所有内部节点都有两个子节点,而不管有多少char

一种是从一个叶子列表开始,然后在每一步中,通过使两个频率最低的树成为左边的树来连接它们。一个新的内部节点的右子树,直到只剩下一棵树。最终结果中的每个内部节点由两个子树连接而成,因此有两个子节点。

 类似资料:
  • 我正在尝试创建一个正确的霍夫曼树,并想知道这是否正确。顶部数字是频率/权重,底部数字是 ASCII 代码。字符串是“hhiiiissssss”。如果我将其输入到文本文件中,则只有一个 LF 正确吗?我不确定为什么我的程序是两读的。

  • 主要内容:哈夫曼树相关的几个名词,什么是哈夫曼树,构建哈夫曼树的过程,哈弗曼树中结点结构,构建哈弗曼树的算法实现赫夫曼树,别名“哈夫曼树”、“最优树”以及“最优 二叉树”。学习哈夫曼树之前,首先要了解几个名词。 哈夫曼树相关的几个名词 路径: 在一棵树中,一个结点到另一个结点之间的通路,称为 路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。 路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度

  • 本文向大家介绍霍夫曼编码算法,包括了霍夫曼编码算法的使用技巧和注意事项,需要的朋友参考一下 霍夫曼编码是一种无损数据压缩算法。在该算法中,分配了可变长度代码以输入不同的字符。代码长度与字符使用频率有关。最常见的字符具有最小的代码,较长的代码具有最不频繁的字符。 主要有两个部分。第一个创建霍夫曼树,另一个遍历该树以查找代码。 例如,考虑一些字符串“ YYYZXXYYX”,字符Y的频率大于X,字符Z的

  • 我正在尝试在python中生成霍夫曼代码树的有序和预序遍历。不过,我似乎碰壁了。我需要生成遍历并将它们写入相应的文件,然后创建指向每个节点位置的二进制路径并将其输出到文件中。这是我到目前为止所拥有的

  • 我正在为算法和数据结构课做作业。我很难理解给出的说明。我会尽力解释这个问题。 我得到的输入是一个正整数 n,后跟 n 个正整数,表示有序字符集中符号的频率(或权重)。第一个目标是构造一个树,为有序字符集的每个字符提供近似的顺序保持霍夫曼代码。我们要通过“贪婪地合并权重最小的两棵相邻树”来实现这一点。 在赋值中,我们看到传统的霍夫曼代码树是通过将权重首先插入到优先级队列中来构造的。然后通过使用 de

  • 赫夫曼树 路径和路径长度:表示树从根节点开始到达节点经过的次数,若一颗树根节点为1层,那么第K层的树的路径的长度为K-1 权: 赋予每一个节点上面特定的权重值 带权路径:带权路径等于节点的权与路径长度的乘积,为带权路径 = 权 * 路径长度 树的带权路径长度:为所有叶子节点的带权路径之和记做WPL(weight path length) 赫夫曼树huffman-tree或哈夫曼树,又称最优二叉树,