数据结构-第六章树和二叉树C(严蔚敏).ppt

《软件技术基础》(数据结构C++版)教案 信息工程系应用教研室 第6章 树和二叉树（Tree and Binary Tree） 例1： 例2：用二叉树表示算术表达式 例3：假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,画出该树. 对遍历的分析： 例：编写递归算法，计算二叉树中叶子结点的数目。 如何把二叉树存入电脑内？ 特别讨论：若已知先序（或后序）遍历结果和中序遍历结果，能否“恢复”出二叉树？ 6.3.2 线索二叉树 讨论1：二叉树是1:2的非线性结构，如何定义其直接后继？ 为区别两种不同情况，特增加两个标志域： 1. 有关线索二叉树的几个术语： 例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。 例1：画出以下二叉树对应的中序线索二叉树。 例2：【 考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 线索二叉树的生成算法（递归算法见教材P115-116） 3. 线索二叉树的遍历（无需堆栈） 附：中序线索二叉树遍历步骤 （算法6.5）： 算法流程： 6.3 遍历二叉树和线索二叉树 例：【 考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 线索二叉树的生成（递归算法见教材P134-135） 6.4 树和森林 6.4.1 树和森林与二叉树的转换 树转二叉树举例： 讨论2：二叉树怎样还原为树？ 森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树） 讨论4：二叉树如何还原为森林？ 6.4.2 树和森林的存储方式 例如： 6.4.3 树和森林的遍历 森林的遍历 附：二叉树若干典型算法（习题课） 附2：层次遍历算法(需要利用队列) 严题集6.47 ④ 转换步骤： step1: 将树中同一结点的兄弟相连; 加线 抹线 旋转 讨论1：树如何转为二叉树？ 孩子—兄弟表示法 step2: 保留结点的最左孩子连线，删除其它孩子连线； step3: 将同一孩子的连线绕左孩子旋转45度角。 方法：加线—抹线—旋转 a b e i d f h g c a b e i d f h g c 兄弟相连 长兄为父 孩子靠左 特点是？ 根结点没有右孩子！ a b e i d f h g c 要点：逆操作，把所有右孩子变为兄弟！ a b d e f h g i c 法一： ① 各森林先各自转为二叉树； ② 依次连到前一个二叉树的右子树上。 讨论3：森林如何转为二叉树？ 即F={T1, T2, …,Tm} B={root, LB, RB} 法二：森林直接变兄弟，再转为二叉树 （参见教材P138图6.17，两种方法都有转换示意图） 法一和法二得到的二叉树是完全相同的、惟一的。 A B C D E F G H J I A B C D E F G H J I A B C D E F G H J I 兄弟相连 长兄为父 头树为根 孩子靠左 A A B C D E F G H J I 要点：把最右边的子树变为森林，其余右子树变为兄弟 即B={root, LB, RB} F={T1, T2, …,Tm} A B C D E F G H J I E F A B C D G H J I 树有三种常用存储方式： ①双亲表示法 ②孩子表示法 ③孩子—兄弟表示法 nextsibling data firstchild 指向左孩子 指向右兄弟 问：树→二叉树的“连线—抹线—旋转” 如何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可。 存储的过程就是树转换为二叉树的过程！ a b e c d f h g b a c e d f g h 树的遍历 例如： a b d e c 先根序列： 后根序列： a b c d e b d c e a 深度优先遍历（先根、后根） 广度优先遍历（层次） 先根遍历 访问根结点； 依次先根遍历根结点的每棵子树。 后根遍历 依次后根遍历根结点的每棵子树； 访问根结点。 树没有中序遍历（因子树不分左右） 讨论：树若采用“先转换，后遍历”方式，结果是否一样？ a b d e c 先序遍历： 后序遍历： 中序遍历： d e c b a a b d e c a b c d e b d c e a 1. 树的先根遍历与二叉树的先序遍历相同； 2. 树的后根遍历相当于二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。 结论： 树的先根序列：a b c d e 树的后根序列：b d c e a 先根遍历 若森林为空，返回； 访问森林中第一棵树的根结点； 先根遍历第一棵树的根结点的子树森林； 先根遍历除去第一棵树之后剩余的树构成的森林。 A B C D E F G H J I 为何有中序