数据结构第四章树和森林，期末不挂科指南，第7篇

树和森林

这篇博客继续我们的《数据结构导论》课程，今天重点说说树和森林怎么备考自考和通过期末考试。

在开始之前，上篇博客最后其实还有一点没有写完，就是如何通过已知序列，恢复一棵二叉树

看例题吧

假设一棵二叉树的中序序列与后序序列分别为：BACDEFGH 和 BCAEDGHF 建立该二叉树

这种题目的解法，其实还是考察树的遍历

先看后序序列，后序序列的最后一个结点，也就是F，一定是根结点，为啥？想想吧

有根结点了，在看中序序列中 F左侧的BACDE左子树，F右侧的GH右子树

然后一遍遍的重复这个顺序，看后序序列 BCAED / GH 中，D，H是左右子树的跟结点

看中序序列 BAC D E / G H

所以 D的左子树 包含BAC结点，H的左子树包含G结点，不包含右结点

剩下的就交给你自己吧，最终要实现如下图所示即可

树的存储结构（该部分内容，近20年自考试卷中无涉及，过吧）

1. 孩子链表 表示法
2. 孩子兄弟链表 表示法
3. 双亲 表示法

树、森林与二叉树的关系

重点内容，着重掌握相互转换

树转换成二叉树

任何一棵树可唯一地与一棵二叉树对应。相应地，一棵二叉树也唯一地对应一棵树，即树与二叉树可以相互转换

将树转换成二叉树的方法如下

1. 将所有兄弟结点连接起来
2. 保留第一个兄弟结点与父结点的连接，断开其他兄弟结点与父结点的连接，然后以根结点为轴心按顺时针的方向旋转45°角。

说的好绕口，其实一点都不难理解，看图即可

文字步骤：

1. 将BCD结点连接起来，保留A与B的连接，断开A与C，A与D的连接
2. 按照顺时针旋转45°，C成为结点B的右孩子，D成为结点C的右孩子，E成为B的左孩子
3. 完成收工

反过去的过程也要会，也就是从二叉树转换成树

森林转换成二叉树

方法：

1. 将每棵树转换成相应的二叉树
2. 将步骤1中得到的各棵二叉树的根结点看做是兄弟连接起来

看一个例子吧

反过去的逻辑也要会，也就是从二叉树转换成森林

文字步骤

1. 在待转换的二叉树中，断开根结点与右孩子的连线，得到两棵二叉树
2. 重复断，断完之后还原兄弟结点到根结点即可

树和森林的遍历

树的遍历

（1）先序遍历

1. 访问根结点
2. 依次先序遍历根的各棵子树

（2）后序遍历

1. 依次后序遍历根的各棵子树
2. 访问根结点

（3）层次遍历

1. 访问根结点
2. 依次从左到右访问结点

森林的遍历

森林的遍历有两种方法：
（1）先序遍历森林

1. 访问森林中第一棵树的根结点
2. 先序遍历森林中第一棵树的根结点子树组成的森林；
3. 先序遍历除去第一棵树之外其余的树组成的森林。

（2）中序遍历森林

1. 中序遍历森林中第一棵树的根结点的子树组成的森林；
2. 访问第一棵树的根结点
3. 中序遍历除去第一棵树之外其余的树组成的森林。

今日小结

树、二叉树、森林的转换，转换方法蛮重要的，在自考中占比的分数一般在8分左右，所以一定要好好的练习哦~

当然有问题，可以找梦想橡皮擦

广宣时间