一个森林由两棵树构成。第一棵树的根节点为R1,其中序遍历结果为C, D, R1。第二棵树的根节点为R2,其先序遍历结果为E, F。对该森林进行中序遍历,可能的结点访问序列是?
答案解析
森林的中序遍历规则是:先中序遍历第一棵树的子树森林,然后访问第一棵树的根节点,最后中序遍历剩余的树构成的森林。第一棵树的中序遍历结果是C, D, R1,这意味着其子树森林中序遍历是C, D。第二棵树先序遍历结果是E, F,无法得知其具体中序遍历结果。根据森林的中序遍历规则,第一棵树的遍历结果C,D,R1应该先于第二棵树的遍历结果。因此森林的中序遍历前三位必须是C,D,R1,而第二棵树中序遍历结果只知道是E和F的组合。选项A错误在于没有按照森林的中序规则,将第二棵树的根节点提前。选项C错误在于将第一棵树的根节点放到了子树前面,违反了中序规则。选项D中第二棵树的顺序错误。
正确答案:B