某二叉树结点的中序遍历序列为ABCDEFG、后序遍历序列为BDCAFGE。现要求:
该二叉树所对应的森林包括几棵树?
【正确答案】:
该二叉树所对应的森林包括2棵树。
【题目解析】:
二叉树转换成森林的步骤:
(1)在待转换的二叉树中,断开根结点与右孩子的连线,得到两棵二叉树,其中一棵是以二叉树的根结点E为根的二叉树,另一棵是以根结点的右孩子G为根结点的二叉树。
(2)在以E为根结点的二叉树中,和以G为根结点的二叉树中都没有右孩子,故最终有2棵树。
该二叉树所对应的森林包括几棵树?
某二叉树结点的中序遍历序列为ABCDEFG、后序遍历序列为BDCAFGE。现要求:
该二叉树所对应的森林包括几棵树?
该二叉树所对应的森林包括2棵树。
二叉树转换成森林的步骤:
(1)在待转换的二叉树中,断开根结点与右孩子的连线,得到两棵二叉树,其中一棵是以二叉树的根结点E为根的二叉树,另一棵是以根结点的右孩子G为根结点的二叉树。
(2)在以E为根结点的二叉树中,和以G为根结点的二叉树中都没有右孩子,故最终有2棵树。