数据结构 第六章（学习笔记四（哈夫曼树））
哈夫曼树的定义
设二叉树具有n个带权值的叶节点，那么从根节点到各个叶节点的路径长度与相应节点权值的乘积的和，叫做二叉树的 带权路径长度。
权： 权代表的是叶子结点的数据信息，是具体的值，也就是结点所储存的值。
具有最小带权路径长度的二叉树称为 哈夫曼树 (也称最优数)。
相同的叶节点构造出不同的二叉树
构造哈夫曼树
构造哈夫曼树的 原则：
① 权值越大的叶节点越靠近根节点；
② 权值越小的叶节点越远离根节点。
构造哈夫曼树的 过程：
哈夫曼编码
规定哈夫曼树中的 左分支为0，右分支为1 ，则从根节点到每个节点所经过的分支对应的0和1组成的序列便为该节点对应字符的编码，这样的编码称为 哈夫曼编码。
在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的 前缀。
例如，有4个字符的编码如下：100, 001, 0，1
这是哈夫曼编码吗？显然是错误的，因为0是001的前缀，不可能。
所以哈夫曼编码也称为 前缀编码。
分析：选D。
分析：选 A。哈夫曼树一定是二叉树，但不一定是完全二叉树。