某二叉树结点的中序序列为BDAECF 后序序列为DBEFCA 则该二叉树对应的森林包括 （)棵树。A．1B．2C．
序列,结点,森林
已帮助 人
某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括 ()棵树。
A．1
B．2
C．3
D．4
请帮忙给出正确答案和分析，谢谢！
-
正确答案：C
单凭二叉树的一种遍历序列是无法确定二叉树的具体形态的。而根据二叉树的先序遍历序列和中序遍历序列是可以唯一确定一棵二叉树的。根据后序遍历序列，A是二叉树的根结点。根据中序遍历序列，则二叉树的形态一定如图4—14所示。对于A的左子树，由后序遍历序列可知，因为B比D后被访问，因此B必为D的父结点，又由中序遍历序列可知，D是B的右儿子。对于A的右子树，同理可确定结点E、C、F的关系。此二叉树形态如图4—15所示。再根据二叉树与森林的对应关系。森林中树的棵数即为其对应二又树中根结点A的兄弟数。可知此森林中有3棵树，根结点分别为A、C和F。