我要招人

去企业版

首页 > 试题广场 >

某二叉树中序序列为A,B,C,D,E,F,G,后序序列为B,

[单选题]

某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是（）

```
EGFACDB
```
```
EACBDGF
```
```
EAGCFBD
```
```
上面的都不对
```

查看答案及解析

DaiDi

首先要明确前序，中序和后序的遍历顺序：

前序：父节点，左子节点，右子节点；

后序：左子节点，右子结点，父节点；

另外，我们必须要知道如果没有中序序列,是无法唯一确定一棵树的。

图是这样的：

/ \

A G

\ /

C F

/ \

B D

结果选择B。

发表于 2014-12-30 13:19:22 回复(0)

登登gogo

后序序列为B,D,C,A,F,G,E，（左右根）那么可以判定E为根，结合中序序列为A,B,C,D,E,F,G,（左根右），可以判断出ABCD一定在FG的左边

发表于 2016-08-10 12:25:31 回复(0)

雷明顿

由后序序列和中序序列可以唯一确定一棵二叉树，这是由两种遍历序列的特点所决定的。

后序序列的最后一个节点是根节点，中序序列中根节点将序列分为左右子树的中序序列；在后序序列中找到左右子树的序列，其最后一个节点是左右子树的根节点，如此递归就能确定整个二叉树的形态。

其算法实现步骤如下：

根据后序序***定树的根节点
根据根节点在中序序列中划分出二叉树的左、右子树包含哪些节点。然后根据左右子树节点在后序序列中的次序可以确定子树的根节点，即回到步骤 1.
如此重复上述步骤，知道每棵子树仅有一个节点为止，如下图所示。

从而前序遍历结果为： EACBDGF

发表于 2015-12-08 21:10:04 回复(3)

Plutoweb

根据第一赞的老哥的启发，捋一下我的思路：

根据后序遍历确定"E"为根节点
根据前序遍历把他们拆分为"A,B,C,D"与"F,G"左右子树
根据后序遍历确定这两个子树的根节点分别为："A"与"G"
然后再根据第二步拆分为"B,C,D"子树，"F"不用管了
重复找到根节点"C"......(直到找完所有节点)

编辑于 2021-03-13 22:35:24 回复(0)

sunlight_run

A G

C F

B D

这是还原后的二叉树，没有箭头，不好画，凑合看

发表于 2017-06-25 21:42:21 回复(0)

媛

如果没有中序序列,是无法唯一确定一棵树的

发表于 2015-11-05 22:11:21 回复(0)

54dabang

记住两点：前序和后续是用来判断根节点的，而中序遍历用来判断左右子树的。

发表于 2015-08-27 20:16:43 回复(1)

提交观点

问题信息

树

难度：

7条回答 193收藏 12782浏览

某二叉树中序序列为A,B,C,D,E,F,G,后序序列为B,

问题信息

热门推荐

相关试题