在二叉搜索树(BST)中,若中序遍历的序列为 {1, 2, 3, 4, 5} ,且先序遍历的第一个序列元素为 3 ,则下列说法正确的是( )。
A:该树一定是一棵完全二叉树
B:元素4和5不可能是兄弟节点
C:元素1所在节点的深度可能大于3(根节点深度为1)
D:元素2一定是元素1的父节点
正确答案:B
答案解析
中序遍历序列 {1, 2, 3, 4, 5} 表明二叉搜索树的节点按升序排列,根节点将中序序列分为左右子树。先序遍历首元素为3,说明根节点是3。由此可确定左子树包含{1,2},右子树包含{4,5}。根据二叉搜索树性质,1和2必须位于根的左子树,4和5位于右子树。左子树中2可能是1的父节点或1为2的左子节点;右子树中4和5可为任意父子关系。树的结构由先序和中序共同决定,但存在多种合法形态。深度取决于路径长度,从根到叶逐层计算。完全二叉树要求除最后一层外满填充且节点连续靠左,无法由给定条件唯一确定。
试卷来源:202603 CCF-GESP编程能力等级认证C++八级真题