Question

C++: 某二叉树的中序序列为ABCDEFG,后序序列为BDCAFGE,则该二叉树的先序序列为（

C++:
某二叉树的中序序列为ABCDEFG,后序序列为BDCAFGE,则该二叉树的先序序列为（ ），该二叉树对应的森林中包括（ ）棵树。
需要计算的过程，或者图，求高手，急

Answer 1

已知某二叉树的中根遍历序列是ABCDEFG,后根遍历序列是BDCAFGE,则它的先跟遍历序列是：EACBDGF。

首先明确先跟遍历：中左右；中根遍历：左中右；后根遍历：左右中。

1、后根遍历明确根节点是E,中根遍历确定左子树是ABCD，右子树上是FG；

2、后序遍历，A是左子树的根，然后在中序里ABCD判断A没有左子树；

3、根据GF中序序列所知F应该为G的左节点。

扩展资料

二叉树的性质

经过前人的总结，二叉树具有以下几个性质：

1、二叉树中，第 i 层最多有 2i-1 个结点。

2、如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。

3、二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。

同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2n2。所以，n 用另外一种方式表示为 n=n1+2n2+1。

两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。

Answer 2

显然长这样，所以先序序列为EACBDGF，这个你谁便用递归法就搞出来了，很基础的题吧

还有“二叉树对应的森林中包括（      ）棵树”二叉树当然就是一棵树啦，有什么森林不森林的

Answer 3

E
/ \
A G
\ \
C F
/ \
B D
后序最后一个是E，很明显E就是根
根据中序分成两叉，ABCD和FG
根据中序和后序，A肯定是左子树的根，并且A没有左子树
接下来就简单了

追问

那最后答案是？

追答

额，你自己看看吧，我不知道深林是什么东西。。

Answer 4

先序是EACBDGF
包括2棵树(把二叉树画出来根据口诀转换成树)

Answer 5

使用前序序列联合中序序列还原二叉树后就可以知道，该二叉树的后序序列为：BDCAFGE

追问

亲，不要乱答好嘛

要求先序