《数据结构》课程PPT教学课件（2012）第6章 树和二叉树 Tree & Binary Tree（3/4）

第二次上机内容预告： （三个方案由易到难，可自选，参见自测题集实验二资料) 方案一：二叉树的建立和遍历 具体内容：先生成一棵二叉树，再用中序遍历方式打印每个 结点值，并统计其叶子结点的个数。 方案二：哈夫曼树的建立和编码器的实现 具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫 曼编码。 方案三：哈夫曼编/译码器的设计与实现 具体内容：参见严题集P149实习5.2要求，或参见自测卷

1 方案一：二叉树的建立和遍历 具体内容：先生成一棵二叉树，再用中序遍历方式打印每个 结点值，并统计其叶子结点的个数。 方案二：哈夫曼树的建立和编码器的实现 具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫 曼编码。 方案三：哈夫曼编/译码器的设计与实现 具体内容：参见严题集P149 实习5.2要求，或参见自测卷 第二次上机内容预告： （三个方案由易到难，可自选，参见自测题集实验二资料）

第6章树和二叉树 CTree Binary Tree) 6.1 树的基本概念 二叉树的运算 6.2 二叉树 6.3遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用

2 第6章 树和二叉树 （Tree & Binary Tree） 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 二叉树的运算

6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 Traversing Binary Tree 遍历—指按某条搜索路线遍访每个结点且不重复。 常用的有先序、中序和后序遍历，还有层次遍历。 6.3.2线索二叉树 Threaded Binary Tree 用二叉链表法存储包含个结点的二叉树，结点的指针区域中 会有n+1个空指针。 可以用它来存放当前结点的直接前驱和后继等线索，以加快查 找速度

3 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 遍历——指按某条搜索路线遍访每个结点且不重复。 常用的有先序、中序和后序遍历，还有层次遍历。 Traversing Binary Tree 6.3.2 线索二叉树 用二叉链表法存储包含n个结点的二叉树，结点的指针区域中 会有n+1个空指针。 可以用它来存放当前结点的直接前驱和后继等线索，以加快查 找速度。 Threaded Binary Tree

NIL和NULL的值都是0， 例：【2000年计算机考研题】给定 区别何在？ T,请画出与其对应的中序线 在Delphir中NIL用来标 28 记空指针，Nul用来表 示空的Variant型变量 33 NIL 或是ASCII码为0的字符 比如用于标记字符串结 6008 束。 在C/C++中定义的宏 NULL不加区别的包括 了以上两种含义。 解：因为中序遍历序列是：55402560 对应线索树应当按此规律连线，即在原 可见Object Pascal的 语法要比C/C++严谨得 多

4 例：【 2000年计算机考研题】给定如图所示二叉树 T，请画出与其对应的中序线索二叉树。 28 25 40 55 60 33 08 54 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。 NIL NIL NIL和NULL的值都是0, 区别何在？ 在Delphi中NIL用来标 记空指针，Null用来表 示空的Variant型变量 或是ASCII码为0的字符， 比如用于标记字符串结 束。 在C/C++中定义的宏 NULL不加区别的包括 了以上两种含义。 可见Object Pascal的 语法要比C/C++严谨得 多

线索二叉树的生成（递归算法见教材P134-135) 设计技巧 依某种顺序遍历二叉树，对悔个结点，判断其左指 针是否为空，以及其前驱结点的右指针是否为空。 每次只修改前驱结点的右指针（后继)和本结点的左指针（前 驱)，参见算法6.6。 线索二叉树的遍历（无需堆栈） 难点：在线索化二叉树中，并不是每个结点都能 直接找到其后继的，当标志为0时，则需要通过一 定运算才能找到它的后继

5 线索二叉树的生成（递归算法见教材P134-135） 设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指 针是否为空，以及其前驱结点的右指针是否为空。 每次只修改前驱结点的右指针（后继）和本结点的左指针（前 驱），参见算法6.6。 线索二叉树的遍历（无需堆栈） 难点：在线索化二叉树中，并不是每个结点都能 直接找到其后继的，当标志为0时，则需要通过一 定运算才能找到它的后继

6.4树和森林 6.4.1树和森林与二叉树的转换 6.4.2树和森林的存储方式 6.4.3树和森林的遍历

6 6.4 树和森林 6.4.1 树和森林与二叉树的转换 6.4.2 树和森林的存储方式 6.4.3 树和森林的遍历

6.4.1 树和森林与二叉树的转换 孩子—兄弟 表示法 讨论1： 树如何转为二叉树？ 转换步骤： step1:将树中同一结点的兄弟相连； 加线 step2:保留结点的最左孩子连线 删除其它孩子连线； 抹线 step3:将同一孩子的连线绕左孩子 旋转45度角。 旋转 7

7 6.4.1 树和森林与二叉树的转换 转换步骤： step1: 将树中同一结点的兄弟相连; 加线 抹线 旋转 讨论1：树如何转为二叉树？ 孩子—兄弟 表示法 step2: 保留结点的最左孩子连线， 删除其它孩子连线； step3: 将同一孩子的连线绕左孩子 旋转45度角

树转二叉树举例： 特点是？ 方法：加线—抹线一旋转 根结点没有右孩子！ 兄弟相连 长兄为父 孩子靠左 a C e 8

8 方法：加线—抹线—旋转 a b e i d f g h c 树转二叉树举例： a b e i d f h g c 兄弟相连 长兄为父 孩子靠左 特点是？ 根结点没有右孩子！

讨论2：二叉树怎样还原为树？ 要点：逆操作，把所有右孩子变为兄弟！ a b e 9

9 讨论2：二叉树怎样还原为树？ a b e i d f h g c 要点：逆操作，把所有右孩子变为兄弟！ a b d e f g h c i

讨论3：森林如何转为三叉树？ F=T1 T2.Tm)root,LB,RB) 法一 ① 各森林先各自转为工叉树： ②依次连到前一个一叉树的右子树上。 法二：森林直接变兄弟，再转为二叉树 参见教材P138图6.17，两种方法都有转换示意图) 法一和法二得到的二叉树是完 全相同的、惟一的。 10

10 法一： ① 各森林先各自转为二叉树； ② 依次连到前一个二叉树的右子树上。 讨论3：森林如何转为二叉树？ 即F={T1 , T2 , .,Tm} B={root, LB, RB} 法二：森林直接变兄弟，再转为二叉树 （参见教材P138图6.17，两种方法都有转换示意图） 法一和法二得到的二叉树是完 全相同的、惟一的