某二叉树的先序遍历序列为ABCDEF，中序遍历序列为BADCFE，则该二叉树的高

题库2022-08-02 35

问题某二叉树的先序遍历序列为ABCDEF，中序遍历序列为BADCFE，则该二叉树的高度（即层数）为（　　）。A.3B.4C.5D.6

选项 A.3
B.4
C.5
D.6

答案 B

解析先序遍历即先根后左子树再右子树，中序遍历为先左子树后跟再右子树。先序遍历的最开始结点A即为整棵树的根，结合中序遍历，A结点左侧B即为根节点A的左子树，右侧DCFE则为A的右子树，同理可以得出C为A的右子树的根节点，D为C的左子树，EF为C的右子树，F为E的左子树。可以得到如下图，所以该二颗树的高度为4。