【题目】
假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ,中序遍历序列为 DBGEHJACIF ,则其前序遍历序列为 ( ) 。
A. ABCDEFGHIJ
B. ABDEGHJCFI
C. ABDEGHJFIC
D. ABDEGJHCFI
由题,后序遍历的最后一个值为A,说明本二叉树以节点A为根节点(当然,答案中第一个节点都是A,也证明了这一点)
下面给出整个分析过程
【第一步】
由后序遍历的最后一个节点可知本树根节点为【A】
加上中序遍历的结果,得知以【A】为根节点时,中序遍历结果被【A】分为两部分【DBGEHJ】【A】【CIF】
于是作出第一幅图如下
【第二步】
将已经确定了的节点从后序遍历结果中分割出去
即【DGJHEBIFC】---【A】
此时,位于后序遍历结果中的最后一个值为【C】
说明节点【C】是某棵子树的根节点
又由于【第一步】中【C】处于右子树,因此得到,【C】是右子树的根节点
于是回到中序遍历结果【DBGEHJ】【A】【CIF】中来,在【CIF】中,由于【C】是根节点,所以【IF】都是这棵子树的右子树,【CIF】子树没有左子树,于是得到下图
第三步】
将已经确定了的节点从后序遍历中分割出去
即【DGJHEBIF】---【CA】
此时,位于后序遍历结果中的最后一个值为【F】
说明节点【F】是某棵子树的根节点
又由于【第二步】中【F】处于右子树,因此得到,【F】是该右子树的根节点
于是回到中序遍历结果【DBGEHJ】【A】【C】【IF】中来,在【IF】中,由于【F】是根节点,所以【I】是【IF】这棵子树的左子树,于是得到下图
【第四步】
将已经确定了的节点从后序遍历中分割出去
即【DGJHEB】---【IFCA】
此时,位于后序遍历结果中的最后一个值为【B】
说明节点【B】是某棵子树的根节点
又由于【第一步】中【B】处于【A】的左子树,因此得到,【B】是该左子树的根节点
于是回到中序遍历结果【DBGEHJ】【A】【C】【F】【I】中来,根据【B】为根节点,可以将中序遍历再次划分为【D】【B】【GEHJ】【A】【C】【F】【I】,于是得到下图
【第五步】
将已经确定了的节点从后序遍历中分割出去
即【DGJHE】---【BIFCA】
此时,位于后序遍历结果中的最后一个值为【E】
说明节点【E】是某棵子树的根节点
又由于【第四步】中【E】处于【B】的右子树,因此得到,【E】是该右子树的根节点
于是回到中序遍历结果【D】【B】【GEHJ】【A】【C】【F】【I】中来,根据【B】为根节点,可以将中序遍历再次划分为【D】【B】【G】【E】【HJ】【A】【C】【F】【I】,于是得到下图
【第六步】
将已经确定了的节点从后序遍历中分割出去
即【DGJH】---【EBIFCA】
此时,位于后序遍历结果中的最后一个值为【H】
说明节点【H】是某棵子树的根节点
又由于【第五步】中【H】处于【E】的右子树,因此得到,【H】是该右子树的根节点
于是回到中序遍历结果【D】【B】【G】【E】【HJ】【A】【C】【F】【I】中来,根据【H】为根节点,可以将中序遍历再次划分为【D】【B】【G】【E】【H】【J】【A】【C】【F】【I】,于是得到下图
至此,整棵二叉树已经还原
现在对该二叉树进行前序遍历便能得到我们想要的答案
【B】
出处http://billhoo.blog.51cto.com/2337751/708872
- 大小: 4.5 KB
- 大小: 6.2 KB
- 大小: 7.3 KB
- 大小: 9.3 KB
- 大小: 11.1 KB
- 大小: 12.6 KB
分享到:
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
已知二叉树的前序和中序遍历,打印后序遍历,采用二叉树的非递归算法,分享给大家~~
1)根据给定二叉树的先序遍历和中序遍历结果,构造出该二叉树; (2)给出该二叉树的后序遍历结果; (3)判定该二叉树是否为平衡二叉树;
数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
二叉树的递归遍历,中序遍历,先序遍历,后序遍历,通过学习二叉树的遍历,可以让我们更紧一步掌握数据的遍历
二叉树的遍历,全部用递归实现,很有规律! 二叉树的遍历,全部用递归实现,很有规律
c++代码,能够根据前序序列、中序序列生成二叉树;能够一步生成,也可以一步步自动生成。 设计前序遍历,中序遍历,后序遍历,层次遍历;
常见的二叉树遍历,分为前序、中序、后续和层次遍历4种。 层次遍历相对比较好理解,对于前3种遍历方式概念的记忆方式应该是这样的:左和右的顺序始终是固定的—先左后右,所谓的前序、中序和后序是针对根来说的。...
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
二叉树已知后序和中序遍历求前序遍历,C++编写已通过编译
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
常见的二叉树遍历方式有三种:前序遍历、中序遍历和后序遍历。具体介绍如下: 1. 前序遍历(Pre-order Traversal): - 访问根节点。 - 对根节点的左子树进行前序遍历。 - 对根节点的右子树进行前序遍历。 ...
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
java 实现的二叉树前序建树,中序建树,后序建树以及前序遍历,中序遍历和后序遍历的代码
二叉树的遍历,前序遍历 中序遍历 后序遍历
一个实现二叉树遍历的程序代码,有先序,中序和后序。
C语言,数据结构课程,知道中序和后序遍历,画二叉树和写出前序遍历。
NULL 博文链接:https://128kj.iteye.com/blog/1692248