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

1、武汉软件工程职业学院 数据结构讲义第 14 讲-2 叉树、树和森林第四章树第十四讲二叉树、树和森林1掌握树的存储结构。2掌握树森林与二叉树的相互转换，3. 树的遍历方法 。教学重点：树森林与二叉树的相互转换教学难点：树森林与二叉树的相互转换授课内容4.5二叉树、树和森林树的存储结构树的存储结构有多种形式。 下面介绍三种常用的存储结构。1双亲数组表示发第四章树这种存储结构是利用每个结点（除根结点外）只有唯一双亲的特点， 用一维数组来存储一棵一般的树。图 451 便是一棵树及其双亲表示的存储结构。 在这种结构中， 寻找一个结点的双亲时，只要访问它的 parent 域，便可立即得到它的双亲的存储位置

2、； 但是，若要寻找一个结点的孩子时，则需遍历整个数组。0A-1A1B0C0B2D0E1EFG3F1G3HJ4H5I55J5图 451 树的双亲2结点定长的孩子链表表示法图 451 所示的树，它是一个三叉树， 可用三叉链表来存储。 其结点结构为： 一个数据域和三个指针域。指针域用于指向该结点的各个孩子结点。该树的三重链表如图 4 52(a) 所示。3孩子兄弟二叉链表表示法第四章树如果用孩子兄弟链表作为存储结构， 其结点结构为：一个数据域和两个指针域。 其中一个指针指向它的第一个孩子结点， 另一个指向它的兄弟结点。图 451 中树的孩子兄弟链表如图 452（b）所示。AABDB DFF (a) 孩

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

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

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

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