树和森林这篇博客继续我们的《数据结构导论》课程,今天重点说说树和森林怎么备考自考和通过期末考试。 在开始之前,上篇博客最后其实还有一点没有写完,就是如何通过已知序列,恢复一棵二叉树 看例题吧
这种题目的解法,其实还是考察树的遍历 先看后序序列,后序序列的最后一个结点,也就是F,一定是根结点,为啥?想想吧 有根结点了,在看中序序列中 F左侧的BACDE左子树,F右侧的GH右子树 然后一遍遍的重复这个顺序,看后序序列 BCAED / GH 中,D,H是左右子树的跟结点 看中序序列 BAC D E / G H 所以 D的左子树 包含BAC结点,H的左子树包含G结点,不包含右结点 剩下的就交给你自己吧,最终要实现如下图所示即可 树的存储结构(该部分内容,近20年自考试卷中无涉及,过吧)
树、森林与二叉树的关系
树转换成二叉树任何一棵树可 将树转换成二叉树的方法如下
文字步骤:
森林转换成二叉树方法:
看一个例子吧 反过去的逻辑也要会,也就是从二叉树转换成森林 文字步骤
树和森林的遍历树的遍历(1)先序遍历
(2)后序遍历
(3)层次遍历
森林的遍历森林的遍历有两种方法:
(2)中序遍历森林
今日小结树、二叉树、森林的转换,转换方法蛮重要的,在自考中占比的分数一般在8分左右,所以一定要好好的练习哦~ 当然有问题,可以找梦想橡皮擦 |
|