这破旧的脑子——二叉树

28次阅读

共计 796 个字符,预计需要花费 2 分钟才能阅读完成。

为什么会写这篇文章
学习的时间越来越长总会忘掉一些东西,就比如向量,矩阵,二叉树,邻接表,太多太多东西,不用就都给忘了,今天看了这样一道面试题:总结下来就是根据二叉树的前中序遍历,然后写出后序遍历,清晰的记得当时学习二叉树的时候做这种题是很快的,可是我还真就卡住了,不是说需要做一会儿,是做不出来,看过好多遍使用程序实现 DFS(深度优先)BFS(广度优先) 的例子,可是让我用笔推断,我还真就脑子瓦特了,所以也记录一下,顺便帮一下也忘记了手工推断的你们回忆一下,你们一定都比我优秀,perfect。
题目:

前序遍历
A D C E F G H B

中序遍历
C D F E G H A B

后序遍历?

这些遍历就是根据遍历根节点的顺序而定义的,前序遍历就是优先遍历根节点然后遍历左右子节点,当然左右子节点也是根据这个原则遍历的,那么中后序遍历也一样。那么我们应该怎么去做呢?其实就是根据前中遍历的结果推断出这颗树。。。

第一步

根据前序遍历原则找出根节点:A 因为优先遍历根节点

根据根节点 A 和中序遍历划分前中序遍历的左右子树,以中左表示,前序遍历的左右子树,以前左表示:

中左:C D F E G H
中右:B
前左:D C E F G H
前右:B

第二步

根据上面的中左,前左继续划分根节点:D 由于右子树就一个节点,所以就结束了
根据根节点 D 和中序遍历划分前中序遍历的左右子树
中左:C
中右:F E G H
前左:C
前右:E F G H

第三步

根据上面的中右,前右继续划分根节点:E 由于左子树就一个节点,所以就结束了
根据根节点 E 和中序遍历划分前中序遍历的左右子树
中左:F
中右:G H
前左:F
前右:G H

第四步

根据上面的中右,前右继续划分根节点:G 由于左子树就一个节点,所以就结束了
根据根节点 G 和中序遍历划分前中序遍历的左右子树
中左:
中右:H
前左:
前右:H

终于构建出来这颗树了,接下来根据后序遍历原则去写:

后序遍历结果亮相:
C F H G E D B A

只有多学习才能变得更强,还是那句话: 坚持一件事,对自己。

正文完
 0