树和二叉树（三）

内容回顾 二叉树的递归遍历方法 中序非递归遍历方法 二叉树的构造方法

5.4 树和森林 5.4.1 树的存储方式 5.4.2 森林与二叉树的转换 5.4.3 树和森林的遍历

教学目标 1．了解树的存储表示。 2．掌握森林与二叉树的转换方法。 3．掌握树的遍历方法。 4．了解森林的遍历方法。 计算机科学与技术系 4/ 计算机科学与技术系 信息与教育技术中心

5.4.1 树的存储方式 树有三种常用存储方式： ①双亲表示法 ②孩子表示法 ③孩子兄弟表示法 1、用双亲表示法来存储 ①双亲表示法 ②孩子表示法 ③孩子兄弟表示法 1、用双亲表示法来存储 思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在表中的位置。 data parents 1 树结构 2 3 n parents data 结点结构

例1: 双亲表示法 1 2 3 4 5 6 7 8 A B C D E F G H I 1 2 3 -1 A B C G E I D H F 例1: 双亲表示法 1 2 3 4 5 6 7 8 A B C D E F G H I 1 2 3 -1 A B C G E I D H F 1 缺点：求结点的孩子时需要遍历整个结构。

2、用孩子表示法来存储 思路：将每个结点的孩子排列起来，形成一个带表头（装双亲结点）的线性表（n个结点要设立n个链表）；再将n个表头用数组存放起来，这样就形成一个混合结构。 1 2 3 4 5 6 7 8 g f e d c b a h b c 例如： a b e c d f h g d e f g h 在孩子表示法中查找双亲比较困难，查找孩子却十分方便，故适用于对孩子操作多的应用。

双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。 带双亲的孩子链表

思路：用二叉链表来表示树，但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子； 右指针指向该结点的下一个兄弟结点。 3、用孩子兄弟表示法来存储 思路：用二叉链表来表示树，但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子； 右指针指向该结点的下一个兄弟结点。 nextsibling data firstchild 指向右兄弟 指向左孩子

例如： a a b e c d f h g b c d e f g h

原因：利用二叉树的已有算法解决树的有关问题。 讨论1：树如何转为二叉树？ 5.4.2 树和森林与二叉树的转换 原因：利用二叉树的已有算法解决树的有关问题。 讨论1：树如何转为二叉树？ 转换步骤： step1: 将树中同一结点的兄弟相连; step2: 保留结点的最左孩子连线，删除其它孩子连线； step3: 将同一孩子的连线绕左孩子旋转45度角。 加线 抹线 旋转

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

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

讨论3：森林如何转为二叉树？ 即F={T1, T2, …,Tm} B={root, LB, RB} 法一： ① 各森林先各自转为二叉树； ② 依次连到前一个二叉树的右子树上。 法二：森林直接变兄弟，再转为二叉树

森林转二叉树举例：（法二） A 兄弟相连 长兄为父 孩子靠左 头根为根 A B C D E F G H J I A B C D E F G

即B={root, LB, RB} F={T1, T2, …,Tm} 讨论4：二叉树如何还原为森林？ 即B={root, LB, RB} F={T1, T2, …,Tm} 要点：把最右边的子树变为森林，其余右子树变为兄弟 G H J I A B C D E F G H J I A B C D E F A B C D E F G H J I

问：树转二叉树的“连线—抹线—旋转” 如何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可。 存储的过程就是转换的过程！ 例如： a b e c d f h g a b c d e f g h

练习 1.将此森林转换为相应的二叉树。

练习 2.将此二叉树还原为树

练习 2．设森林F中有三棵树，第一、第二和第三棵树的结点树分别为m1、m2和m3，则与森林F对应的二叉树的根结点的右子树上的结点个数是（ ）。 ① m1 ② m1+m2 ③ m3 ④ m2+m3 ④ 森林转化为二叉树的规则是首先将森林中的各棵树的根结点看成是兄弟结点，然后再按照树转化为二叉树的规则进行转化。因此，本题中经转化而得到的二叉树的根结点的右子树上结点数等于第二、第三棵树上的结点数之和。

5.4.3 树和森林的遍历 树的遍历 常用方法 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点

A B E F I G C D E I F G B C D A A B C D E F G I 先根遍历： 后根遍历： 层次遍历： A B

小结 树的存储方式 树和森林与二叉树的转换 树和森林的遍历 ①双亲表示法 ②孩子表示法 ③孩子兄弟表示法 树转二叉树：加线—抹线—旋转 ①双亲表示法 ②孩子表示法 ③孩子兄弟表示法 树和森林与二叉树的转换 树转二叉树：加线—抹线—旋转 二叉树怎样还原为树：把所有右孩子变为兄弟 森林如何转为二叉树 二叉树如何还原为森林 树和森林的遍历 先根（序）遍历、后根（序）遍历、按层次遍历

作业 1.设一棵树的二元组形式表示为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法表示出该树的存储结构并将该树转化为对应的二叉树。 2. 已知一棵二叉树如图所示，请将该二叉树还原为森林。 A B F C D E G H