首页 > 试题广场 >

二叉树的后序排列DBEFCA，中序排列DBAECF，那么对其

[单选题]
二叉树的后序排列DBEFCA，中序排列DBAECF，那么对其做先序线索化二叉树，节点E的线索化指向节点（） 
  • BC
  • AC
  • DF
  • CF
查看答案及解析
添加回答
推荐
田_我是大姐大头像 田_我是大姐大
选择D。
由二叉树的后序排列DBEFCA（后序遍历是 先找左右两个子节点，然后再找子节点的父节点）。
中序排列DBAECF （中序遍历是 先找子节点的父节点，然后再找子节点，子节点分为左孩子和右孩子，左孩子 在这个父节点的左边，右孩子在父节点的右边）。
可以得出二叉树如下图：

由此，可以得出  节点E的线索化指向节点 CF，和E连接的是CF，所以选择D
编辑于 2015-08-26 19:41:10 回复(0)
讨鬼头像 讨鬼
发表于 2015-08-26 08:25:08 回复(0)
huixieqingchun头像 huixieqingchun
注意线索的含义，添加的新指针是指向前驱和后继的，认真分析。
发表于 2016-05-10 17:05:44 回复(0)
手机抄手专家头像 手机抄手专家
节点的线索化就是某种(前序,中序,后序)序列的前驱节点和后继结点
发表于 2015-09-05 15:31:08 回复(1)
繁星的夜空2012头像 繁星的夜空2012
首先，从后序排列中可以知道A是树的根节点；
其次，从中序排列可以知道（DB）是树的左子树，而（ECF）是树的右子树
再次，观察后序排列，先从左子树出发，可知B是左子树的根节点，然后再从中序排列得知D是B的左孩子。
再次，观察后序排列，从右子树(EFC)出发，可知C是右子树的根节点，，然后再从中序排列得知E是C的左孩子，F是C的右孩子。
结论：已知后续排列和中序排列，可以得到唯一的先序排列。
发表于 2016-12-22 16:36:34 回复(0)
__sgf__头像 __sgf__
写出先序遍历序列，然后找一下前驱和后继就行了。
发表于 2022-03-14 02:41:20 回复(0)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa
先还原树 后 DBEFCA  中 DBAECF
         A
  B      C
D      E   F
然后先序为：ABDCEF ，E指向C前驱，后继F
发表于 2018-06-17 17:36:17 回复(0)
苏城丶头像 苏城丶
注意题眼是做先序线索化
发表于 2020-09-28 16:36:51 回复(0)
rs勿忘初心头像 rs勿忘初心
首先，从后序排列中可以知道A是树的根节点；
其次，从中序排列可以知道（DB）是树的左子树，而（ECF）是树的右子树
再次，观察后序排列，先从左子树出发，可知B是左子树的根节点，然后再从中序排列得知D是B的左孩子。
再次，观察后序排列，从右子树(EFC)出发，可知C是右子树的根节点，，然后再从中序排列得知E是C的左孩子，F是C的右孩子。
结论：已知后续排列和中序排列，可以得到唯一的先序排列。
发表于 2017-07-01 20:17:20 回复(0)
牛客-68头像 牛客-68
先序序列为 ABDCEF 位于E两侧的为CF
发表于 2017-06-20 16:33:26 回复(0)
范雷东头像 范雷东
感觉这道题出的挺好的
发表于 2017-04-11 09:45:10 回复(0)
牛客713182号头像 牛客713182号
树要转化成二叉搜索树.。。
发表于 2016-08-17 12:40:35 回复(0)
situs头像 situs
D


每个方框格式：左指针，值，右指针
发表于 2015-08-26 22:43:44 回复(0)
KevinJia头像 KevinJia
D
发表于 2015-08-26 21:59:30 回复(0)
click_one头像 click_one
D 根据中序和后续 可以获取该二叉树 根据二叉树的前序遍历规则 可以得到前序的遍历顺序为：ABDCEF 因此线索化后E指向了CF
发表于 2015-08-26 21:09:42 回复(0)
且听风吟_sunflower头像 且听风吟_sunflower
D
先序排列为ABDCEF,对E来说，其直接前驱为C后继为F
发表于 2015-08-26 19:17:28 回复(0)
夏菲头像 夏菲
D  由中序和后序得到先序序列为ABDCEF，所以其做先序线索化二叉树，节点E的线索化指向CF
发表于 2015-08-26 17:03:56 回复(0)
AndrewZJ头像 AndrewZJ
D
发表于 2015-01-11 02:53:56 回复(0)
提交观点

问题信息

树 腾讯
上传者：秋之邂逅
难度：
18条回答 12388浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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