【自考】数据结构第四章树和森林,期末不挂科指南,第7篇

树和森林

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

[En]

This blog continues our course “introduction to data structures”. Today, we focus on how trees and forests prepare for the self-exam and pass the final exam.

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

[En]

Before we start, there is actually one thing left unfinished in the last blog, that is, how to restore a binary tree through a known sequence.

看例题吧

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

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

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

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

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

看中序序列 BAC D E / G H

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

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

【自考】数据结构第四章树和森林,期末不挂科指南,第7篇

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

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

树、森林与二叉树的关系

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

树转换成二叉树

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

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

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

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

【自考】数据结构第四章树和森林,期末不挂科指南,第7篇

文字步骤:

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

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

森林转换成二叉树

方法:

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

看一个例子吧

【自考】数据结构第四章树和森林,期末不挂科指南,第7篇

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

文字步骤

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

树和森林的遍历

树的遍历

(1)先序遍历

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

(2)后序遍历

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

(3)层次遍历

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

森林的遍历

森林的遍历有两种方法:
(1)先序遍历森林

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

(2)中序遍历森林

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

今日小结

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

[En]

The conversion method of tree, binary tree and forest is very important. The score in the self-examination is generally about 8, so be sure to practice well.

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

广宣时间

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

Original: https://www.cnblogs.com/happymeng/p/shujujiegou_7.html
Author: 梦想橡皮擦
Title: 【自考】数据结构第四章树和森林,期末不挂科指南,第7篇

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/116698/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部