设一棵二叉树有 n 个结点，则有 n-1 条边(指针连线) ， 而 n 个结点共有 2n 个指针域

    (Lchild 和 Rchild) ，显然有 n+1 个空闲指针域未用。则可以利用这些空闲的指针域来存放结

    点的直接前驱和直接后继信息。

    为避免混淆,对结点结构加以改进，增加两个标志域，如图所示。用这种结点结构构成

    的二叉树的存储结构；叫做线索链表；指向结点前驱和后继的指针叫做线索；

    2、线索二叉树的构建

    按照某种次序遍历，加上线索的二叉树称之为线索二叉树。线索化二叉树: 二叉树的线

    索化指的是依照某种遍历次序使二叉树成为线索二叉树的过程。

    线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继的过程。

    【2013 年】若 x 是后序线索二叉树中的叶结点，且 x 存在左兄弟结点 Y，则 x 的右

    线索指向的是______。

    A. x 的父结点 b. 以 Y 为根的子树的最左下结点

    c. x 的左兄弟结点 Y d. 以 Y 为根的子树的最右下结点

    【2014 年】若对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分

    别是______。

    A．e、c b．e、a c．d、c d．b、a 考点 14：树和二叉树（★★★）

    1、树转化为二叉树

    对于一般的树，可以方便地转换成一棵唯一的二叉树与之对应。将树转换成二叉树在“孩

    子兄弟表示法”中已给出，其详细步骤是：

    1 加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。

    2 去连线。除最左的第一个子结点外，父结点与所有其它子结点的连线都去掉。

    3 旋转。将树顺时针旋转 450，原有的实线左斜。

    4 整型。将旋转后树中的所有虚线改为实线，并向右斜。

    这样转换后的二叉树的特点是：

    ◆ 二叉树的根结点没有右子树，只有左子树；

    ◆ 左子结点仍然是原来树中相应结点的左子结点，而所有沿右链往下的右子结点均是原来

    树中该结点的兄弟结点。

    由于二叉树和树都可用二叉链表作为存储结构，对比各自的结点结构可以看出，以二叉

    链表作为媒介可以导出树和二叉树之间的一个对应关系。

    ◆ 从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。

    ◆ 从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。

    2、二叉树转换成树

    对于一棵转换后的二叉树，如何还原成原来的树? 其步骤是：

    （1）加虚线。若某结点 i 是其父结点的左子树的根结点，则将该结点 i 的右子结点以及沿右

    子链不断地搜索所有的右子结点，将所有这些右子结点与 i 结点的父结点之间加虚线相连，

    如图(a)所示。

    （2）去连线。去掉二叉树中所有父结点与其右子结点之间的连线，如图(b)所示。

    （3）规整化。将图中各结点按层次排列且将所有的虚线变成实线，如图(c)所示。

    3、森林转换成二叉树

    转换步骤：

    1 将 F={t1, t2,? ,tn} 中的每棵树转换成二叉树。

    2 按给出的森林中树的次序，从最后一棵二叉树开始，每棵二叉树作为前一棵二叉树的

    根结点的右子树，依次类推，则第一棵树的根结点就是转换后生成的二叉树的根结点，如图

    所示。

    4、二叉树转换成森林

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

    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 编码。