首页 > 试题广场 >

对某二叉树进行先序遍历的结果是ABDEFC,中序遍历的结果是

[单选题]
对某二叉树进行先序遍历的结果是ABDEFC,中序遍历的结果是DBFEAC，则后序遍历的结果是（） 
  • DBFEAC
  • DFEBCA
  • CFEDBA
  • CEFBDA
添加回答
推荐
agjsytt头像 agjsytt
B. 由中序序列，c是a的唯一右孩子，所以，后序一定是***ca这样的结果(左，右，根)，选B.
编辑于 2017-03-18 09:23:36 回复(0)
小白同学头像 小白同学

知道先序是根->左->右，中序是左->根->右，后序是左->右->根，但是以前一直没整明白怎么根据已知两个序遍历求第三种遍历（前提是一定要知道中序遍历），今天做这个题的时候忽然脑袋开窍了。
最重要的一点就是：找到根->找到左右子树
一直重复这个操作，直到最后一个子节点。
先序遍历的结果是ABDEFC，根据先序得到根节点是A.
中序遍历的结果是DBFEAC，根据中序得到A之前的节点都是左子树，A之后的节点都是右子树，所以可以得出：
图片说明
接着分析左子树的情况，先序排列是BDEF,根节点是B，中序排列是DBFE，B之前的节点是它的左子树，B之后的节点是它的右子树，可以得出：
图片说明
最后分析右子树的情况，先序排列是EF，中序排列是FE，所以E是根节点，F是左节点。
最后就是：
图片说明
得到后序遍历：DFEBCA

发表于 2017-11-29 12:04:11 回复(3)
敲代码的咸鱼头像 敲代码的咸鱼
B
先序遍历第一个元素是头节点，然后中序遍历中A的左边是DBFE右边是C
画好了头，然后先序BDEFC，B为头
发表于 2018-05-14 22:20:15 回复(0)
blackwidow头像 blackwidow 
由前序中序推导后续
已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
Ø    根据前序序列的第一个元素建立根结点；
Ø    在中序序列中找到该元素，确定根结点的左右子树的中序序列；
Ø    在前序序列中确定左右子树的前序序列；
Ø    由左子树的前序序列和中序序列建立左子树；
Ø    由右子树的前序序列和中序序列建立右子树。
由中序后序推导前序
已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
Ø    根据后序序列的最后一个元素建立根结点；
Ø    在中序序列中找到该元素，确定根结点的左右子树的中序序列；
Ø    在后序序列中确定左右子树的后序序列；
Ø    由左子树的后序序列和中序序列建立左子树；
Ø    由右子树的后序序列和中序序列建立右子树。
由前序和后序无法确定中序

编辑于 2017-03-11 02:25:17 回复(0)
Spectre_头像 Spectre_
B
发表于 2019-10-15 23:30:37 回复(0)
fy_bihan头像 fy_bihan
1、由先序遍历可知，A为根结点，由中序遍历可知，DBFE是A的左子树，C为A的右子树
2、由先序遍历可知，BDFE中，B为A的左子树的根节点，由中序遍历可知，D为B的左子树，FE为B的右子树
3、由先序遍历可知，E为B的右子树的根节点，由中序遍历可知，F为E的左子树，
所以后序遍历的顺序为DFEBCA
发表于 2018-12-04 23:35:37 回复(0)
求一个offer555头像 求一个offer555
B
由前序遍历确定根节点，然后通过根节点确定中序遍历的左右子树。循环重复前述操作既可确定树的结构。详细可见剑指offer重建二叉树一题。
发表于 2018-10-25 19:15:22 回复(0)
Mark宇宙头像 Mark宇宙
B
发表于 2018-10-25 17:30:50 回复(0)
lucky!头像 lucky!
B
发表于 2018-06-21 16:32:32 回复(0)
周伟诚头像 周伟诚

答案

B

思路

通过先序和中序序列，找到共同的根节点进行分析，画图即可。

发表于 2018-03-12 17:08:37 回复(0)
Aban头像 Aban
B DFEBCA，通过前序遍历确定根节点，通过中序遍历确定左右子树。
发表于 2018-03-07 17:00:30 回复(0)
Anoyer_元戎内推：AEMTt头像 Anoyer_元戎内推：AEMTt

B

发表于 2018-03-06 19:24:37 回复(0)
小琦2头像 小琦2
B
树结构：   A
         B              C
   D        E     空     空
空 空   F  空
发表于 2018-03-06 11:49:09 回复(0)
看花开花落-头像 看花开花落-
   B
发表于 2018-02-09 11:45:30 回复(0)
胭脂红头像 胭脂红
B 不能确定，但B是唯一一个可能的。、

因为由先序遍历确定A是根节点，由中序遍历可以确定DBFE是在左边C是在右边。
发表于 2017-11-24 22:40:32 回复(0)
lcsxy头像 lcsxy
选B
根据先序遍历判断A是根节点，根据中序遍历判断DBFE都在左子树，C在右子树，然后再DBFE中再用这种方法判断。
最后重建整棵树。
发表于 2017-11-23 15:55:14 回复(0)
鄞头像 鄞
B
发表于 2017-02-27 00:58:15 回复(0)
牧羊少年_jeep头像 牧羊少年_jeep
先序遍历是根左右，中序遍历是左根右，后序遍历左右根，在进行推算即可
发表于 2016-12-30 18:08:56 回复(0)
提交观点

问题信息

C++工程师 4399游戏 2017 树 Java工程师 销售
来自：职能类模拟题1
上传者：牛100
难度：
18条回答 7629浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号