共计 1396 个字符，预计需要花费 4 分钟才能阅读完成。
哈夫曼树
- 在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。
上面的二叉树当中，从根结点 A 到叶子结点 H 的路径，就是 A，B，D，H。
- 在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。
仍然用刚才的二叉树举例子，从根结点 A 到叶子结点 H，共经过了 3 条边，因此路径长度是 3。
- 结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积。
如上图，假设结点 H 的权重是 3，从根结点到结点 H 的路径长度也是 3，因此结点 H 的带权路径长度是 3 X 3 = 9。
- 树的带权路径长度（WPL），即在一棵树中，所有叶子结点的带权路径长度之和。
仍然以这颗二叉树为例，树的路径长度是 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53
哈夫曼树：哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树
- 举个例子，给定权重分别为 1，3，4，6，8 的叶子结点，我们应当构建怎样的二叉树，才能保证其带权路径长度最小？
原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。
下图左侧的这棵树就是一颗哈夫曼树，它的 WPL 是 46，小于之前例子当中的 53：
以下说法错误的是（A）
- A. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
- B. 若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
- C. 已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
- D. 在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
度为二的树就是二叉树。（错）
首先，我们明确一个概念，树的度数是按节点的最大度数来定义的。所以，度为 2 的树要求每个节点最多只能有两棵子树, 并且至少有一个节点有两棵子树；这与二叉树的要求：度不超过 2, 就是说度也可以是 1 或者 0 相矛盾。
其次，二叉树还有一个重要特点：左子树和右子树不一样；而普通的树不分左右子树.
二叉树共有 5 种基本形态
(1) 空二叉树；(2) 只有一个根结点的二叉树；(3) 只有左子树；(4) 只有右子树；(5) 左右子树都有的二叉树
霍夫曼树的结点个数不能是偶数
首先，哈夫曼树只有度为 0 和 2 的节点。这是因为哈夫曼树的构造总是以两棵值最小的树合并，每次合并都是两棵子树，不会有度为 1 的节点。
由二叉树性质，二叉树的节点关系 n0=n2+1，也就是度为 0 的节点数总是比度为 2 的节点数多 1. 若其中一个为奇数那么另外一个就必然是偶数，加起来就还是奇数。
哈夫曼树的构造方法
假设有 6 个叶子结点，权重依次是 2，3，7，9，18，25，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？
第一步：构建森林
我们把每一个叶子结点，都当做树一颗独立的树（只有根结点的树），这样就形成了一个森林：
在上图当中，右侧是叶子结点的森林，左侧是一个辅助队列，按照权值从小到大存储了所有叶子结点。至于辅助队列的作用，我们后续将会看到。
第二步：选择当前权值最小的两个结点，生成新的父结点，不断重复至只有一个节点。
借助辅助队列，我们可以找到权值最小的结点 2 和 3，并根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和：
此时，队列中仅有一个结点，说明整个森林已经合并成了一颗树，而这棵树就是我们想要的哈夫曼树：