上述转换规则是递归的，可以写出其递归算法。以下给出具体的还原步骤。

1 去连线。将二叉树 b 的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连

线全部去掉，得到若干棵孤立的二叉树，每一棵就是原来森林 F 中的树依次对应的二叉树。 2 二叉树的还原。将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树。

5、树的遍历

由树结构的定义可知，树的遍历有二种方法。

(1) 先序遍历：先访问根结点，然后依次先序遍历完每棵子树。如图，先序遍历的次序是：

AbcdEFGIJhK

(2) 后序遍历：先依次后序遍历完每棵子树，然后访问根结点。如图，后序遍历的次序是：

cdbFIJGhEKA

树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。

树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同

【2019 年】若将一棵树 t 转化为对应的二叉树 bt，则下列对 bt 的遍历中，其遍历序列

与 t 的后根遍历序列相同的是（）

A.先序遍历 b.中序遍历 c.后序遍历 d.按层遍历

【2020 年】已知森林 F 及与之对应的二叉树 t，若 F 的先根遍历序列是 a, b, c, d, e, f，中

根遍历序列是 b, a, d, f, e, c 则 t 的后根遍历序列是：

A、b, a, d, f, e, c b、b, d, f, e, c, a c、b, f, e, d, c, a d、f, e, d, c, b, a 考点 15：哈夫曼树(★★★)

1、最优二叉树(huffman 树)

1 结点路径：从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。

2 路径长度：结点路径上的分支数目称为路径长度。

3 结点的带权路径长度：从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积

4权(值)：各种开销、代价、频度等的抽象称呼。

5树的路径长度：从树根到每一个结点的路径长度之和。

2、huffman 树的构造

1 根据 n 个权值{w1, w2, ? ,wn}，构造成 n 棵二叉树的集合 F={t1, t2, ? ,tn}，其中每棵二

叉树只有一个权值为 wi 的根结点，没有左、右子树；

2 在 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二

叉树根结点权值为其左、右子树根结点的权值之和；

3 在 F 中删除这两棵树，同时将新得到的树加入 F 中；

4 重复2、3，直到 F 只含一颗树为止。

构造 huffman 树时，为了规范，规定 F={t1,t2, ? ,tn}中权值小的二叉树作为新构造的二叉树

的左子树，权值大的二叉树作为新构造的二叉树的右子树；在取值相等时，深度小的二叉树

作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。

图是权值集合 w={8, 3, 4, 6, 5, 5}构造 huffman 树的过程。所构造的 huffman 树的 wpL

是： wpL=6x2+3x3+4x3+8x2+5x3+5x3 =79。

3、huffman 编码方法

由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个

字符的 huffman 编码不可能是另一个字符的 huffman 编码的前缀。

若字符集 c={a, b, c, d, e, f}所对应的权值集合为 w={8, 3, 4, 6, 5, 5}，如图所示，则字符

a,b, c,d, e,f 所对应的 huffman 编码分别是：10，010，011，00 ，110，111。

以字符集 c 作为叶子结点，次数或频度集 w 作为结点的权值来构造 huffman 树。规定

huffman 树中左分支代表“0”，右分支代表“1” 。

从根结点到每个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结

点所对应的编码，称之为 huffman 编码。