选择题
某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的深度(根结点在第1层)为______。
A、
2
B、
3
C、
4
D、
5
【正确答案】
C
【答案解析】
[考点] 数据结构与算法 由于在前序遍历二叉树中首先访问根结点,因此,前序序列中的第一个结点为二叉树的根结点,即A为根结点,又由于在中序遍历中访问根结点的次序为居中,而访问左子树上的结点为居先,访问右子树上的结点为最后,因此在中序序列以根结点(A)为分界线,前面的子序列(DCB)一定在左子树中,后面的子序列(EFG)一定在右子树中。同样的道理,对于已经划分出的子序列再进行如上操作,还原二叉树后得出深度为4。
提交答案
关闭