给定一个二叉树,采用扩展二叉树形式表示,其中 '#' 表示空节点。若其前序遍历序列为 A B # D # # C E # # F # #,则其对应的二叉树的后序遍历序列是?
答案解析
核心考点:二叉树的遍历(前序和后序),扩展二叉树。
解题思路:根据前序遍历序列还原二叉树,然后进行后序遍历。
选项分析:
前序遍历序列 A B # D # # C E # # F # # 对应的二叉树结构为A(B(D),C(E,F)),后序遍历序列为左子树->右子树->根,去掉空节点就是D B E F C A。
A. # # D B # # E # F C A: 包含空节点,错误。
B. D # # B E # # F C A: 包含空节点,且后序遍历错误,错误。
C. D B E F C A: 正确的后序遍历序列,正确。
D. D # # B E # # C F # A: 包含空节点,后序遍历错误,错误。
正确答案的依据:根据给出的前序遍历序列,构建二叉树,然后进行后序遍历得到D B E F C A。
易错点:忽略了空节点或弄混了前序和后序遍历的顺序。
正确答案:C