若一棵二叉树的前序遍历为a, e, b, d, c，后序遍历

[单选题]

若一棵二叉树的前序遍历为a, e, b, d, c，后序遍历为b, c, d, e, a，则根节点的孩子节点为（）

```
只有e
```
```
有e、b
```
```
有e、c
```
```
无法确定
```

查看答案及解析

推荐

kuring

通过前序遍历序列和后序遍历序列不能够唯一确定一个二叉树，本例子存在两种情况：

    a
   /
  e
 / \ 
b   d
     \
      c

和

 a 
  \
   e
  / \ 
 b   d
      \
       c

可以看出根节点的孩子节点只有e

选A

编辑于 2015-06-19 20:49:07 回复(5)

星陨无痕

二叉树

前序遍历为a, e, b, d, c；

前序遍历是先访问根结点，再左子树，再右子树；

后序遍历为b, c, d, e, a；

后序是先访问左子树, 再右子树，再根结点

根据两个条件可知

a为最上父节点，e为a的左节点,b是e的左节点，并且b没有子节点，d是c的父节点，e的右节点。

由这些就看出，只有e是a的子节点，所以答案选择A

发表于 2015-06-21 10:18:07 回复(0)

iam小可

/ \

b d

发表于 2015-02-17 15:38:07 回复(1)

养兔子的熊

答案为A。

根据前序或后续序列，可以确定a必定有一个子结点e，假设e为左孩子，a右孩子不为空，则后续遍历序列中与a相邻的应该为a的右孩子。

同理，假设e为右孩子，a的左孩子不为空，则先序遍历时与a相邻的为a的左孩子。

故a有且只有e这一个孩子，左右无法确定。

发表于 2015-08-19 16:55:37 回复(1)

不想打工的沸羊羊很坦荡

发表于 2016-07-27 16:26:54 回复(8)

weizier

本例的e和c都无法确定是其父节点的右孩子还是左孩子。

但是可以确定的是a是整棵树的根节点，然后看后序遍历可以得知e必定是a的左节点或者是右节点。如果e是a的左孩子，并且a还有右孩子的话，那么在后序遍历序列里e和a必定还有一个节点，显然矛盾。如果e是a的右孩子，那么a不可能存在左孩子，因为这样一来在前序遍历里边a和e中间便应先是左孩子然后再是e，这显然也不对。

综上，a只有一个孩子，但无法确定是左孩子还是右孩子。

发表于 2015-06-21 00:39:38 回复(0)