VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > temp > python入门教程 >
  • 【自考】数据结构第四章树和森林,期末不挂科指南,第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://www.cnblogs.com/happymeng/p/shujujiegou_7.html

 


相关教程