二叉树中已知前序和中序求其后序(图解加技巧让你轻松掌握)

发布时间 2024-01-03 20:00:18作者: DoubleLi

 

 

一 

        首先咱得了解二叉树的结构,和前序/中序/后序遍历分别是什么。 

1:什么是根和左右孩子:二叉树的每个节点都可以作为根,每个根下面的叫左右孩子,也可以没有孩子

实际使用中会如下图A是根左孩子是B,右孩子是C;C是根没有左右孩子,B是根左孩子是D,右孩子是E

2 前序/中序和后序遍历分别是什么:

前序遍历:先访问再访问左孩子然后访问右孩子,简称根左右的访问顺序叫前序遍历

中序遍历:先访问左孩子再访问然后访问右孩子,简称左根右的访问顺序叫中序遍历

后序遍历:先访问左孩子再访问右孩子然后访问,简称左右根的访问顺序叫后序遍历

如下图前序遍历为:A, B, D, E, C

如下图中序遍历为:D, B, E, A, C

如下图后序遍历为:D, E, B, C, A

 二 理解前中序的意义

如下图

从前序遍历可知根节点为 A,我们在中序遍历中找到A。在 A左半边的值在图中也恰好在左半 边,右半边的值也恰好在图中右边 。所以按这个规律画图即可

 

1   已经知道在二叉树中:
前序序列: E,H,B,C,F,A,D,G
中序序列: B,H,F,C,A,E,D, G
求后序遍历:

2 根据上述结论开始解题

第一步:从前序遍历中找到第一个根节点(E)

第二步: 从前序遍历中找到第二个根节点(H)

 第三步: 从前序遍历中找到第三个根节点(B),但由图可知B已经结束所以直接跳过

第四步: 从前序遍历中找到第四个根节点(C)

第五 步:由图可知F,A已经结束,所以直接跳过

第六步: 从前序遍历中找到第七个根节点(D)

如图咱就结束了

后续遍历如图应为:B, F, A, C, H, G, D, E

 如有不对的地方欢迎评论区指点,画图不宜望点赞