哈夫曼编码与最优前缀码
来源：10-3 贪心选择性质的证明
咋啥都不会啊
2018-11-11
bobo老师您好！
我在算法教科书 贪心算法章节中，发现书上写着 “表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意一个结点都有两个儿子”
可是完全二叉树不应该保证第h层，叶子结点集中在最左边吗？
我又去专门找了本算法导论，找到算法导论中描述“最优前缀码总是对应一棵满（full）二叉树”实在是找不到英文版的算法导论。但满二叉树不应该是每层都应该是填满孩子的吗？
我又发现维基百科“A full binary tree is a tree in which every node has either 0 or 2 children.”这个于我所学的满二叉树定义，有点不一样啊。
我是觉得课本是写错了，但我不知道咋改正这句话。所以来求助下老师
算法导论
在学的算法课本
写回答
1回答
-
对于满二叉树这个名词，国内外的一些教材，定义确实有所不同。
国内教材的主流定义是：满二叉树，每一层都是满的; （貌似考研是这么定义的）
而国外教材的主流定义是：每个节点要么没有孩子，有孩子就一定要有俩。
所以：
根据国内教材的主流定义，下图左边是满二叉树，右边不是；
根据国外教材的主流定义，下图左右两边都是满二叉树。
0 0 / \ / \ 1 2 1 2 / \ / \ / \ 3 4 5 6 5 6
对于这种术语上的分歧，不用太纠结。根据上下文，了解真正要表达的意思就好。当然，如果是考试，要找考纲或者考试组织方问清楚。
对于你说上下文，满二叉树都是和国外主流定义统一的。
至于完全二叉树，国内外的定义没有分歧（complete binary tree），你看的书用的术语不准确或者翻译不准确：）
加油！
032018-11-11
相似问题
哈夫曼树是一颗满二叉吗
回答 1
优惠券叠加，得出优惠最大的组合情况
回答 1
Leetcode 152 穷举法时间超时
回答 1
最大堆和最小堆问题
回答 1
动态规划如果两个状态变量如何解决呢？
回答 1