给定一棵二叉树,其层序遍历序列为ABCDEFG,其中A为根节点。若要采用基于队列的非递归方式进行层序遍历,在访问节点C之后,队列中存储的节点指针顺序是怎样的?
答案解析
层序遍历使用队列进行辅助,根节点A入队后,出队,并将其左右子节点B和C入队。接着,B出队,其左右子节点D和E入队。现在,队列中的节点顺序为CED。C出队,其左右子节点F和G入队。此时,队列中的节点顺序为DEGF,但由于题目要求是在访问C**之后**,故此时D和E还在队列中,加上C的左右子节点F和G,即DEGF。此时D还没被访问,所以队列里是D、E、F、G。但是题目问的是访问C之后,所以答案是D,E,F,G,其中D,E是B的左右子节点,F,G是C的左右子节点。因此,选项A错误,没有包含D和E。选项B错误,没有包含D。选项C错误,没有包含G。选项D错误,因为访问C之后,D和E依旧在队列中,故不应该只有F和G。
正确答案:A