第6章 树和二叉树 6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林

Presentation on theme: "第6章 树和二叉树 6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林"— Presentation transcript:

1 第6章 树和二叉树 6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林
6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林 6.7 Huffman树及其应用

2 树 和 二 叉 树的ADT 二叉树 树的存储结构 树 树的遍历 树的应用 【本章学习要点】 逻辑结构 存储结构 逻辑结构 存储结构 基本性质
遍历二叉树 线索二叉树 树和森林 树 和 二 叉 二叉树 树的存储结构 树 树的遍历 Huffman树 判定过程 树的应用

3 第6章 树和二叉树 6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林
6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林 6.7 Huffman树及其应用

4 本章学习重点和难点 难点： 重点：(1)二叉树的定义、存储结构、遍历及应用； (2)线索二叉树的定义、存储结构及相应的操作；
(3)树和森林与二叉树之间的相互转化方法； (4)哈夫曼树的建立方法和哈夫曼编码。 难点： （1）二叉树的构造 、应用； （2）线索二叉树的遍历和相应的操作。 4

5 说明：树是递归结构，在树的定义中又用到了树的概念
6.1 树的有关概念 树的概念 树形结构是一种重要的非线性结构。树是n个结点的有限集合，在任一棵非空树中： （1）有且仅有一个称为根的结点。 （2）其余结点可分为m个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。 J I A C B D H G F E K L M 说明：树是递归结构，在树的定义中又用到了树的概念

6 数据对象 D：D是具有相同特性的数据元素的集合。
6.1 树的有关概念 树的概念 ADT Tree{ 数据对象 D：D是具有相同特性的数据元素的集合。 数据关系 R： 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。

7 6.1 树的有关概念 树的概念 ADT Tree{ 数据对象 D： 数据关系 R： 基本操作 P： 查 找 类 插 入 类 删 除 类 }

8 查找类： 6.1 树的有关概念 树的基本操作P Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值
6.1 树的有关概念 树的基本操作P 查找类： Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历

9 InitTree(&T) // 初始化置空树
6.1 树的有关概念 树的基本操作P 插入类： InitTree(&T) // 初始化置空树 CreateTree(&T, definition) // 按定义构造树 Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树

10 DestroyTree(&T) // 销毁树的结构
6.1 树的有关概念 树的基本操作P 删除类： ClearTree(&T) // 将树清空 DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树

11 例如：集合 T={A, B, C, D, E, F, G, H, I, J，K，L，M} A是根，其余结点可以划分为3个互不相交的集合：
6.1 树的有关概念 树的概念 例如：集合 T={A, B, C, D, E, F, G, H, I, J，K，L，M} A是根，其余结点可以划分为3个互不相交的集合： T1={B, E, F，K，L} , T2={C, G} , T3={D, H, I, J，M} 这些集合中的每一集合都本身又是一棵树，它们是A的子树。 J I A C B D H G F E K L M

12 树是一种分枝结构，树中只有根结点没有前趋；其余结点有零个或多个后继；
6.1 树的有关概念 树的概念 从逻辑结构看： 树是一种分枝结构，树中只有根结点没有前趋；其余结点有零个或多个后继； 除根外，其余结点都有且仅一个前趋；都存在唯一一条从根到该结点的路径。 J I A C B D H G F E K L M

13 ***************************
6.1 树的有关概念 树的概念 *************************** 线性结构 非线形结构—树 根结点 (无前驱) 第一个数据元素 (无前驱) 最后一个数据元素 (无后继) 多个叶子结点 (无后继) 其它数据元素 (一个前驱、一个后继) 其它数据元素 (一个前驱、多个后继)

14 例 6.1 树的有关概念 树的应用 1）树可表示具有分枝结构关系的对象 单位行政机构的组织关系 J I A C B D H G F E K
6.1 树的有关概念 树的应用 1）树可表示具有分枝结构关系的对象 例 单位行政机构的组织关系 J I A C B D H G F E K L M

15 6.1 树的有关概念 树的应用 2）树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。 计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。 例 C 文件夹1 文件夹n 文件1 文件2 文件夹11 文件夹12 文件11 文件12

16 （2）凹入表示法 （1）树形表示法 6.1 树的有关概念 树的表示 A B E K L F C G D H M I J J I A C B
6.1 树的有关概念 树的表示 （1）树形表示法 （2）凹入表示法 A B E K L F C G D H M J I J I A C B D H G F E K L M

17 A E D H J K L F G C B M I （3）嵌套集合表示法 （文氏图） 6.1 树的有关概念 树的表示 J I A C B D
6.1 树的有关概念 树的表示 （3）嵌套集合表示法 （文氏图） A E D H J I K L M F G C B J I A C B D H G F E K L M

18 (A(B(E,F), C(G), D(H,I,J))) 第三层
6.1 树的有关概念 树的表示 （4）广义表表示法 (A）第一层 (A(B, C, D)) 第二层 (A(B(E,F), C(G), D(H,I,J))) 第三层 (A(B(E(K,L),F), C(G), D(H(M),I,J))) 第四层 J I A C B D H G F E K L M

19 结点层：根结点的层定义为1，其它依此类推； 树的深度：树中最大的结点层； 结点的度：结点子树的个数； 树的度： 树中最大的结点度；
6.1 树的有关概念 树的有关术语 结点层：根结点的层定义为1，其它依此类推； 树的深度：树中最大的结点层； 结点的度：结点子树的个数； 树的度： 树中最大的结点度； 叶子结点：也叫终端结点，是度为 0 的结点； 第1层 第3层 第2层 第4层 J I A C B D H G F E K L M 树的度为3 树的深度为4

20 6.1 树的有关概念 树的有关术语 分枝结点：度不为0的结点； 有序树：子树有序的树，如：家族树； 无序树：不考虑子树的顺序； 森林：互不相交的树集合； 树和森林的关系： （1）一棵树去掉根 ，其子树构成一个森林； （2）一个森林增加一个根结点成为树。

21 第6章 树和二叉树 6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林
6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林 6.7 Huffman树及其应用

22 树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本节我们主要讨论另一种树型结构——二叉树。
6.2 二叉树 树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本节我们主要讨论另一种树型结构——二叉树。 A F G E D C B

23 6.2 二叉树 6.2.1 二叉树的概念 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构

24 概念：二叉树或为空树，或由根及两颗不相交的左、右子树构成，并且左、右子树本身也是二叉树。
6.2.1 二叉树的概念 概念：二叉树或为空树，或由根及两颗不相交的左、右子树构成，并且左、右子树本身也是二叉树。 特点： 二叉树中每个结点最多有两棵子树；即二叉树每个结点度小于等于2; 左、右子树不能颠倒——有序树; 二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念; A F G E D C B

25 6.2.1 二叉树的概念 A F G E D C B F A G E D B C (a) (b) 二叉树是有左右之分的

26 6.2.1 二叉树的概念 二叉树的基本形态 (c) 右子树空 φ (a)空树 (b)仅有根 (d) 左子树空 (e) 左、右子树均在

27 6.2 二叉树 二叉树的概念 二叉树的性质 二叉树的存储结构

28 性质1 在二叉树的第i(i≥1)层上至多有2i-1个结点。
6.2.2 二叉树的性质 性质1 在二叉树的第i(i≥1)层上至多有2i-1个结点。 证明：用数学归纳法就可以证明。 证明：最多结点数为各层结点个数相加，即 1+2+4+…+2k-1=2k-1 性质2 深度为k的二叉树最多有2k-1个结点。 A B C D E F G I H J k层二叉树

29 6.2.2 二叉树的性质 两种特殊的二叉树 满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树； 完全二叉树：二叉树中所含的 n 个结点和满二叉树中编号为1至n的 结点一一对应。 A G F E D C B (a) K=3的满二叉树 A E D C B (b) G A E D C B (c) (b)完全二叉树 (c) 不是完全二叉树 结论：满二叉树一定是完全二叉树，反之不一定

30 性质3 具有n个结点的完全二叉树的深度为log2n  +1
6.2.2 二叉树的性质 性质3 具有n个结点的完全二叉树的深度为log2n  +1 证明：设所求完全二叉树的深度为k 由性质2和完全二叉树的定义知： 2k-1-1＜n≤2k-1 k-1层的最多结点数 k层的最多结点数 由此可以推出：2k-1 ≤n＜2k A E D C B 取对数得： k-1≤log2n＜k 由于k为整数，故有k-1= log2n  即： k= log2n  +1 性质2:深度为k的二叉树最多有2k-1个结点

31 注意：n1生成n1*1个节点，n2生成n2*2个节点，
6.2.2 二叉树的性质 性质4 对任意二叉树T，如果度数为0结点数为n0,度数为1结点数为n1,度数为2结点数为n2，则n0=n2+1。 证明：二叉树T的结点总数 n=n0+n1+n （1） 二叉树的分支结点总数 b=n （2） 由于分支结点是由度为1和度为2的结点生成的 即分支结点总数b=n1+2*n （3） 注意：n1生成n1*1个节点，n2生成n2*2个节点， 根结点不由任何结点产生 A B C D E F G I H J 由(1)(2)(3)得 求得：n0=n2+1

32 性质5:若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点:
6.2.2 二叉树的性质 性质5:若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点: (1) 若 i=1，则该结点是二叉树的根，无双亲，否则， 编号为 i/2 的结点为其双亲结点； (2) 若 2i>n，则该结点无左孩子，否则，编号为 2i的 结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为 2i+1 的结点为其右孩子结点。 2i+2 i/2 2i+1 2i i+1 i

33 通过性质5把非线性结构轻易转化成了线性结构。
6.2.2 二叉树的性质 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 i=1 只有根结点 编号i=4 双亲为i/2 =2 左子树为2i=8 右子树为2i+1=9 编号i=5 双亲为i/2 =2 左子树为2i= 右子树为2i+1=11 i=8,2i>n无左子树 通过性质5把非线性结构轻易转化成了线性结构。

34 6.2 二叉树 6.2.1 二叉树的概念 二叉树的性质 二叉树的存储结构

35 6.2.3 二叉树的存储结构 二叉树的顺序存储表示 二叉树的链式存储表示

36 采用一维数组，按层序顺序依次存储二叉树的每一个结点。 如下图所示：
6.2.3 二叉树的存储结构 二叉树的顺序存储表示 2i+2 i/2 2i+1 2i i+1 i (1)完全（或满）二叉树 采用一维数组，按层序顺序依次存储二叉树的每一个结点。 如下图所示： A B C D E F G I H J A B C D E F G H I J 利用性质5实现线性结构和非线性结构的灵活转换。

37 通过虚设部分结点，使其变成相应的完全二叉树。 A
6.2.3 二叉树的存储结构 二叉树的顺序存储表示 (2)一般二叉树 通过虚设部分结点，使其变成相应的完全二叉树。 A B C E G J A B C E G J A B C E G J

38 说明：顺序存储方式对于畸形二叉树，浪费较大空间
6.2.3 二叉树的存储结构 二叉树的顺序存储表示 (3)特殊的二叉树 A B C J 说明：顺序存储方式对于畸形二叉树，浪费较大空间

39 lch rch data C 语言的类型描述如下: typedef Struct node { DataType data;
6.2.3 二叉树的存储结构 二叉树的链式存储表示 二叉链表存储： 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域 lch rch data C 语言的类型描述如下: typedef Struct node { DataType data; Struct node *lch,*rch; }BinTNode;

40 root A ∧ B n 个结点的二叉树中， 有多少个空链接域？ 6.2.3 二叉树的存储结构 二叉树的链式存储表示 C ∧ ∧ E ∧
二叉链表图示 ∧ D A ∧ C ∧ ∧ E ∧ ∧ F B root A F E D C B 二叉树 n 个结点的二叉树中， 有多少个空链接域？

41 root 性质6：n 个结点的二叉树中，共有 n+1 个空指针域。 A ∧ B 证：n个结点总的指针域数2n 除了根结点外，其余n-1个结点
6.2.3 二叉树的存储结构 二叉树的链式存储表示 性质6：n 个结点的二叉树中，共有 n+1 个空指针域。 二叉链表图示 ∧ D A ∧ C ∧ ∧ E ∧ ∧ F B root 证：n个结点总的指针域数2n 除了根结点外，其余n-1个结点 都是由指针域指出的结点； 所以，剩余的结点数即 空指针域个数为： 2n-（n-1）=n+1 二叉链表的缺点是很难找到结点的双亲

42 结点结构: lch data rch parent C 语言的类型描述如下: 6.2.3 二叉树的存储结构 二叉树的链式存储表示
三叉链表（带双亲指针的二叉链表）:三叉链表中每个结点包含四个域：数据域、左指针域、右指针域、双亲指针域 结点结构: lch data rch parent C 语言的类型描述如下: typedef Struct node { DataType data; Struct node *lch,*rch,*parent; };

43 root lch data rch parent 6.2.3 二叉树的存储结构 二叉树的链式存储表示--三叉链表 A B C D E F A

44 第6章 树和二叉树 6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林
6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林 6.7 Huffman树及其应用

45 6.3 二叉树的遍历 二叉树的遍历方法 二叉树的遍历算法

46 遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。
二叉树的遍历方法 遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。 访问：访问是指对结点进行各种操作的简称，包括输出、查找、修改等等操作。 遍历是各种数据结构最基本的操作，许多其它的操作可以在遍历基础上实现。

47 ？ “遍历”是任何类型均有的操作： 线性结构的遍历：只有一条搜索路径(因为每个结点均只有一个后继)；
二叉树的遍历方法 “遍历”是任何类型均有的操作： 线性结构的遍历：只有一条搜索路径(因为每个结点均只有一个后继)； 非线性结构的遍历：二叉树是非线性结构，则存在如何遍历即按什么样的搜索路径遍历的问题。 如何访问二叉树的每个结点， 而且每个结点仅被访问一次？ ？

48 先上后下的按层次遍历； 先左（子树）后右（子树）的遍历； 先右（子树）后左（子树）的遍历。 6.3 .1 二叉树的遍历方法
对“二叉树”而言，可以有三条搜索路径： 先上后下的按层次遍历； 先左（子树）后右（子树）的遍历； 先右（子树）后左（子树）的遍历。

49 B F D G 6.3 .1 二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树
A F G E D C B 令：L：遍历左子树 T：访问根结点 R：遍历右子树 有六种遍历方法： T L R，L T R，L R T， T R L，R T L，R L T 约定先左后右,有三种遍历方法： T L R、L T R、L R T ，分别称为 先序遍历、中序遍历、后序遍历

50 中序遍历序列： 图示 F G D B 例 D ,B ,G ,E ,A ,C ,F 6.3 .1 二叉树的遍历方法 中序遍历（ L T R ）
若二叉树非空 （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树 例 中序遍历右图所示的二叉树 中序遍历序列： D ,B ,G ,E ,A ,C ,F 图示

51 练习 d e c b f a + * / - 中序 a,+,b,*,c,-,d,-,e,/,f 6.3 .1 二叉树的遍历方法
中序遍历下图所示的二叉树 d e c b f a + * / - 中序 a,+,b,*,c,-,d,-,e,/,f

52 先序遍历序列：A,B,D,E,G,C,F 图示 B F D G 例 6.3 .1 二叉树的遍历方法 先序遍历（T L R） A
若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； 先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按 T L R 的顺序遍历左子树 （3）先序遍历右子树：即按 T L R 的顺序遍历右子树 例 先序遍历序列：A,B,D,E,G,C,F 图示

53 练习 d e c b f a + * / - 先序 -,+,a,*,b,-,c,d,/,e,f 6.3 .1 二叉树的遍历方法
先序遍历下图所示的二叉树 d e c b f a + * / - 先序 -,+,a,*,b,-,c,d,/,e,f

54 后序遍历序列： D,G,E,B,F,C,A 图示 B F D G 例 6.3 .1 二叉树的遍历方法 后序遍历（ L T R ） A
若二叉树非空 （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点 后序遍历右图所示的二叉树 （1）后序遍历左子树：即按 L R T 的顺序遍历左子树 （2）后序遍历右子树：即按 L R T 的顺序遍历右子树 （3）访问根结点A 例 后序遍历序列： D,G,E,B,F,C,A 图示

55 练习 d e c b f a + * / - 后序 a,b,c,d,-,*,+,e,f,/,- 6.3 .1 二叉树的遍历方法
后序遍历下图所示的二叉树 d e c b f a + * / - 后序 a,b,c,d,-,*,+,e,f,/,-

56 二叉树的遍历方法 按层遍历 层次遍历序列： A,B,C,D,E,F,G A F G E D C B

57 课后思考：按层遍历算法 按层遍历引入了队列作为辅助工具。 算法思想为： （1）将二叉树根入队列；
二叉树的遍历方法 按层遍历 按层遍历引入了队列作为辅助工具。 算法思想为： （1）将二叉树根入队列； （2）将队头元素出队列，并判断此元素是否有左右孩子，若有，则将它的左右孩子入列，否则转（3）； （3）重复步骤（2），直到队列为空 。 A F G E D C B 课后思考：按层遍历算法

58 6.3 二叉树的遍历 二叉树的遍历方法 二叉树的遍历算法

59 上面先序遍历的定义等价于： 6.3.2 二叉树的遍历算法 先序遍历（T L R）的定义 若二叉树非空 （1）访问根结点；
二叉树的遍历算法 先序遍历（T L R）的定义 若二叉树非空 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树； 上面先序遍历的定义等价于： 若二叉树为空，结束 ——基本项（也叫终止项） 若二叉树非空 ——递归项 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；

60 void prev (BinTree T) { if (T) T { visit(T->data)； prev(T->lch);
二叉树的遍历算法 先序遍历递归算法 void prev (BinTree T) { if (T) { visit(T->data)； prev(T->lch); prev(T->rch); } 先序序列为 + * a – b c / d e 称为前缀表达式 ∧ e ∧ ∧ a ∧ + * / /\ d /\ - T ∧ b ∧ ∧ c ∧ a*(b-c)+d/e

61 T void Mid (BinTree T) + { if (T) {Mid(T->lch); visit( T->data)；
二叉树的遍历算法 ∧ e ∧ ∧ a ∧ + * / /\ d /\ - T ∧ b ∧ ∧ c ∧ 中序遍历递归算法 void Mid (BinTree T) { if (T) {Mid(T->lch); visit( T->data)； Mid(T->rch); } 中序序列为 a * b – c+ d / e 称为中缀表达式 a*(b-c)+d/e

62 T + void Post(BinTree T) { if (T) * {Post(T->lch); Post(T->rch);
二叉树的遍历算法 后序遍历递归算法 ∧ e ∧ ∧ a ∧ + * / /\ d /\ - T ∧ b ∧ ∧ c ∧   void Post(BinTree T) { if (T) {Post(T->lch); Post(T->rch); visti( T->data)； } 后序序列为 a b c – * d e / + 称为后缀表达式 a*(b-c)+d/e

63 中序序列为： a * b – c+ d / e BiTNode *GoFarLeft(BiTree T, Stack *S)
二叉树的遍历算法 中序遍历的非递归算法 BiTNode *GoFarLeft(BiTree T, Stack *S) {//找到左子树的最左下的结点 if (!T ) return NULL; while (T->lch ){ Push(S, T); T = T->lch; } return T; d b e a * - / c + 中序序列为： a * b – c+ d / e

64 void Inorder_I(BiTree T) { Stack *S; t = GoFarLeft(T, S); // 找到最左下的结点
二叉树的遍历算法 中序遍历的非递归算法 void Inorder_I(BiTree T) { Stack *S; t = GoFarLeft(T, S); // 找到最左下的结点 while(t){ visit(t->data); if (t->rch) t = GoFarLeft(t->rch, S); else if ( !StackEmpty(S )) // 栈不空时退栈 t = Pop(S); else t = NULL; // 栈空表明遍历结束 } // while }// Inorder_I

65 遍历二叉树的过程实质: 是把二叉树的结点进行线性排列的过程。
6.4 遍历的应用 遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作： （1）求结点的双亲、孩子结点、结点的层次； （2）求孩子结点； （3）求结点的层次； （4）遍历过程中生成结点，建立二叉树； 遍历二叉树的过程实质: 是把二叉树的结点进行线性排列的过程。

66 6.4 遍历的应用 6.4.1 遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价

67 递归建立二叉树 我们按先序递归遍历的思想来建立二叉树。 其建立思想如下： （1）建立二叉树的根结点； （2）先序建立二叉树的左子树；
遍历的基本应用 二叉树的生成 递归建立二叉树 我们按先序递归遍历的思想来建立二叉树。 其建立思想如下： （1）建立二叉树的根结点； （2）先序建立二叉树的左子树； （3）先序建立二叉树的右子树。

68 t=(bitree*)malloc(sizeof(bitree)); t->data=x; t->lch=creat();
遍历的基本应用 二叉树的生成 二叉树的生成的递归算法 bitree *creat() { bitree *t; t=(bitree*)malloc(sizeof(bitree)); t->data=x; t->lch=creat(); t->rch=creat(); return t; }

69 int countleaf(bitree t ,int num) { if(t!=NULL)
遍历的基本应用 求二叉树的叶子数。 算法思想：采用任何遍历方法，遍历时判断访问的结点是不是叶子，若是则叶子数加1。 int countleaf(bitree t ,int num) { if(t!=NULL) {if((t->lch==NULL) &&(t- >rch)==NULL)) num++; num=countleaf(t->lch,num); num=countleaf(t->rch,num); } return num;

70 rh=treedepth(t->rch); if(lh>=rh) h=lh+1; else h=rh+1; }
遍历的基本应用 求二叉树的深度 算法思想：从第一层的根结点开始往下递推可得到。 下面给出后序遍历求二叉树深度的递归算法： Int treedepth(bitree *t) {int h,lh,rh; if(t==NULL) h=0; else { lh=treedepth(t->lch); rh=treedepth(t->rch); if(lh>=rh) h=lh+1; else h=rh+1; } return h; }

71 遍历的应用 6.4.1 遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价

72 B D C D D 6.4.2二叉树的遍历与存储结构的应用 二叉树的遍历与存储结构之间的转化
问题：给定一个遍历序列，能否唯一确定一棵二叉树？ 例如：先序序列为ABCD,其二叉树的结构是什么？ A D C B A C D B A C B D 答案是 不唯一

73 关键（1）确定二叉树的根结点； 给定某两种遍历序列能否唯一确定一棵二叉树？ 给定中序和后序 给定中序和前序 唯一确定一棵二叉树
6.4.2二叉树的遍历与存储结构的应用 构造二叉树 关键（1）确定二叉树的根结点； （2）结点的左右次序。 给定某两种遍历序列能否唯一确定一棵二叉树？ 给定中序和后序 给定中序和前序 给定先序和后序不能唯一确定一棵二叉树 唯一确定一棵二叉树 唯一确定一棵二叉树

74 给定二叉树先序和中序遍历序列，如何构造二叉树？ 先序：1 2 4 6 3 5 7 8 中序：2 6 4 1 3 7 5 8 例
6.4.2二叉树的遍历与存储结构的应用 构造二叉树 给定二叉树先序和中序遍历序列，如何构造二叉树？ 先序： 中序： 例 1 左2 右4 1 前3578 中3758 2 4 6 前3578 中3758 前 246 中 264 6 前 46 中64

75 根据给定的遍历次序构造二叉树，并给出先序遍历序列。 中序遍历序列：a,+,b,*,c,-,d,-,e,/,f
6.4.2二叉树的遍历与存储结构的应用 构造二叉树 作业 根据给定的遍历次序构造二叉树，并给出先序遍历序列。 中序遍历序列：a,+,b,*,c,-,d,-,e,/,f 后序遍历序列：a,b,c,d,-,*,+,e,f,/,-

76 先序:-,+,a,*,b,-,c,d,/,e,f 答案： e d c b f a + * / - 6.4.2二叉树的遍历与存储结构的应用
构造二叉树 e d c b f a + * / - 答案： 先序:-,+,a,*,b,-,c,d,/,e,f

77 6.4 遍历的应用 6.4.1 遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价

78 （2）它们都是非空的，且左右子树分别具有相同结构。 “形状”相同
二叉树的相似与等价 二叉树的相似与等价的含义 两株二叉树具有相同结构指： （1）它们都是空的 ； （2）它们都是非空的，且左右子树分别具有相同结构。 “形状”相同 定义具有相同结构的二叉树为相似二叉树。 相似且相应结点包含相同信息的二叉树称为 等价二叉树。

79 if ( ISEMPTY(t1) && ISEMPTY(t2) )//二叉树空 x = 1 ;
二叉树的相似与等价 判断两株二叉树是否等价 int EQUAL( t1 , t2 ) BTREE t1 , t2 ; { int x ; x = 0 ; if ( ISEMPTY(t1) && ISEMPTY(t2) )//二叉树空 x = 1 ; else if ( !ISEMPTY( t1 ) && ! ISEMPTY( t2) ) //二叉树不空 if ( DATA( t1 ) == DATA( t2 ) ) if ( EQUAL( LCHILD( t1 ) , LCHILD( t2 ) ) ) x= EQUAL( RCHILD( t1) , RCHILD( t2) ) return( x ) ; } /* EQUAL */

80 二叉树的相似与等价 二叉树的复制 BTREE COPY( BTREE oldtree ) { BTREE temp ; if ( oldtree != NULL ) temp = new Node ; temp -> lch = COPY( oldtree->lch ) ; temp -> rch = COPY( oldtree->rch ) ; temp -> data = oldtree->data ; return ( temp ); } return ( NULL ) ;

81 结论： “遍历”是二叉树各种操作的基础； 可以在遍历过程中对结点进行各种操作， 对于一棵已知树可求结点的双亲； 求结点的孩子结点；
6.4. 遍历的应用 结论： “遍历”是二叉树各种操作的基础； 可以在遍历过程中对结点进行各种操作， 对于一棵已知树可求结点的双亲； 求结点的孩子结点； 判定结点所在层次； 树的深度； 生成二叉树 ……

82 6.5 线索二叉树 线索二叉树的表示 二叉树的线索化 线索二叉树的遍历

83 6.5 线索二叉树 线索二叉树的表示 二叉树的线索化 线索二叉树的遍历

84 如何利用二叉链表的空指针域？ 6.5 线索二叉树 知识回顾
6.5 线索二叉树 知识回顾 二叉链表是一种单向链接结构，从一个结点出发，沿着指针走向只能到达其子孙结点，却无法返回其祖先结点。 正像线性链表可以从单向链表发展到双向链表一样，二叉链表也可以采用双向链表。 遍历二叉树就是按一定的规则将二叉树中的结点排列成一个线性序列，即对一个非线性结构进行线性化的过程。 有n个结点的二叉链链表中必定存在n+1个空链域。 如何利用二叉链表的空指针域？

85 6.5 线索二叉树 线索二叉树的概念 考虑利用这些空链域来存放遍历后结点的前驱和后继信息，这就是线索二叉树构成的思想。 采用既可以指示其前驱又可以指示后继的双向链接结构的二叉树被称为线索二叉树。 利用空链域存储信息 链式存储结构——线索链表

86 lch ltag data rtag rch typedef struct node {datatype data;
线索二叉树的表示 线索链表的结点结构 lch ltag data rtag rch typedef struct node {datatype data; struct node *lch,*rch; int ltag,rtag; }threadbithptr; 其中：ltag，rtag为两个标志域 lch域指示结点的左孩子 lch域指示结点的前驱 ltag= rch域指示结点的右孩子 rch域指示结点的后继 rtag=

87 遍历二叉树的结果是求得结点的一个线性序列;
线索二叉树的表示 线索二叉树 e d c b f a + * / - 遍历二叉树的结果是求得结点的一个线性序列; 先序遍历序列: -,+,a,*,b,-,c,d,/,e,f 中序遍历序列：a,+,b,*,c,-,d,-,e,/,f 后序遍历序列：a,b,c,d,-,*,+,e,f,/,-

88 用线索保存遍历的信息 充分利用剩余的n+1个空指针域
6.5 线索二叉树 线索二叉树 用二叉链表作为二叉树的存储结构是，只能找到结点的左右孩子信息，不能得到结点在某种遍历次序中的前驱和后继结点，这种信息只能在遍历的过程中才能得到。 用线索保存遍历的信息 充分利用剩余的n+1个空指针域

89 遍历指向该线性序列中的“前驱”和“后继” 的指针，称作“线索”。
二叉树的线索化 二叉树存储结构--线索链表 遍历指向该线性序列中的“前驱”和“后继” 的指针，称作“线索”。 b a e f d c g g NUl 1 d e NUL 1 a f 中序 a,e,b,f,c,t,d 1 b 1 c 线索链表

90 线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，叫线索链表。
线索二叉树的表示 线索二叉树的相关概念 线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，叫线索链表。 线索：指向前驱和后继的指针。 线索二叉树：采用双向链接结构表示的二叉树。 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。

91 6.5 线索二叉树 线索二叉树的表示 二叉树的线索化 线索二叉树的遍历

92 常在二叉树线索链表上添加一个头结点，令其lchild指向二叉树的根结点，其rchild域指向中序遍历时访问的最后一个结点。
二叉树的线索化 关于线索二叉链表的头结点的设定方法1 常在二叉树线索链表上添加一个头结点，令其lchild指向二叉树的根结点，其rchild域指向中序遍历时访问的最后一个结点。 令二叉树中序序列中的第一个结点的lchild和最后一个结点的rchild均指向头结点。 说明：由此方法设定的头结点类似为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。

93 构成双向 循环线索链表 g head ->lch指向根结点 head ->rch指向中序 最后一个结点 e d a f c b
二叉树的线索化 关于线索二叉链表的头结点的设定方法1 b a e f d c g head head ->lch指向根结点 head ->rch指向中序 最后一个结点 1 g 中序遍历的 第一个结点和 最后一个结点 都指向头结点 1 d e 1 a f 构成双向 循环线索链表 1 b 1 c 线索链表 中序 a,e,b,f,c,t,d

94 类似线性链表，为每个线索树增加一个头结点,并设: head->lch = T (二叉树的根) ;
二叉树的线索化 关于线索二叉树的头结点的设定方法2 类似线性链表，为每个线索树增加一个头结点,并设: head->lch = T (二叉树的根) ; head->rch = head ; head->ltag = 0 ; head->rtag = 0 ; 当线索树为空时： head->lch = head ; head->rch = head ; head->ltag = 1 ; head->rtag = 0; A B C D E F G I H J T A B C D E F G I H J HEAD (b)带头结点的线索树 (a) 不带头结点的线索树

95 如何在中序线索树找指定结点的后继？ 在中序线索树中查找中序后继的方法 （1）当结点没有右子树时，即：
二叉树的线索化 查找---在线索树中找节点---中序后继 在中序线索树中查找中序后继的方法 （1）当结点没有右子树时，即： 当p->rtag =1 时，p->rch 既为所求后继结点（线索）。 （2）当结点有右子树时，即： 当p->rtag = 0 时，p的后继结点为p的右子树的最左下结点。 如何在中序线索树找指定结点的后继？

96 threadbithptr * Inordernext(bithptr *p) { threadbithptr *q;
二叉树的线索化 在中序线索树中找结点*p的中序后继 threadbithptr * Inordernext(bithptr *p) { threadbithptr *q; if (p->rtag==1) return(p->rch); else } p q (a) p的右子树为空

97 while(q->ltag==0) q=q->lch; p的右子树不空 6.5.2 二叉树的线索化
二叉树的线索化 在中序线索树中找结点*p的中序后继 threadbithptr * Inordernext(bithptr *p) { else // *p右子树非空 { q=p->rch; //从*p的右子树开始找 while(q->ltag==0) q=q->lch; // 找右子树的“最左下”结点 return(q); } p q q (b) p的右子树不空

98 threadbithptr * Inordernext(bithptr *p) { threadbithptr *q;
二叉树的线索化 在中序线索树中找结点*p的中序后继 threadbithptr * Inordernext(bithptr *p) { threadbithptr *q; if (p->rtag==1) //*P的右子树为空 return(p->rch); else // *P右子树非空 { q=p->rch; while(q->ltag==0) // 找右子树的“最左下”结点 q=q->lch; return(q); } } //查找右子树中最左下的结点。 q (b) p p q (a)

99 如何在中序线索树找 指定结点的前趋？ 在线索二叉树中查找中序前驱的方法 （1）当结点没有左子树时，即：
二叉树的线索化 查找--在线索二叉树树中找结点--中序前驱 在线索二叉树中查找中序前驱的方法 （1）当结点没有左子树时，即： 当p->ltag =1 时，p->lch 既为所求前驱结点（线索）。 （2）当结点有左子树时，即： 当p->ltag = 0 时，p的前驱结点为p的左子树的最右下结点。 如何在中序线索树找 指定结点的前趋？

100 if (p->ltag = = 0 ) while(q->rtag = = 0) q = q->rch ;
二叉树的线索化 在中序线索树中找结点*p的中序前趋 分析：(1) 当p->ltag = 1时，p->lch 既为所求（线索）。 (2) 当p->ltag = 0时，q为p的左子树的最右下结点。 threadbithptr INPRE(threadbithptr p) threadbithptr p ; {threadbithptr q ; q=p->lch ; } p q p q if (p->ltag = = 0 ) while(q->rtag = = 0) q = q->rch ; p的左孩子为空 p的左孩子不空

101 6.5 线索二叉树 6.5.1 线索二叉树的表示 二叉树的线索化 线索二叉树的遍历

102 g 中序遍历的 第一个结点和 e d 最后一个结点 都指向根结点 a f c b 中序 a,e,b,f,c,t,d
线索二叉树的遍历 b a e f d c g thrt 中序遍历的 第一个结点和 最后一个结点 都指向根结点 1 g 1 d e 1 a f 1 b 1 c 线索链表 中序 a,e,b,f,c,t,d

103 TraverseInthread(threadbithptr *p) {if (p!=Null) {
线索二叉树的遍历 遍历中序线索二叉树的递归算法 TraverseInthread(threadbithptr *p) {if (p!=Null) { while (p->ltag==0)//找中序序列的开始结点 p=p->lch; do { visit(p->data) p=Inordernext(p);//找*p的中序后继结点 } while (p!=Null); }

104 g 中序遍历的 第一个结点和 e d p 最后一个结点 都指向根结点 a f c b 中序 a,e,b,f,c,t,d
线索二叉树的遍历 b a e f d c g thrt 中序遍历的 第一个结点和 最后一个结点 都指向根结点 1 p g 1 d e 1 a f 1 b 1 c 线索链表 中序 a,e,b,f,c,t,d

105 6.5.3 线索二叉树的遍历 遍历中序线索二叉树的非递归算法
线索二叉树的遍历 遍历中序线索二叉树的非递归算法 TraverseInthread(biThrTree Thrt，Status(*visit)){ //中序遍历线索二叉树T的非递归算法 T指向线索二叉树的头结点，头结点的lch指向根结点，中序的最后一个结点指向根结点。每次判定结点的ltag和rtag p=Thrt->lch; //p指向二叉树真正的根结点 while(p!=Thrt){ while (p->ltag==0） p=p->lch; //找中序序列的开始结点 if(!visit(p->data)) // 图中的a被访问 while (p->rtag==1)&&p->rch!=Thrt{ //循环结束条件，此时p指向结点e // p->rch!=T表明p不是是中序遍历的最后一个结点 p=p->rch; //p指向图中的e结点 visit(p->data) }//图中e被访问 p=p->rch;//右线索指向后继结点，此时p指向图中的f结点 // 重复以上过程，直到有线索指向根为止 } return(ok); }}

106 是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。
线索二叉树的遍历 中序线索化二叉树 线索化的实质: 是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。

107 图示 如何建立线索链表？ 在中序遍历过程中修改结点的左、右指针域 保存当前访问结点的“前驱”和“后继”信息。
线索二叉树的遍历 中序线索化二叉树 如何建立线索链表？ 在中序遍历过程中修改结点的左、右指针域 保存当前访问结点的“前驱”和“后继”信息。 遍历过程中，附设指针pre, pre指向刚访问过的结点。P指向当前访问结点。即pre是p的前驱 类似线性表的两个相邻的结点， 修改相应的pre域和next域 图示

108 void InThreading(BiThrTree p) { InThreading(p->lchild); // 左子树线索化
线索二叉树的遍历 中序线索化二叉树 void InThreading(BiThrTree p) { InThreading(p->lchild); // 左子树线索化 Thread p // 线索化根结点 InThreading(p->rchild); // 右子树线索化 } // InThreading 具体见下页：

109 void InThreading(BiThrTree p) { if (p) { // 对以p为根的非空二叉树进行线索化
线索二叉树的遍历 中序线索化二叉树 void InThreading(BiThrTree p) { if (p) { // 对以p为根的非空二叉树进行线索化 InThreading(p->lchild); // 左子树线索化 if (!p->lchild) // 建前驱线索 { p->LTag = Thread; p->lchild = pre; } if (!pre->rchild) // 建后继线索 { pre->RTag = Thread; pre->rchild = p; } pre = p; // 保持 pre 指向 p 的前驱 InThreading(p->rchild); // 右子树线索化 } // if } // InThreading

110 Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { // 构建中序线索链表
线索二叉树的遍历 构建中序线索化二叉树 Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { // 构建中序线索链表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode)))) exit (OVERFLOW); Thrt->LTag = 0; Thrt->RTag =1; Thrt->rchild = Thrt; // 添加头结点，指向自身 if (!T) Thrt->lchild = Thrt; //二叉树空，指向自身

111 Thrt->lchild = T; pre = Thrt;//头结点Thrt指向T InThreading(T);
线索二叉树的遍历 中序线索化二叉树 else { Thrt->lchild = T; pre = Thrt;//头结点Thrt指向T InThreading(T); pre->rchild = Thrt; // 处理最后一个结点 pre->RTag = 1; //pre->rch 与Thrt->rch 互链接 Thrt->rchild = pre; } return OK; } // InOrderThreading

112 线索二叉树的遍历 在二叉树中一般不讨论结点的插入与删除，原因是其插入与删除的操作与线性表相同，所不同的是需要详细说明操作的具体要求。 而在线索树中结点的插入与删除则不同，因为要同时考虑修正线索的操作。 线索树的缺点： 在插入和删除时，除了修改指针外，还要相应地修改线索。

113 (1)若S的右子树为空，则直接插入;如图所示
线索二叉树的遍历 例 将结点 R 插入作为结点 S 的右孩子结点： (1)若S的右子树为空，则直接插入;如图所示 插入前 （ S的右子树为空） S R S R (a) 插入后

114 (2)若S的右子树非空，则R插入后原来S的右子树作为R的右子树。
线索二叉树的遍历 例 (2)若S的右子树非空，则R插入后原来S的右子树作为R的右子树。 (b) S R 插入前 （右子树非空） S R W 插入后

115 例 6.5.3 线索二叉树的遍历 线索二叉树的右插入算法:将结点 R 插入作为结点 S 的右孩子
线索二叉树的遍历 例 线索二叉树的右插入算法:将结点 R 插入作为结点 S 的右孩子 S R Void RINSERT (threadbithptr S , R ) { if ( S->rtag = 1) // 右子树空 { R->rtag = 1; R->ltag = 1 ; R->rch = S->rch ; //R的中序后继是原来S的后继 R->lch = S ; //R的中序前驱是S S->rtag = 0 ; //修改s的右标识 S->rch = R ; //S的右孩子是R } else//右子树非空 { w = Inordernext ( S ) ; R=w->lch ; //R的中序后继是w S R W

116 线索二叉树的左插入算法:将结点 R 插入作为结点 S 的左孩子
线索二叉树的遍历 思考题： 线索二叉树的左插入算法:将结点 R 插入作为结点 S 的左孩子

117 a b c d e - × + / 先缀表达式能否唯一确定二叉树 按给定先缀的表达式建立相应的二叉树 应用举例
6.5.3 遍历二叉树和线索二叉树 按给定先缀的表达式建立相应的二叉树 应用举例 已知表达式的先缀表示式 -×+ a b c / d e a b c d e - × + / 先缀表达式能否唯一确定二叉树 表达式=（第一操作数）（运算符）（第二操作数）

118 a b c d e - × + / 对于二元运算符： 左右子树不空； 操作数为叶子结点； 运算符为分支结点； 应用举例
6.5.3 遍历二叉树和线索二叉树 应用举例 按给定的表达式建立相应的二叉树 a b c d e - × + / 对于二元运算符： 左右子树不空； 操作数为叶子结点； 运算符为分支结点；

119 方法：从左到右扫描后缀表达式，遇到操作符 用对前面的操作数建立二叉树，以此类推。 例如：后缀表达式a b + c * d e / -
6.5.3 遍历二叉树和线索二叉树 应用举例 按给定后缀的表达式建立相应的二叉树 方法：从左到右扫描后缀表达式，遇到操作符 用对前面的操作数建立二叉树，以此类推。 例如：后缀表达式a b + c * d e / - a b c d e - × + /

120 结合原表达式转化成后缀表达式（利用栈）和后缀转化成二叉树两种方法实现。
6.5.3 遍历二叉树和线索二叉树 应用举例 按给定的原表达式建立相应的二叉树 原表达式（a + b ) * c - ( d / e ) 思想： 结合原表达式转化成后缀表达式（利用栈）和后缀转化成二叉树两种方法实现。 a b c d e - × + /

121 + + + / + 分析表达式和二叉树的关系: a+b (a+b)×c × c a b a b a+b×c (a+b)×c – d/e -
6.5.3 遍历二叉树和线索二叉树 分析表达式和二叉树的关系: a+b (a+b)×c × + + c a b a b a+b×c (a+b)×c – d/e - + × / a × + c d e b c a b

122 6.6 树和森林 树的操作是可以通过 对二叉树的操作来实现

123 6.6 树和森林 树的存储结构 树、森林与二叉树的转换 树和森林的遍历

124 采用一组连续空间存储树的结点,通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。
6.6.1 树的存储结构 双亲表示法 采用一组连续空间存储树的结点,通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。 结点数 9 A 0 B 1 C 1 D 2 E 2 F 3 G 5 H 5 I 5 1 2 3 4 5 6 7 8 data parent A C H G D F B E I

125 树结构: data parent 双亲表示类型定义 #define MAX 100 Typedef struct PTnode{
6.6.1 树的存储结构 双亲表示法 树结构: data parent 双亲表示类型定义 #define MAX 100 Typedef struct PTnode{ //结点结构 Elem data; int parent; //双亲位置域 } PTnode

126 树结构: typedef struct { PTNode nodes [MAX_TREE_SIZE]; int r, n;
6.6.1 树的存储结构 双亲表示法 树结构: typedef struct { PTNode nodes [MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数 } PTree;

127 r=0 n=9 6.6.1 树的存储结构 孩子链表表示法 对树的每个结点用线性链表存贮它的孩子结点 data firstchild
child next ∧ A B C D E F G H I A C H G D F B E I 2 3 ∧ 4 5 ∧ 6 ∧ 7 8 9 ∧ 结点的孩子结点链表 树的孩子链表图示 孩子链表表示法示意图

128 找一个结点的孩子十分方便，但要找一个结点的双亲则要遍历整个结构
6.6.1 树的存储结构 孩子链表表示法 对树的每个结点用线性链表存贮它的孩子结点 孩子结点结构: 双亲结点结构: child next data firstchild typedef struct { Elem data; ChildPtr firstchild; // 孩子链的头指针 } CTBox; typedef struct CTNode { int child; struct CTNode *next; } *ChildPtr; 找一个结点的孩子十分方便，但要找一个结点的双亲则要遍历整个结构

129 r=0 n=9 6.6.1 树的存储结构 双亲孩子表示法 结合双亲表示法和孩子表示法 0 1 2 3 4 5 6 7 8 9 I
data parent link r=0 n=9 A C H G D F B E I 9 ∧ A B 1 C D 2 E F 3 G 5 H I 2 3 ∧ 4 5 ∧ 6 ∧ 7 8 9 ∧ 结点的孩子结点链表 带双亲孩子链表示意图

130 用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和右边下一个兄弟结点。
6.6.1 树的存储结构 树的二叉链表---孩子兄弟表示法 用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和右边下一个兄弟结点。 结点结构: firstchild data firstbrother typedef struct CSNode{ Elem data; struct CSNode *firstchild, *firstbrother; } CSNode, *CSTree;

131 与二叉树的存储表示一样，但含义不同 6.6.1 树的存储结构 树的二叉链表---孩子兄弟表示法
用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和右边第一个兄弟结点。 A I H G F E C D B 树的孩子兄弟表示法图示 B的第一个孩子结点 B的右兄弟结点 ∧ 与二叉树的存储表示一样，但含义不同 A C H G D F B E I

132 A B C E D F G A B C D E F G root A B C E D F G 二叉树：左、右子树 树： 左是孩子，右是兄弟
6.6.1 树的存储结构 树的二叉链表---孩子兄弟表示法 root A B C E D F G A B C D E F A B C E D F G G 二叉树：左、右子树 树： 左是孩子，右是兄弟

133 把树和二叉树对应起来 如何把树的转化成二叉树？ 树和二叉树的存储表示方式是一样的，只是左右孩子表达的逻辑关系不同： 二叉树：左右孩子；
6.6.1 树的存储结构 树的二叉链表---孩子兄弟表示法 树和二叉树的存储表示方式是一样的，只是左右孩子表达的逻辑关系不同： 二叉树：左右孩子； 树的二叉链表：第一个孩子结点和右边第一个兄弟结点。 把树和二叉树对应起来 如何把树的转化成二叉树？

134 6.6 树和森林 树的存储结构 树、森林与二叉树的转换 树和森林的遍历

135 图示 树转换为二叉树的方法 （1）在所有兄弟结点之间加一条连线； （2）对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线；
树、森林与二叉树的转换 树转换为二叉树的方法 树转换为二叉树的方法 （1）在所有兄弟结点之间加一条连线； （2）对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线； 图示

136 例 将树转换为二叉树 6.6.2 树、森林与二叉树的转换 树转换为二叉树的方法 每棵树对应的二叉树 E I K J L A C B D F
树、森林与二叉树的转换 树转换为二叉树的方法 例 将树转换为二叉树 E I K J L A C B D F G H A B C D F H G E I J L K 每棵树对应的二叉树

137 （2）将各二叉树的根结点视为兄弟连在一起。
树、森林与二叉树的转换 森林转换为二叉树的方法 （1）将森林中的每一树转换二叉树； （2）将各二叉树的根结点视为兄弟连在一起。 图示

138 森林转换为二叉树 例 6.6.2 树、森林与二叉树的转换 森林转换为二叉树的方法 包含3棵树的森林 森林对应的二叉树 每棵树对应的二叉树 A
树、森林与二叉树的转换 森林转换为二叉树的方法 森林转换为二叉树 例 A B D F H G E C I J L K F H G E I K J L A C B D 包含3棵树的森林 A B C D I J L K F H G E 森林对应的二叉树 每棵树对应的二叉树

139 森林和二叉树的对应关系 设森林 F = ( T1, T2, …, Tn ); T1 = (root，t11, t12, …, t1m);
树、森林与二叉树的转换 森林和二叉树的对应关系 设森林 F = ( T1, T2, …, Tn ); T1 = (root，t11, t12, …, t1m); 二叉树 B =(Node(root), LBT, RBT ); 由森林转换成二叉树的转换规则为: 若 F = Φ，则 B = Φ； 否则， 由 ROOT( T1 ) 对应得到 Node(root)； 由 (t11, t12, …, t1m ) 对应得到 LBT； 由 (T2, T3,…, Tn ) 对应得到 RBT。

140 由 Node(root) 对应得到 ROOT( T1 )； 由LBT 对应得到 ( t11, t12, …，t1m)；
树、森林与二叉树的转换 森林和二叉树的对应关系 由二叉树转换为森林的转换规则为： 若 B = Φ， 则 F = Φ； 否则， 由 Node(root) 对应得到 ROOT( T1 )； 由LBT 对应得到 ( t11, t12, …，t1m)； 由RBT 对应得到 (T2, T3, …, Tn)。

141 任何一棵与树对应的 二叉树,其右子树必为空 树或森林与二叉树之间有一个自然的一一对应的关系。 任何一个森林或树可以唯一地对应到一棵二叉树；
树、森林与二叉树的转换 树或森林与二叉树之间有一个自然的一一对应的关系。 任何一个森林或树可以唯一地对应到一棵二叉树； 任何一棵二叉树可以唯一地对应到一个森林或一棵树 任何一棵与树对应的 二叉树,其右子树必为空

142 图示 （1）如果结点X是其双亲Y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与Y用连线连起来； （2）去掉所有双亲到右孩子的连线
树、森林与二叉树的转换 二叉树到树、森林的转换 （1）如果结点X是其双亲Y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与Y用连线连起来； （2）去掉所有双亲到右孩子的连线 图示

143 6.6 树和森林 树的存储结构 树、森林与二叉树的转换 树和森林的遍历

144 与二叉树的遍历类似，树的遍历也是从根结点出发，对树中各个结点访问一次且仅进行一次。
树和森林的遍历 与二叉树的遍历类似，树的遍历也是从根结点出发，对树中各个结点访问一次且仅进行一次。 由于一个结点可以有两棵以上的子树，因此一般不讨论中根遍历。 对树进行遍历可有两条搜索路径： （1）从左到右 （2）按层次从上到下。 树的按层次遍历类似于二叉树的按层次遍历；

145 先根图示 先根顺序 访问根结点 ； 先根顺序遍历T1 ; 先根顺序遍历T2 ; … 先根顺序遍历Tk ; 6.6.3 树和森林的遍历
树和森林的遍历 树的先根遍历 T1 T2 Tk n T … 先根顺序 访问根结点 ； 先根顺序遍历T1 ; 先根顺序遍历T2 ; … 先根顺序遍历Tk ; 先根图示

146 void preordertre(CSnode * root) /* root 一般树的根结点 */ { if(root!=NULL)
树和森林的遍历 树的先根遍历 树的先根遍历递归该算法如下： void preordertre(CSnode * root) /* root 一般树的根结点 */ { if(root!=NULL) { visit(root->data); /* 访问根结点 */ preordertre( root-> firstchild); preordertre( root-> nextsilbing); }

147 后根图示 后根顺序 后根顺序遍历T1 ; 后根顺序遍历T2 ; … 后根顺序遍历Tk ; 访问根结点 ； 6.6.3 树和森林的遍历
树和森林的遍历 树的后根遍历 T1 T2 Tk n T … 后根顺序 后根顺序遍历T1 ; 后根顺序遍历T2 ; … 后根顺序遍历Tk ; 访问根结点 ； 后根图示

148 visit(root->data);
树和森林的遍历 树的后根遍历 树的后根遍历递归算法： void postordertre(CSnode * root) /* root 一般树的根结点 */ { if (root!=NULL ) { postordertre( root-> firstchild); postordertre( root-> nextsilbing); visit(root->data); }

149 层次遍历 自上而下 自左到右 依次访问树中的每个结点 6.6.3 树和森林的遍历 树的按层次遍历 T1 T2 Tk n T … A C B
树和森林的遍历 树的按层次遍历 T1 T2 Tk n T … 层次遍历 自上而下 自左到右 依次访问树中的每个结点 A C B D E I H J G K

150 （2）出队一个结点便立即访问之，然后将它的非空的第一个孩子结点进队，同时将它的所有非空兄弟结点逐一进队；
树和森林的遍历 树的按层次遍历 算法思想： 算法运用队列做辅助存储结构。其步骤为： （1）首先将树根入队列； （2）出队一个结点便立即访问之，然后将它的非空的第一个孩子结点进队，同时将它的所有非空兄弟结点逐一进队； （3）重复（2），这样便实现了树按层遍历。

151 树和森林的遍历 练习 树的的转换和遍历 A C B D E I H J G K

152 B C D E F G H I J K 森林由三部分构成： 1．森林中第一棵树的根结点； 2．森林中第一棵树的子树森林；
树和森林的遍历 B C D E F G H I J K 森林的组成部分 森林由三部分构成： 1．森林中第一棵树的根结点； 2．森林中第一棵树的子树森林； 3．森林中其它树构成的森林。

153 先序遍历 若森林不空，则 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中(除第一棵树之外)其
树和森林的遍历 森林的先序遍历 先序遍历 若森林不空，则 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中(除第一棵树之外)其 余树构成的森林。 即：依次从左至右对森林中的 每一棵树进行先根遍历。

154 中序遍历森林中(除第一棵树之外)其 余树构成的森林。
树和森林的遍历 森林的中序遍历 中序遍历 若森林不空，则 中序遍历森林中第一棵树的子树森林； 访问森林中第一棵树的根结点； 中序遍历森林中(除第一棵树之外)其 余树构成的森林。 即依次从左至右对森林中的 每一棵树进行后根遍历。

155 森林和二叉树的对应关系 在森林转换成二叉树过程中： 森林 二叉树 第一棵树的子树森林 转换成 左子树 剩余树森林 转换成 右子树；
树和森林的遍历 森林和二叉树的对应关系 在森林转换成二叉树过程中： 森林 二叉树 第一棵树的子树森林 转换成 左子树 剩余树森林 转换成 右子树；

156 对树和森林的遍历可以调用二叉树对应的遍历算法
树和森林的遍历 树的遍历和二叉树遍历的对应关系 ？ 树 森林 二叉树 先根遍历 先序遍历 先序遍历 后根遍历 中序遍历 中序遍历 对树和森林的遍历可以调用二叉树对应的遍历算法

157 B C D E F G H I J K 森林由三部分构成： 1．森林中第一棵树的根结点； 2．森林中第一棵树的子树森林；
树和森林的遍历 B C D E F G H I J K 知识回顾 森林由三部分构成： 1．森林中第一棵树的根结点； 2．森林中第一棵树的子树森林； 3．森林中其它树构成的森林。

158 return(max(h1+1, h2)); 求树的深度的算法： int TreeDepth(CSTree T) {//T是森林
树和森林的遍历 求树的深度的算法： int TreeDepth(CSTree T) {//T是森林 if(!T) return 0; else { h1 = TreeDepth( T->firstchild ); //森林中第一棵树的子树森林的深度 h2 = TreeDepth( T->firstbrother); //森林中其他子树构成的森林的深度，与T在同一层 } } // TreeDepth return(max(h1+1, h2));

159 第6章 树和二叉树 6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林
6.1 树的有关概念 6.2 二叉树 6.3 二叉树的遍历 6.4 遍历的应用 6.5 线索二叉树 6.6 树和森林 6.7 Huffman树及其应用

160 HUFFMAN编码又称哈夫曼编码，是一种可变长编码方式，是由美国数学家David Huffman1952年在麻省理工攻读博士时所发明的;
编码的原理： (1)将使用次数多的代码转换成长度较短的代码; (2)保持编码的唯一可解性。

161 哈夫曼编码的理论依据：是变字长编码理论; 在变字长编码中，按编码输入信息符号出现的统计概率，给输出码字分配以不同的字长;
6.7 Huffman树及其应用 Huffman介绍 哈夫曼编码的理论依据：是变字长编码理论; 在变字长编码中，按编码输入信息符号出现的统计概率，给输出码字分配以不同的字长; Huffman 编码是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。 Huffman树是二叉树的一种特殊转化形式。Huffman树又称最优二叉树，是一种带权路径长度最短的二叉树。

162 结点的路径长度：从根结点到该结点的路径上分支的数目; 树的路径长度：树中每个结点的路径长度之和。
6.7 Huffman树及其应用 Huffman树的相关概念 结点的路径长度：从根结点到该结点的路径上分支的数目; 树的路径长度：树中每个结点的路径长度之和。 在结点数相同的条件下，完全二叉树是路径最短的二叉树。 1 2 3 4 6 2 3 4 7 6 5 8 1 非完全二叉树 完全二叉树

163 WPL(T) = wklk (对所有叶子结点)。
6.7 Huffman树及其应用 Huffman树的相关概念 树的带权路径长度定义： 树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)。 “最优树”或Huffman树。 在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”或Huffman树。

164 6.7 Huffman树及其应用 Huffman树的相关概念 最优二叉树或哈夫曼树（Huffman） ：带权路径长度 WPL 最小的二叉树，称该二叉树为最优二叉树或哈夫曼树。在哈夫曼树中，权值大的结点离根最近。 哈夫曼树 2 4 5 7 2 4 7 5 7 5 2 4 (a) WPL=36 (b) WPL=46 (c) WPL=35

165 6.7 Huffman树及其应用 带权路径长度 A 4 7 5 2 C D B A 7 5 2 4 B C D
B C D WPL=7*1+5*2+2*3+4*3=35 WPL=7*2+5*2+2*2+4*2=36 4 7 5 2 A B C D C D 4 7 5 2 A B WPL=7*3+5*3+2*1+4*2=46 WPL=7*1+5*2+2*3+4*3=35

166 为什么S = n + 1 ？ 内结点 增长树 外结点 如内结点数为 n，则外结点 S = n + 1 6.7 Huffman树及其应用

167 内结点路径长度I ：从根结点到每个内结点的路长的总合。 外结点路径长度E：从根结点到每个内结点的路长的总和。
6.7 Huffman树及其应用 Huffman树的相关概念 内结点路径长度I ：从根结点到每个内结点的路长的总合。 外结点路径长度E：从根结点到每个内结点的路长的总和。 I = 2×1+3×2+1×3 = 11 E = 1×2+5×3+2×4 = 25 结论：如内结点路径长度为I，则外结点路径长度 E = I＋2×n

168 1． 根据给定的n个权值 ，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。
6.7 Huffman树及其应用 Huffman树的构造 构造Huffman树的步骤： 1． 根据给定的n个权值 ，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。 2． 设F是由这n棵二叉树构成的集合，在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和； 3． 从F中删除这两颗树，并将新树加入F； 4． 重复 2、3，直到F中只含一颗树为止； 这棵树便是Huffman树

169 例 6.7 Huffman树及其应用 Huffman树的构造 构造以W=（5，14，40，26，10）为权的哈夫曼树。
要使二叉树WPL小,就须在构造 树时, 将权值大的结点靠近根。 26 5 10 14 40 15 5 10 14 40 26 95 55 40 55 14 5 10 15 29 26 29 26 15 5 10 29 14 5 10 15 40 26 40

170 n个结点需要进行n-1次合并，每次合并都产生一个新的结点，所以最终的Huffman树共有2n-1个结点。

171 6.7 Huffman树及其应用 图示

172 CreatHuffmanTree （tree） hufmtree tree[ ]
{　　int i,j,p1,p2; float small1,small2,f; 　　　for (i=0; i<m; i++) //初始化 　　　　　{ tree[i].weight=0.0; 　　　　　tree[i].lch=-1; 　　　　　tree[i].rch=-1; 　　　　　tree[i].parent=-1; 　　　　} } Huffman 算法 typedef struct { float weight; int lch,rch,parent; }hufmtree; hufmtree tree[m];

173 //把合并后的结点放入向量tree[n]~tree[m} {p1=0;p2=0; // 两个根结点在向量tree中的下标
6.7 Huffman树及其应用 void InputWeight(HuffmanTree T) 　　{//输入权值 　　　float w; 　　　int i; 　　　for (i=0; i<n;i++) 　　　　{ printf(“\n输入第%d个权值:”,i+1); 　　　　　scanf(“%f”,&w); 　　　　　tree[i].weight=w;} 　　} for(i=n; i<m; i++) //把合并后的结点放入向量tree[n]~tree[m} {p1=0;p2=0; // 两个根结点在向量tree中的下标 small1=maxval;small2=mavval; //maxval 是float类型的最大值

174 for (j=0;j<i-1;j++) //选择两个权值最小的结点
6.7 Huffman树及其应用 　　　 　for (j=0;j<i-1;j++) //选择两个权值最小的结点 　　　if(tree[j].parent==-1)  　　　　if(tree[j].weight<small1) 　　　　　{ 　　　　　　small2=small1;//改变最小权，次小权及其位置 　　　　　　small1=tree[j].weight;//找出最小的权值 　　　　　　p2=p1; 　　　　　　p1=j;  　　　　　} 　　　　else if(tree[j].weight<small2) 　　　　　{small2=tree[j].weight;//改变次小权及位置 　　　　　　p2=j;} 　　}//选择结束

175 //新生成的结点放在向量tree[i+1] tree[i].lch=p1+1; tree[i].rch=p2+1;
6.7 Huffman树及其应用 tree[p1].parent=i+1; tree[p2].parent=i+1; //新生成的结点放在向量tree[i+1] tree[i].lch=p1+1; tree[i].rch=p2+1; tree[i].weight= tree[p1]. weight + tree[p1]. weight； } }//huffmantree

176 前缀编码指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
6.7 Huffman树及其应用 Huffman编码 前缀编码指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。 等长编码：这类编码的二进制串的长度取决于电文中不同的字符个数，假设需传送的电文中只有四种字符，只需两位字符的串便可分辨。(01,10,11,00) 不等长编码:即各个字符的编码长度不等。(0,10,110,011,)

177 利用哈夫曼树构造一组最优前缀编码。主要用途是实现数据压缩。在某些通讯场合，需将传送的文字转换成由二进制字符组成的字符串。
6.7 Huffman树及其应用 Huffman编码 Huffman树在通讯编码中的一个应用 利用哈夫曼树构造一组最优前缀编码。主要用途是实现数据压缩。在某些通讯场合，需将传送的文字转换成由二进制字符组成的字符串。 方法： 利用哈夫曼树构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，使所传电文的总长度最短。

178 不等长编码的好处：可以使传送电文的字符串的总长度尽可能地短。对出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。
6.7 Huffman树及其应用 Huffman编码 不等长编码的好处：可以使传送电文的字符串的总长度尽可能地短。对出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。 邮局发电报： 例 原文 电文（二进制字符串） 原文 发送方 接收方

179 例 6.7 Huffman树及其应用 Huffman编码 要传输的原文为ABACCDA 等长编码 A：00 B：01 C：10 D：11
接收方： 转换成 A的编码是 B、D的前缀 AAAACCDA BBCCDA ……

180 前缀编码： 任何字符编码不是其它字符编码的前缀
6.7 Huffman树及其应用 Huffman编码 前缀编码： 任何字符编码不是其它字符编码的前缀 设 A：0 B： C： D：111 发送方：将ABACCDA 转换成 总长度是13,所得的译码是唯一的

181 ①概率统计（如对一幅图像，或m幅同种类型图像作灰度信号统计），得到n个不同概率的信息符号。
6.7 Huffman树及其应用 Huffman编码—具体步骤 ①概率统计（如对一幅图像，或m幅同种类型图像作灰度信号统计），得到n个不同概率的信息符号。　 ②将n个信源信息符号的n个概率，按概率大小排序。　 ③将n个概率中，最后两个小概率相加，这时概率个数减为 n-1个。　 ④将n-1个概率，按大小重新排序。

182 ⑤重复③，即将新排序后的最后两个小概率再相加，相加和与其余概率再排序。
6.7 Huffman树及其应用 Huffman编码—具体步骤 ⑤重复③，即将新排序后的最后两个小概率再相加，相加和与其余概率再排序。　 ⑥如此反复重复n-2次，得到只剩两个概率序列。　 ⑦以二进制码元（0，1）赋值，构成哈夫曼码字 编码结束。　

183 Huffman 编码的特点 哈夫曼码字长度和信息符号出现概率大小次序正好相反，即大概信息符号分配码字长度短，小概率信息符号分配码字长度长。

184 哈夫曼编码广泛应用于各种数据压缩技术中，且仍不失为熵编码中的最佳编码方法。
6.7 Huffman树及其应用 Huffman编码--- 采用Huffman 编码时注意的问题 ①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力。 ②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。 采用Huffman 编码的应用 哈夫曼编码广泛应用于各种数据压缩技术中，且仍不失为熵编码中的最佳编码方法。

185 1）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉 树； 2）将该二叉树所有左分枝标记0，所有右分枝标记1；
6.7 Huffman树及其应用 利用二叉树设计前缀编码： 某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，利用二叉树设计一种不等长编码： 例 1）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉 树； 2）将该二叉树所有左分枝标记0，所有右分枝标记1； 3）从根到叶子结点路径上标记作为叶子结点所对应 字符的编码；

186 1 a、b、 c、d、 e、 f、 g、 h， 5、29、 7、 8、 14、 23、 3、11 构造以字符使用频率
6.7 Huffman树及其应用 利用二叉树设计前缀编码： a、b、 c、d、 e、 f、 g、 h， 5、29、 7、 8、 14、 23、 3、11 构造以字符使用频率 作为权值的Huffman树 1 100 58 42 29 29 a: 0001 b: 10 c: 1110 d: 1111 e: 110 f: 01 g: 0000 h: 001 19 23 14 15 8 11 7 8 3 5 图1 总编码长度等于Huffman树的带权路径长度WPL。 Huffman编码是一种有前缀编码。解码时不会混淆。

187 1 不同的规则获得的编码是不同的 a、b、 c、d、 e、 f、 g、 h， 5、29、 7、 8、 14、 23、 3、11
6.7 Huffman树及其应用 利用二叉树设计前缀编码： a、b、 c、d、 e、 f、 g、 h， 5、29、 7、 8、 14、 23、 3、11 29 19 58 42 100 15 8 7 3 5 11 23 14 1 a: 0110 b: 10 c: 1110 d: 1111 e: 110 f: 00 g: 0111 h: 010 图2 不同的规则获得的编码是不同的

188 由于Huffman编码需要扫描两次，第一次是统计数字，第二次是编码写文件，大大影响了速度。
有人发明了enhanced Huffman aglorithm。这种算法只扫描一遍文件，动态产生Huffman树，即每读n个字节就重新编码一次Huffman树，以达到提高速度的目的。在解码的过程中使用动态还原技术。

189 在求得某些判定问题时，利用Huffman树获得最佳判定算法。
编制一个将百分制转换成五分制的程序。可用二叉树描述判定过程。 例 a  80 a  90 不及格 良好 中等 及格 优秀 a  60 a  70 在求得某些判定问题时，利用Huffman树获得最佳判定算法。

190 例 6.7 Huffman树及其应用 设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下： 其判定过程:
分数 比例数 其判定过程: 转换一个分数所需的比较次数= 从根到对应结点的路径长度 转换10000个分数所需的总比较次数=  (0.05      4） a  80 a  90 不及格 良好 中等 及格 优秀 a  60 a  70 二叉树的 带权路径长度

191 本章小结 树 和 二 叉 树的ADT 二叉树 树和森林 树的应用 逻辑结构 存储结构 二叉树逻辑结构 二叉树存储结构 顺序存储
二叉树基本性质 二叉树的遍历 二叉树的应用 线索二叉树 顺序存储 二叉链表 树 和 二 叉 先根遍历 中根遍历 后根遍历 层次遍历 二叉树 树的存储结构 树和森林的转换与二叉树的转换 树和森林的遍历 树和森林 Huffman树 Huffman编码 判定过程 树的应用

192 本章小结 熟练掌握二叉树的结构特性，了解相应的证明方法。（完全二叉树、满二叉树、哈夫曼树） 熟悉二叉树的各种存储结构的特点及适用范围。
　熟练掌握二叉树的遍历二叉树方法及二叉树的构造方法。 熟练掌握各种遍历策略的递归算法和主要的非递归算法；

193 本章小结 深入理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系；
　灵活运用遍历算法实现二叉树的其它操作； 深入理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系； 熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法； 深入理解线索二叉树与双向循环链表之间的联系。

194 本章小结 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。 熟练掌握 1 至 2 种建立二叉树和树的存储结构的方法。
学会编写实现树的各种操作的算法。 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。

195 【习题】 将树转换为二叉树 例 F I A B D H G C E I A C B D H G F E

196 以二叉链表为存储结构，写出求二叉树结点总数的算法
【习题】 例 以二叉链表为存储结构，写出求二叉树结点总数的算法 分析： 求结点数的递归定义为： (1)若为空树，结点数为0 (2)若只有根结点，则结点数为1； (3)否则，结点数=1+左子树结点数+右子树结点数

197 【习题】 typedef char DataType;//定义DataType类型 　typedef struct node{ 　　　　DataType data; 　　　　struct node *lch, *rch;//左右孩子子树 　　}BinTNode; //结点类型 　typedef BinTNode *BinTree ;//二叉树类型 int Node(BinTree T) 　　{//算结点数 　　　if(T) 　　　　if (T->lchild==NULL)&&(T->rch==NULL) 　　　　　return 1; 　　　　else return Node(T->lch)+Node(T->rch)+1; 　　　else return 0; 　　}

198 设： w i = { 2 , 3 , 4 , 11 }， 例 求：∑wj · l j（加权路径长度）
【习题】 设： w i = { 2 , 3 , 4 , 11 }， 求：∑wj · l j（加权路径长度） 例 2 3 4 11 (b) 11 4 2 3 (a) 11 4 2 3 (c) （a）11×1＋4×2＋2×3＋3×3=34 （b）2×1＋3×2＋4×3＋11×3=53 （c）2×2＋11×2＋3×2＋4×2=40

199 化整为 { 2, 7, 4, 5 }，以它们为各叶结点上的权值，建立霍夫曼树。左分支赋 0，右分支赋 1，
【习题】 设给出一段报文： CAST CAST SAT AT A TASA 对字符集合 { C, A, S, T }进行Huffman编码 例 因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18 }。 化整为 { 2, 7, 4, 5 }，以它们为各叶结点上的权值，建立霍夫曼树。左分支赋 0，右分支赋 1， 得霍夫曼编码(变长编码)。

200 编码(变长编码)： A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。
【习题】 编码(变长编码)： A : T : C : S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。 18 11 6 7 5 2 4 1 A T C S 霍夫曼编码树