选择题
设二叉树的前序序列为ABDEGHCFIJ,中序序列为DBGEHACIFJ。则后序序列为______。
A、
ABCDEFGHIJ
B、
JIHGFEDCBA
C、
GHIJDEFBCA
D、
DGHEBIJFCA
【正确答案】
D
【答案解析】
[考点] 数据结构与算法 由于在前序遍历二叉树时首先访问根结点,因此,前序序列中的第一个结点为二叉树的根结点,即A为根结点,又由于在中序遍历中访问根结点的次序为居中,而访问左子树上的结点为居先,访问右子树上的结点为最后,因此在中序序列以根结点(A)为分界线,前面的子序列(DBGEH)一定在左子树中,后面的子序列(CIFJ)一定在右子树中。同样的道理对于已经划分出的子序列再进行如上操作,还原二叉树后再按后序遍历,得序列为DGHEBIJFCA。
提交答案
关闭