给定一个森林,其中包含三棵树T1、T2和T3。T1的根节点为A,其子树森林先序遍历结果为B、C。T2的根节点为D,其子树森林为空。T3的根节点为E,其子树森林先序遍历结果为F、G。若对该森林进行先序遍历,所得的结点访问序列是什么?
答案解析
森林的先序遍历规则为:先访问第一棵树的根节点,然后先序遍历第一棵树的子树森林,最后先序遍历剩余的树构成的森林。对于本题,首先访问T1的根节点A,然后先序遍历T1的子树森林得到B、C。接着访问T2的根节点D。最后访问T3的根节点E,然后先序遍历T3的子树森林得到F、G。因此,正确的访问序列为A, B, C, D, E, F, G。选项B错误在于将T3的先序结果提前,选项C错误在于将T2的根节点放在了T3之后,选项D错误在于将T1的子树森林的顺序颠倒,并且将T3的子树森林顺序颠倒。
正确答案:A