考虑一个包含两棵树的森林,T1的结构为根节点X,子树森林先序遍历为Y,Z。T2的结构为根节点A,子树森林先序遍历为B。如果对该森林进行中序遍历,并给定中序遍历的结果是Y,Z,X,B,A,那么该森林先序遍历结果是?

答案解析

森林的中序遍历规则为:先中序遍历第一棵树的子树森林,然后访问第一棵树的根节点,最后中序遍历剩余的树构成的森林。根据中序遍历结果Y,Z,X,B,A,可以推断出:T1的根节点是X,且子树森林的中序遍历是Y,Z;T2的根节点是A,且子树森林中序遍历是B。由于T1子树森林的先序和中序是一致的(本题中均未指定子树森林本身是否为二叉树),可知T1子树森林先序为Y,Z。T2子树森林先序为B。故森林的先序遍历为: 访问第一棵树根节点X,然后先序遍历第一棵树子树森林(Y,Z),然后访问第二棵树的根节点A,然后先序遍历第二棵树子树森林(B)。选项B错误在于将T2的子树森林提前。选项C是中序遍历结果。选项D错误在于将T1子树森林顺序颠倒。
正确答案:A
随机推荐
开始刷题