这篇博客继续我们的《数据结构导论》课程,今天重点说说树和森林怎么备考自考和通过期末考试。
在开始之前,上篇博客最后其实还有一点没有写完,就是如何通过已知序列,恢复一棵二叉树
看例题吧
假设一棵二叉树的中序序列与后序序列分别为:BACDEFGH 和 BCAEDGHF 建立该二叉树
这种题目的解法,其实还是考察树的遍历
先看后序序列,后序序列的最后一个结点,也就是F,一定是根结点,为啥?想想吧
有根结点了,在看中序序列中 F左侧的BACDE左子树,F右侧的GH右子树
然后一遍遍的重复这个顺序,看后序序列 BCAED / GH 中,D,H是左右子树的跟结点
看中序序列 BAC D E / G H
所以 D的左子树 包含BAC结点,H的左子树包含G结点,不包含右结点
剩下的就交给你自己吧,最终要实现如下图所示即可
重点内容,着重掌握相互转换
任何一棵树可唯一地
与一棵二叉树对应。相应地,一棵二叉树也唯一地对应一棵树,即树与二叉树可以相互转换
将树转换成二叉树的方法如下
说的好绕口,其实一点都不难理解,看图即可
文字步骤:
反过去的过程也要会,也就是从二叉树转换成树
方法:
看一个例子吧
反过去的逻辑也要会,也就是从二叉树转换成森林
文字步骤
(1)先序遍历
(2)后序遍历
(3)层次遍历
森林的遍历有两种方法: (1)先序遍历森林
(2)中序遍历森林
树、二叉树、森林的转换,转换方法蛮重要的,在自考中占比的分数一般在8分左右,所以一定要好好的练习哦~
当然有问题,可以找梦想橡皮擦
广宣时间
更多内容,欢迎关注 https://dwz.cn/r4lCXEuL