问题
单项选择题
某二叉树的先序遍历序列为ABFCDE、中序遍历序列为BFADCE,则该二叉树根的左孩子和右孩子结点分别是()
A.B和F
B.F和B
C.B和C
D.C和B
答案
参考答案:C
解析:
本题考查数据结构基础知识。
二叉树的遍历运算常采用先序、中序、后序和层序方式,可以由指定的二叉树得出其各种遍历序列,也可以由其中的一些遍历序列构造出对应的二叉树。
先序遍历非空二叉树的方式为:先访问根结点,然后先序遍历根的左子树,最后先序遍历根的右子树。因此,从先序遍历序列可以确定根结点。
中序遍历非空二叉树的方式为:先中序遍历根的左子树,然后访问根结点,最后先序遍历根的右子树。因此,若已知根结点,则可根据中序遍历将左子树和右子树上的结点划分开。
题中由先序序列可以得知符号A代表根结点,则由中序序列可知,B、F是做左子树上的结点,C、D、E是右子树上的结点。反复用上述方式推导,则可得该二叉树如下图所示。