某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA

[单选题]

某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括（）棵树

```
1
```
```
2
```
```
3
```
```
4
```

查看答案及解析

烟消bug云散

二叉树转换为树和森林。若二叉树非空，则二叉树根及其左子树为第一棵二叉树形式，二叉树根的右子树又可以看做一个由森林转换后的二叉树，应用同样的方法，直到最后产生一棵没有右子树的二叉树为止，这样就得到一个森林。为了进一步得到树，可用树的二叉链表表示逆方法，即结点的右子树的根、右子树的右子树的根......找出原本是同一个双亲的兄弟。二叉树转换为树或森林是唯一的。

发表于 2016-07-12 09:38:50 回复(0)

水慕渔樵

3颗树，如图。二叉树到森林的转换是：二叉树中节点的左孩子是森林中该节点的孩子，右孩子是森林中该节点的兄弟。

发表于 2016-09-09 21:27:40 回复(2)

天是一般蓝

三序中知道其中两个就可以推出第三个，但是前提是我们要知道中序。

每个序都有隐藏信息：

前序：序列的第一个为根结点

后序：序列的最后一个为根结点

中序：通过前序或者后序知道根结点后可推出左右子树

根据题目：

中序序列为BDAECF

后序序列为DBEFCA

1：由后序序列推出 A为根结点

2：将A代入中序中得（BD）A（ECF），BD为左子树，ECF为右子树

3：对于 BD：

中序：BD

后序：DB

推出：（空）B（D）

4：对于 ECF：

中序：ECF

后序：EFC

推出：（E）C（F）

因此可以推出上面有人分析的图

最后二叉树转化为森林上面也有人讲了，我不多说了。

编辑于 2021-01-14 16:21:53 回复(1)

free斩

选C

发表于 2015-01-07 02:39:32 回复(3)

追风筝

又二叉树的中序遍历和后序遍历可以构建该二叉树，图见楼上。

从树到二叉树的转化方法一般是“兄弟孩子法”，也就是把树结点的第一个孩子变为左孩子结点，兄弟结点变为右孩子节点。由此得到的二叉树，根节点必无右孩子。所以对于森林到二叉树树的转化，是依次把森林的每棵树转化为二叉树，把最后一颗转化后的二叉树的根节点作为上一颗二叉树的右孩子节点，这样把两颗二叉树接成一颗二叉树。然后依次向前连接，直到只有一颗二叉树。反过来，构建后的二叉树的右下节点都是由对应的森林里不同的树相连而成的，可以想象二叉往树右侧的先序遍历依次经过A-C-F到达树的底端，这三个结点在对应的森林中都必定分属不同的树。所以一共有三棵树。

发表于 2015-08-02 19:46:17 回复(0)