已知某二叉树的中序序列为CBDAEFI、先序序列为ABCDEFI,则该二叉树的高度为(58)。A.2B.3C.4D.5

Question

已知某二叉树的中序序列为CBDAEFI、先序序列为ABCDEFI，则该二叉树的高度为(58)。

A．2

B．3

C．4

D．5

Answer 1

正确答案：C
解析：本题考查二叉树的遍历运算。根据二叉树的定义，非空二叉树由根结点、根的左子树和根的右子树三部分组成。二叉树的先序遍历定义为：先访问根结点，然后先序遍历根的左子树，最后先序遍历根的右子树。二叉树的中序遍历定义为：中序遍历根的左子树，访问根结点，最后中序遍历根的右子树。由此，根据二叉树的先序遍历序列和中序遍历序列构造二叉树时，首先根据先序序列找到根结点，然后由中序序列分别得到左、右子树的中序序列和先序序列，如此反复进行分解，即可得到原二叉树。因该二叉树的先序序列中A是第一个结点，因此确定A是整棵二叉树的树根，在中序序列中找到A，并据此划分出根的左子树上的结点中序序列CBD和右子树上的结点中序序列EFI。再根据先序遍历的特点，先序序列指示出B是左子树的根结点，中序序列中C在B的左边、D在B的右边，因此确定C结点在以B为根的左子树上、D结点在以B为根的右子树上。依次类推，根据先序序列确定根，根据中序序列分割子树，最后得到的原二叉树如下图所示。

二叉树的层数为树的高度。