第5章 树（ Tree ）和二叉树 5.1 树的基本概念 5.2 二叉树 5.3 遍历二叉树和线索二叉树 5.4 树和森林 特点：非线性结构，只有一个直接前趋，但可能有多个直接后继（1：n） 5.1 树的基本概念 5.2 二叉树 5.3 遍历二叉树和线索二叉树 5.4 树和森林 5.5 哈夫曼树及其应用

5.1 树的基本概念 举例： 书本的目录 家族的族谱 磁盘文件目录 乒乓球淘汰赛的赛制

5.1 树的基本概念 1. 树的定义 由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是一棵树，被称作这个根结点的子树 。 注1：当n＝0时，这棵树被称为空树。 注2：树的定义具有递归性，即树中还有树。

例如： A C G B D E F K L H M I J 其中：A是根；其余结点分成三个互不相交的子集， 只有根结点的树 有13个结点的树 其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树。

2. 若干术语 根 叶子 森林 有序树 无序树 ——即根结点(没有前趋) ——即终端结点(没有后继) A B C G E I D H F J M L K 2. 若干术语 根 叶子 森林 有序树 无序树 ——即根结点(没有前趋) ——即终端结点(没有后继) ——指m棵不相交的树的集合(例如删除A后的三个子树) ——结点各子树从左至右有序，不能互换（左为第一） ——结点各子树可互换位置。 双亲 孩子 兄弟 堂兄弟 祖先 子孙 ——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即双亲位于同一层的结点（但并非同一双亲） ——即从根到该结点所经分支的结点 ——即该结点下层子树中的结点

2. 若干术语（续） 结点 结点的度 结点的层数 ——即树的数据元素 ——结点挂接的子树个数 （有几个直接后继度就是几） A B C G E I D H F J M L K 2. 若干术语（续） 结点 结点的度 结点的层数 ——即树的数据元素 ——结点挂接的子树个数 （有几个直接后继度就是几） ——从根到该结点的层数（根结点算第一层） 树的度 树的深度 ——所有结点度中的最大值（Max{各结点的度}） ——所有结点中最大的层数（Max{各结点的层数}）

3. 树的逻辑结构 4. 树的存储结构 讨论1：树是非线性结构，该怎样存储？ ————仍然有顺序存储、链式存储等方式。 (特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。 4. 树的存储结构 讨论1：树是非线性结构，该怎样存储？ ————仍然有顺序存储、链式存储等方式。

讨论2：树的顺序存储方案应该怎样制定？ 讨论3：树的链式存储方案应该怎样制定？ 二叉树 可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难（不能唯一复原就没有实用价值）。 讨论3：树的链式存储方案应该怎样制定？ 可用多重链表：一个前趋指针，n个后继指针。 细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？ 缺点：等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。 解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。 二叉树

5. 树的运算 本章重点：二叉树的表示和实现 要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！ （遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。 本章重点：二叉树的表示和实现

5.2 二叉树 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构 为何要重点研究每个结点最多只有两个 “叉” 的树？ 5.2 二叉树 为何要重点研究每个结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树； 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构

二叉树的定义 定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1：2） 基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒（即：二叉树为有序树）。

基本形态： Ф 空二叉树 右子树 根结点只有右子树 只有一个根结点 左子树 根结点只有左子树 左子树 右子树 根结点同时有左右子树

思考：具有3个结点的二叉树可能有几种不同形态？ 5种

两种特殊形态的二叉树 定义1： 满二叉树 ( Full Binary Tree) 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 特点： 叶子只能出现在最后一层； 只有度为0和度为2的结点。 6 2 1 7 5 4 3 8 9 10 11 13 14 15 12 满二叉树

定义2： 完全二叉树 ( Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层 ( 0  h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。 6 2 1 7 5 4 3 8 9 10 11 12 完全二叉树 2 1 6 5 4 3 2 1 5 4 3 6 7 非完全二叉树

特点： 1. 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。

课堂讨论： ① 二叉树是不是树的特殊情况？ 答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。 ② 满二叉树和完全二叉树有什么区别？ 答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。

2. 二叉树的性质 性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）。 （利用二进制性质可轻松求出） 性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）。 1 提问：第i层上至少有 个结点？ 讨论2：深度为k的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出） 2k -1 性质2: 深度为k的二叉树至多有2k -1个结点（k>0）。 提问：深度为k时至少有 个结点？ k

讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？ 性质3: 对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数 n0 必定等于 n2＋1 （即n0=n2+1） 证明： ∵ 二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数) 又∵二叉树中全部结点数n＝B+1 ( 总分支数＋根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个) 三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1 实际意义：叶子数＝2度结点数＋1 A B C G E I D H F J

对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质： 性质4: 具有n个结点的完全二叉树的深度必为[log2n]＋1 证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1<n≤2k-1 或2k-1≤n<2k 三边同时取对数，于是有：k-1≤log2n<k 因为k是整数，所以k=[log2n]+1 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

4. 设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 课堂练习： 1. 树Ｔ中各结点的度的最大值称为树Ｔ的 。 Ａ) 高度 Ｂ) 层次 Ｃ) 深度 Ｄ) 度 √ 2.深度为k 的二叉树的结点总数，最多为 个。 Ａ)２k-1 Ｂ) log2k Ｃ) ２k－１ Ｄ)２k √ 3. 深度为9的二叉树中至少有 个结点。 Ａ)２9 Ｂ)２8 Ｃ)９ Ｄ)２9－1 √ 4. 设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 489 488 1 解：易求出总层数和末层叶子数。总层数k=log2n＋1 =10; 且前9层总结点数为29-1=511 (完全二叉树的前k-1层肯定是满的) 所以末层叶子数为1000-511=489个。 由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。

请注意叶子结点总数≠末层叶子数！ 还应当加上第k-1层（靠右边）的0度结点个数。 分析：末层的489个叶子只占据了上层的245个结点（489/2 ) 上层（k=9)右边的0度结点数还有29-1-245=11个！ 所以， 全部叶子数＝489(末层)＋11(k-1层)=500个。 度为2的结点＝叶子总数－1=499个。 第i层上的满结点数为2i-1 另一法：可先求2度结点数,再由此得到叶子总数。 首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉） 另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2， （共有489/2＝244个）。 所以，全部2度结点数为255(k-2层)＋244(k-1层)=499个； 总叶子数＝2度结点数＋1=500个。

3. 二叉树的存储结构 [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E F G H I T[0]一般不用 [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E F G H I A B C G E I D H F 一、顺序存储结构 将二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。 问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5） 例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。

讨论：不是完全二叉树怎么办？ 答：一律转化为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。 [1] [2] [3] [4] [5] [6] [7] [8] [9] … [16] A B ^ C D … E A B E C D 缺点：①浪费空间；②插入、删除不便

二、链式存储结构 用二叉链表即可方便表示。 二、链式存储结构 用二叉链表即可方便表示。 一般从根结点开始存储。 （相应地，访问树中结点时也只能从根开始） 一个二叉链表的结点分为三个域：如下图 data left_child right_child

例： ^ A B D C E A B E C D

5.3 遍历二叉树和线索二叉树 一、遍历二叉树（Traversing Binary Tree） 5.3 遍历二叉树和线索二叉树 一、遍历二叉树（Traversing Binary Tree） 遍历的定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。 遍历的用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 遍历方法——牢记一种约定，对每个结点的查看都是“先左后右” 。

遍历规则——— 二叉树由根、左子树、右子树构成，定义为 D、 L、R D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，则有三种实现方案： DLR LDR LRD 先 (根)序遍历 中 (根)序遍历 后(根)序遍历

先序遍历 (Preorder Traversal) 前序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则： 访问根结点 (D)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f - / + * a b c d e f

前序遍历二叉树的递归算法 void PreOrder ( BinTreeNode *T ) { if ( T != NULL ) { Visit( T->data); PreOrder ( T->leftChild ); PreOrder ( T->rightChild ); }

中序遍历 (Inorder Traversal) 中序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则： 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f - / + * a b c d e f

中序遍历二叉树的递归算法 void InOrder ( BinTreeNode *T ) { if ( T != NULL ) { InOrder ( T->leftChild ); Visit( T->data); InOrder ( T->rightChild ); }

后序遍历 (Postorder Traversal) 后序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则： 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。 遍历结果 a b c d - * + e f / - - / + * a b c d e f

后序遍历二叉树的递归算法： void PostOrder ( BinTreeNode * T ) { if ( T != NULL ) { PostOrder ( T->leftChild ); PostOrder ( T->rightChild ); Visit( T->data); }

层序遍历 - / + * a b c d e f 层序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则： 从二叉树的根结点开始， 从上至下逐层遍历，每层 中按从左至右的顺序对结点 逐个访问。 遍历结果 - + / a * e f b - c d - / + * a b c d e f

例1： A 先序遍历的结果是： A B D E C B C 中序遍历的结果是： D B E A C D E 后序遍历的结果是： D E B C A 口诀： DLR—先序遍历，即先根再左再右 LDR—中序遍历，即先左再根再右 LRD—后序遍历，即先左再右再根

例2：用二叉树表示算术表达式 先序遍历 + * * / A B C D E 中序遍历 A / B * C * D + E 后序遍历 层序遍历 + * E * D / C A B + * A / E D C B

结点数据类型自定义 typedef struct node{ int data; struct node *lchild,*rchild； } node; node *root; 先序遍历算法 DLR( node *root ) {if (root !=NULL) //非空二叉树 {printf(“%d”,root->data); //访问D DLR(root->lchild); //递归遍历左子树 DLR(root->rchild); //递归遍历右子树 } return(0); } 中序遍历算法 LDR(node *root) {if(root !=NULL) {LDR(root->lchild); printf(“%d”,root->data); LDR(root->rchild); } return(0);} 后序遍历算法 LRD (node *root) {if(root !=NULL) {LRD(root->lchild); LRD(root->rchild); printf(“%d”,root->data); } return(0);}

重点讨论：若已知先序/后序遍历结果和中序遍历结果，能否“恢复”出二叉树？ 例1：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析： ①由后序遍历特征，根结点必在后序序列尾部（即A）； ②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）； ③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。

中序遍历：B D C E A F H G 后序遍历：D E C B H G F A

例2：前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下：

KCG EKCG A B H DF F D E C K G

练习：假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。

二、线索二叉树（Threaded Binary Tree） 普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。 若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。 例如中序遍历结果：B D C E A F H G，实际上已将二叉树转为线性排列，显然具有唯一前趋和唯一后继！

为什么要线索？ 1）二叉树的存储结构中没有反映出某结点的直接前趋结点和直接后继结点是什么。 2）二叉树的二叉链表存储结构中的那些空指针域 可利用。

规 定： 当LTag＝0时,则lchild指向其左孩子； 当LTag＝1时, lchild指向其直接前趋(线索)； 为了避免混淆，给每个结点增加两个标志域： lchild LTag data RTag rchild 当LTag＝0时,则lchild指向其左孩子； 当LTag＝1时, lchild指向其直接前趋(线索)； 当RTag＝0时,则rchild指向其右孩子； 当RTag＝1时, rchild指向其直接后继(线索)；

有关线索二叉树的几个术语： 线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索； 线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化； 线索二叉树：加上线索的二叉树称为线索二叉树。 线索二叉链表：将二叉链表中结点左右孩子空指针域分别指向该结点的直接前驱和后继,称为线索二叉链表。

线索二叉树 二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树： ⑴ 前序线索二叉树 ⑵ 中序线索二叉树 ⑶ 后序线索二叉树 ⑷ 层序线索二叉树

线索二叉树画法 前序线索二叉树： 前序序列为：ABCD

线索二叉树 中序线索二叉树： 中序序列为：BADC

线索二叉树 后序线索二叉树： 后序序列为：BDCA

例：画出以下二叉树对应的中序线索二叉树。 解：该二叉树中序遍历结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行： A B C G D E F H I

对应的中序线索二叉树存储结构如图所示： 注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G root -- A B -- root A C B 1 E F G D I H

练：给定如图所示二叉树T，请画出与其对 应的中序线索二叉树。 28 25 40 55 60 33 08 54 NIL 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。

5.4 树和森林 一、树转换为二叉树 A B C D E F G

⑴加线——树中所有相邻兄弟之间加一条连线。 ⑵去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 ⑶层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

二、森林与二叉树的互相转换 森林 由森林转换的二叉树 分别转换成二叉树 T1 T2 T3 A A F H B C D G I J E K B

森林转换为二叉树 ⑴ 将森林中的每棵树转换成二叉树； ⑵ 从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

二叉树转换为树或森林 ⑴ 加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来； ⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线； ⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

加线 去线 I H G B C D A F E 层次调整 F H G E A I C D B F H G D C E B A I F E D

三、树的遍历 1、树的先根遍历 当树非空时 {访问根结点 依次先根遍历根的各棵 子树} 树先根遍历: ABEFCDG A B C D E F

2、树的后根遍历 A B C D E F G 当树非空时 {依次后根遍历根的各棵 子树 访问根结点} 树后根遍历： EFBCGDA

(a) (b) (c) (d) 练习：分别画出和下列树对应的各二叉树： K J I H G F E C D B A A A A B B C

5.5 哈夫曼树 (Huffman Tree) 路径长度 (Path Length) 两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。

带权路径长度 (Weighted Path Length, WPL) 二叉树的带权路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。

WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35 带权路径长度 达到最小

1、哈夫曼树： 带权路径长度达到最小的二叉树； 在哈夫曼树中，权值大的结点离根最近； 如何构造一颗哈夫曼树？？ 例题：已知权值（7，5，2，4），构造哈夫曼树。

哈夫曼树的构造过程：（重点） （1）初始 （2）合并{2} {4} （3）合并{5} {6} （4）合并{7} {11} 6 7 5 2 4 18 5 6 7 11 5 6 2 4 （3）合并{5} {6} （4）合并{7} {11} 2 4

2、哈夫曼编码 主要用途是实现数据压缩。 设给出一段报文： CASTCASTSATATATASA 1 2、哈夫曼编码 1 1 主要用途是实现数据压缩。 7 2 5 4 A C T S 设给出一段报文： CASTCASTSATATATASA 字符集合是 { C, A, S, T }，各字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 若给每个字符以右上角方式编码，即： A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36

若按各个字符出现的概率不同而给予不等长编码，以它们作为各叶结点上的权值, 建立哈夫曼树。左分支赋 0，右分支赋 1，得哈夫曼编码。

CASTCASTSATATATASA A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。 总编码长度正好等于哈夫 曼树的带权路径长度WPL。 哈夫曼编码: A : 0 T : 10 C : 110 S : 111 110011110 11001111011101001001001110 1 2 4 5 7 哈夫曼编码树

习题 1、在一棵二叉树中，第5层上的结点数最多是（ ）。 8 B. 15 C. 16 D. 32 1、在一棵二叉树中，第5层上的结点数最多是（ ）。 8 B. 15 C. 16 D. 32 2、在一棵二叉树中，度为2的结点数为7，度为1的结点数为7，那么叶结点数为（ ） 6 B. 7 C. 8 D. 9 3、在一棵非空二叉树的中序遍历序列里，根结点的右边只有（ ）结点。 左子树上的部分 B. 左子树上的所有 C. 右子树上的部分 D. 右子树上的所有

4、一棵二叉树由17个结点组成，其中度为2的结点数为7，那么度为1的结点数为（ ） A. 2 B. 3 C. 4 D. 5 5、将一棵树T转换成相应的二叉树BT，那么对树T的先序遍历是对BT的（ ） A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 不确定 6、将一棵树T转换成相应的二叉树BT，那么对树T的后序遍历是对BT的（ ）

7、设森林F中有三棵树，其结点数分别为n1, n2, n3。把该森林转换为二叉树后，该二叉树根结点的左子树和右子树中分别有（ ① ）和（ ② ）个结点。 ① A. n1-1 B. n1 C. n1+1 D. n1+n2 ② A. n1 B. n1+n2 C. n3 D. n2+n3 8、一棵有n个结点的树，把它转换为二叉树后，该二叉树根结点的左子树和右子树中分别有（ ① ）和（ ② ）个结点。 ① A. n-2 B. n-1 C. n+1 D. n+2 ② A. 0 B. n C. n+1 D. n+2

9、已知中序遍历序列为A-B-C-E-F-G-H-D，后序遍历序列为A-B-F-H-G-E-D-C。画出该二叉树，并写出其先序遍历序列。 10、现有权值序列为10、16、20、6、30、24，试构造一棵哈夫曼树,并求WPL值。 11、有五个字符E、D、C、B、A，对应的使用频率分别为0.09、0.12、0.19、0.21、0.39，试通过哈夫曼树为这五个字符进行编码，并写出它们的哈夫曼编码。