武汉软件工程职业学院数据结构讲义第14讲_2叉树、树和森林

1、第十四讲二叉树、树和森林1 掌握树的存储结构。2 掌握树森林与二叉树的相互转换，3. 树的遍历方法 。教学重点： 树森林与二叉树的相互转换 教学难点： 树森林与二叉树的相互转换 授课容4.5 二叉树、树和森林4.5.1 树的存储结构树的存储结构有多种形式。下面介绍三种常用的存储结构。1 双亲数组表示发这种存储结构是利用每个结点 （除根结点外） 只有唯一双亲的特点， 用一维数组来存储 一棵一般的树。图 4 51 便是一棵树及其双亲表示的存储结构。在这种结构中，寻找一 个结点的双亲时，只要访问它的 parent 域，便可立即得到它的双亲的存储位置；但是，若 要寻找一个结点的孩子时，则需遍历整个数组

2、。A-1B0C0D0E1F1G3H5I5J50123456789图 4 5 1 树的双亲表示法2 结点定长的孩子链表表示法图 45 1 所示的树，它是一个三叉树，可用三叉链表来存储。其结点结构为：一个 数据域和三个指针域。指针域用于指向该结点的各个孩子结点。该树的三重链表如图4 5 2(a) 所示。3 孩子兄弟二叉链表表示法 如果用孩子兄弟链表作为存储结构， 其结点结构为： 一个数据域和两个指针域。 其中 一个指针指向它的第一个孩子结点，另一个指向它的兄弟结点。图45 1 中树的孩子(b)孩子兄弟链表表示法兄弟链表如图 452 ( b )所示。(a) 孩子链表表示法图45 2 树的链表表示法假

3、设把图 452(b)中指向兄弟的水平方向指针改为下斜45 °，不难发现它与一棵二叉树的链表结构十分相似。 由于二叉树的结构规、 简单， 因此常将一般树结构转换为二 叉树结构，然后利用二叉树已有的算法进行处理。4.5.2 树与二叉树之间的转换对于一般树， 树中孩子的次序并不重要， 只要双亲与孩子的关系正确即可。 但在二叉树 中，左、右孩子的次序是严格区分的。所以在讨论二叉树和一般树之间的转换时， 为不引起 混淆，就约定按树上现有结点次序进行转换。1 一般树转换为二叉树 将一般树转化为二叉树的思路，主要根据树的孩子兄弟存储方式而来，具体步骤为： （ 1） 加线。在各兄弟结点之间用虚线相连

4、。可理解为每个结点的兄弟指针指向它的 一个兄弟。（ 2） 抹线。对每个结点仅保留它与其最左孩子的连线，抹去该结点与其它孩子之间 的连线。可理解为每个结点仅有一个孩子指针，让它指向自己的第一个孩子。（ 3） 旋转。把虚线改为实线从水平方向向下旋转45 °，成右斜下方向。原书中实线成左斜下方向。这样就形成一棵二叉树。由于二叉树中各结点的右孩子都是原一树数中该结点的兄弟， 而一般树的根结点又没有 兄弟结点， 因此所生成的二叉树的根结点没有右子树。 在所生成的二叉树中某一结点的左孩 子仍是原来树中该结点的长子，并且是它的最左孩子。图45 3 是一个由一般树转为二叉树的实例。(b)图 4 5

5、3 一般树转换为二叉树2 二叉树还原为一般树 二叉树还原为一般树，此时的二叉树必须是由某一树转换而来的没有右子树的二叉树。其还原过程也分为三步：（1） 加线。若某结点 I 是双亲结点的左孩子，则将该结点 I的右孩子以及当且 仅当 连续地沿着右孩子的右链不断搜索到所有右孩子，都分别与结点 I 的双亲结点用虚线连接。（ 2） 抹线。把原二叉树中所有双亲结点与其右孩子的连线抹去。这里的右孩子实质上是原一般数中结点的兄弟，抹去的连线是兄弟间的关系。（ 3） 进行整理。把虚线改为实线，把结点按层次排列。二叉树还原为一般树的示例，如图 4 5 4 所示。ADBFGEJCIABDCEFGIAABCEFGII

6、FGI图 4 5 4 二叉树还原为一般树4.5.3 森林与二叉树的转换森林是树的有限集合，如图 4 55（a）所示。1 森林转换为二叉树 森林转换为二叉树的步骤为：（ 1） 将森林中每棵子树转换成相应的二叉树，形成有若干二叉树的森林。（ 2） 按森林中树的先后次序， 依次将后边一棵二叉树作为前边一棵二叉树根结点的 右子树， 这样整个森林就生成了一棵二叉树。 实际上第一棵树的根结点便是生成后的二叉树 的根结点。图 4 55 是森林转化为二叉树的示例。F(a) 一般 树的森(b)二 叉树的 森(c) 第二棵树并入第一棵图45(d) 最 终 结5 森林转换为二叉树2 二叉树还原为森林 将一棵由森林转换得到的二叉树还原为森里的步骤是：( 1) 抹线。将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不