大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说数据结构第六章树和二叉树自测题答案_数据结构第三章答案,希望您对编程的造诣更进一步.
树和森林
这篇博客继续我们的《数据结构导论》课程，今天重点说说树和森林怎么备考自考和通过期末考试。
在开始之前，上篇博客最后其实还有一点没有写完，就是如何通过已知序列，恢复一棵二叉树
看例题吧
假设一棵二叉树的中序序列与后序序列分别为：BACDEFGH 和 BCAEDGHF 建立该二叉树
这种题目的解法，其实还是考察树的遍历
先看后序序列，后序序列的最后一个结点，也就是F，一定是根结点，为啥？想想吧
有根结点了，在看中序序列中 F左侧的BACDE左子树，F右侧的GH右子树
然后一遍遍的重复这个顺序，看后序序列 BCAED / GH 中，D，H是左右子树的跟结点
看中序序列 BAC D E / G H
所以 D的左子树 包含BAC结点，H的左子树包含G结点，不包含右结点
剩下的就交给你自己吧，最终要实现如下图所示即可
树的存储结构（该部分内容，近20年自考试卷中无涉及，过吧）
- 孩子链表 表示法
- 孩子兄弟链表 表示法
- 双亲 表示法
树、森林与二叉树的关系
重点内容，着重掌握相互转换
树转换成二叉树
任何一棵树可唯一地与一棵二叉树对应。相应地，一棵二叉树也唯一地对应一棵树，即树与二叉树可以相互转换
将树转换成二叉树的方法如下
- 将所有兄弟结点连接起来
- 保留第一个兄弟结点与父结点的连接，断开其他兄弟结点与父结点的连接，然后以根结点为轴心按顺时针的方向旋转45°角。
说的好绕口，其实一点都不难理解，看图即可
文字步骤：
- 将BCD结点连接起来，保留A与B的连接，断开A与C，A与D的连接
- 按照顺时针旋转45°，C成为结点B的右孩子，D成为结点C的右孩子，E成为B的左孩子
- 完成收工
反过去的过程也要会，也就是从二叉树转换成树
森林转换成二叉树
方法：
- 将每棵树转换成相应的二叉树
- 将步骤1中得到的各棵二叉树的根结点看做是兄弟连接起来
看一个例子吧
反过去的逻辑也要会，也就是从二叉树转换成森林
文字步骤
- 在待转换的二叉树中，断开根结点与右孩子的连线，得到两棵二叉树
- 重复断，断完之后还原兄弟结点到根结点即可
树和森林的遍历
树的遍历
（1）先序遍历
- 访问根结点
- 依次先序遍历根的各棵子树
（2）后序遍历
- 依次后序遍历根的各棵子树
- 访问根结点
（3）层次遍历
- 访问根结点
- 依次从左到右访问结点
森林的遍历
森林的遍历有两种方法：
（1）先序遍历森林
- 访问森林中第一棵树的根结点
- 先序遍历森林中第一棵树的根结点子树组成的森林；
- 先序遍历除去第一棵树之外其余的树组成的森林。
（2）中序遍历森林
- 中序遍历森林中第一棵树的根结点的子树组成的森林；
- 访问第一棵树的根结点
- 中序遍历除去第一棵树之外其余的树组成的森林。
今日小结
树、二叉树、森林的转换，转换方法蛮重要的，在自考中占比的分数一般在8分左右，所以一定要好好的练习哦~
当然有问题，可以找梦想橡皮擦
广宣时间
更多内容，欢迎关注 https://dwz.cn/r4lCXEuL
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/10260.html
