问题 单项选择题

某二叉树的先序遍历序列为ABFCDE、中序遍历序列为BFADCE,则该二叉树根的左孩子和右孩子结点分别是()

A.B和F

B.F和B

C.B和C

D.C和B

答案

参考答案:C

解析:

本题考查数据结构基础知识。

二叉树的遍历运算常采用先序、中序、后序和层序方式,可以由指定的二叉树得出其各种遍历序列,也可以由其中的一些遍历序列构造出对应的二叉树。

先序遍历非空二叉树的方式为:先访问根结点,然后先序遍历根的左子树,最后先序遍历根的右子树。因此,从先序遍历序列可以确定根结点。

中序遍历非空二叉树的方式为:先中序遍历根的左子树,然后访问根结点,最后先序遍历根的右子树。因此,若已知根结点,则可根据中序遍历将左子树和右子树上的结点划分开。

题中由先序序列可以得知符号A代表根结点,则由中序序列可知,B、F是做左子树上的结点,C、D、E是右子树上的结点。反复用上述方式推导,则可得该二叉树如下图所示。

选择题
填空题