武汉软件工程职业学院《数据结构讲义》讲叉树树和森林

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

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

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

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

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

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