哈夫曼编码与最优前缀码

Question

bobo老师您好！

        我在算法教科书 贪心算法章节中，发现书上写着 “表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意一个结点都有两个儿子”

可是完全二叉树不应该保证第h层，叶子结点集中在最左边吗？

我又去专门找了本算法导论，找到算法导论中描述“最优前缀码总是对应一棵满（full）二叉树”实在是找不到英文版的算法导论。但满二叉树不应该是每层都应该是填满孩子的吗？

我又发现维基百科“A full binary tree is a tree in which every node has either 0 or 2 children.”这个于我所学的满二叉树定义，有点不一样啊。

我是觉得课本是写错了，但我不知道咋改正这句话。所以来求助下老师

算法导论

在学的算法课本

Answer 1

liuyubobobo 2018-11-11 18:10:54

对于满二叉树这个名词，国内外的一些教材，定义确实有所不同。

国内教材的主流定义是：满二叉树，每一层都是满的; （貌似考研是这么定义的）

而国外教材的主流定义是：每个节点要么没有孩子，有孩子就一定要有俩。

所以：

根据国内教材的主流定义，下图左边是满二叉树，右边不是；

根据国外教材的主流定义，下图左右两边都是满二叉树。

     0                 0
    / \               / \
  1     2            1   2
 / \   / \              / \
3   4 5   6            5   6

 

对于这种术语上的分歧，不用太纠结。根据上下文，了解真正要表达的意思就好。当然，如果是考试，要找考纲或者考试组织方问清楚。

对于你说上下文，满二叉树都是和国外主流定义统一的。

至于完全二叉树，国内外的定义没有分歧（complete binary tree），你看的书用的术语不准确或者翻译不准确：）

加油！

• 提问者 咋啥都不会啊 #1

  bobo老师，那个书中的应该不可能是完全二叉树吧。

• liuyubobobo 回复 提问者 咋啥都不会啊 #2

  不是。你看的书用的术语不准确或者翻译不准确：）

• 提问者 咋啥都不会啊 回复 liuyubobobo #3

  好的谢谢bobo老师了