数据结构第六章树和二叉树自测题答案_数据结构第三章答案

数据结构第六章树和二叉树自测题答案_数据结构第三章答案树和森林 这篇博客继续我们的《数据结构导论》课程,今天重点说说树和森林怎么备考自考和通过期末考试。 在开始之前,上篇博客最后其实还有一点没有写完,就是如何通过已知序列,恢复一棵二叉树 看例题吧 假设一

【自考】数据结构第四章树和森林,期末不挂科指南,第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分左右,所以一定要好好的练习哦~

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

广宣时间

更多内容,欢迎关注 https://dwz.cn/r4lCXEuL

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
转载请注明出处: https://daima100.com/10260.html

(0)
上一篇 2022-12-30 17:30
下一篇 2023-01-22

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注