🏷️ 知识点：二叉排序树
在常用的描述二叉排序树的存储结构中，关键字值最大的结点是（ ）。
A. 左指针一定为空 B. 右指针一定为空 C. 左、右指针均为空 D. 左、右指针均不为空
[tag_link]
正确答案：B
在二叉排序树中，关键字值最大的结点位于树的最右侧，这是由二叉排序树的性质决定的：对于任意结点，其左子树中的所有结点关键字值均小于该结点，右子树中的所有结点关键字值均大于该结点。 因此，从根结点开始一直向右遍历，直到没有右子结点时，所到达的结点即为最大值结点。 由于该结点没有右子结点，其右指针一定为空。
左指针的情况则不确定：最大值结点可能有左子树（此时左指针不为空），也可能没有左子树（此时左指针为空），但这并不影响其作为最大值结点的特性。 选项A、C、D均不能准确描述最大值结点的指针状态，故选项B正确。
含有 4 个元素值均不相同的结点的二叉排序树有（ ）种。
A. 4 B. 6 C. 10 D. 14
[tag_link]
正确答案：D
二叉排序树（BST）的结构数量由卡特兰数决定。 对于 n 个值均不相同的节点，不同形态的二叉排序树数量等于第 n 个卡特兰数
，计算公式为
其中 表示组合数。
当
时，计算 ：
因此，含有 4 个元素值均不相同的结点的二叉排序树共有 14 种。
下图所示的二叉树是（ ）。
A. 二叉判定树 B. 二叉排序树 C. 二叉平衡树 D. 堆
[tag_link]
正确答案：B
首先，需要明确题目中各个选项的定义：二叉判定树通常用于描述算法中的判定过程，如比较排序中的决策树，其结构不一定有序； 二叉排序树（又称二叉搜索树）的特点是对于任意节点，其左子树的所有节点值均小于该节点值，右子树的所有节点值均大于该节点值，整个树呈现有序性； 二叉平衡树（如 AVL 树）在二叉排序树的基础上要求左右子树的高度差不超过 1，以保持查询效率； 堆是一种完全二叉树，满足堆属性（如最大堆中父节点值大于等于子节点值）。
题目中的图片为占位符，未展示具体二叉树结构。 但根据常见考试题型和数据结构知识，若二叉树节点值呈现有序排列（左小右大），则通常归类为二叉排序树。 图示二叉树往往符合这一特征，且二叉排序树是基础且常见的数据结构，因此选项 B 最符合题意。 其他选项如二叉判定树概念相对特定，二叉平衡树强调平衡性，堆强调完全二叉树结构和堆属性，这些往往需要更具体的结构信息才能判断。
分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A. （100,80,90,60,120,110,130） B. （100,120,110,130,80,60,90） C. （100,60,80,90,120,110,130） D. （100,80,60,90,120,130,110）
[tag_link]
正确答案：C
在构造二叉排序树时，序列A、B、D生成的树结构相同，而序列C生成的左子树结构不同，具体如下：
- A、B、D的树结构为：
` 100
/ \
80 120
/ \ / \
60 90 110 130
`- C的树结构为：
` 100
/ \
60 120
\ / \
80 110 130
\
90
`因此，与其他三个序列所构造的结果不同的是C。 >
利用逐个插入建立序列 (50,72,43,85,75,20,35,45,65,30) 对应的二叉排序树后，要查找元素 30 要进行的元素间比较次数是（ ）。
A. 4 B. 5 C. 6 D. 7
[tag_link]
正确答案：B
考查二叉排序树的构造和查找。 按题中数据的输入次序，建立的二叉排序树如右图所示。 查找元素 30 需要依次比较的元素为 50,43,20,35,30，比较次数为 5 次。
` 50
/ \
43 72
/ \ /
20 45 65 85
\ /
35 75
/
30
`
下列给定的关键字输入序列中，不能生成如下二叉排序树的是（ ）。
A. 4，5，2，1，3 B. 4，5，1，2，3 C. 4，2，5，3，1 D. 4，2，1，3，5
[tag_link]
正确答案：B
选项 B 生成二叉排序树的过程如下，显然 B 选项错误：
以下关于二叉排序树的说法中，错误的有（ ）个。
A. 1 B. 2 C. 3 D. 4
[tag_link]
正确答案：D
说法 I 错误：对二叉排序树进行前序遍历（根→左→右）时，先访问根结点，然后访问所有小于根的左子树结点，最后访问所有大于根的右子树结点，得到的序列并非从大到小； 只有中序遍历才能得到有序序列。 说法 II 错误：二叉排序树要求每个结点的左子树中所有结点值都小于该结点值，右子树中所有结点值都大于该结点值； 仅满足“比左孩子值大、比右孩子值小”不能保证整个子树满足条件，例如左孩子的右孩子可能大于根结点，违反定义。 说法 III 错误：插入的关键字总是位于叶结点，但是叶结点并不一定位于最底层。 说法 IV 错误：删除结点时，若结点有两个孩子，通常用前驱或后继替换，可能改变树的结构； 重新插入同一关键字时，会作为新叶子插入，位置可能不同，因此得到的树与原来不一定相同。 综上，错误的有 I、II、IV，共 3 个。
在任意一棵非空二叉排序树 T1 中，删除某结点 v 之后形成二叉排序树 T2 ，再将 v 插入 T2 形成二叉排序树 T3 。下列关于 T1 与 T3 的叙述中，正确的是（ ）。
I. 若 v 是 T1 的叶结点，则 T1 与 T3 不同
II. 若 v 是 T1 的叶结点，则 T1 与 T3 相同
III. 若 v 不是 T1 的叶结点，则 T1 与 T3 不同
IV. 若 v 不是 T1 的叶结点，则 T1 与 T3 相同
A.仅 I、III
B.仅 I、IV
C.仅 II、III
D.仅 II、IV
[tag_link] 正确答案：C在一棵 二叉排序树 中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。
已知二叉排序树如下图所示，元素之间应满足的大小关系是（ ）。
A. (x_1 < x_2 < x_5) B. (x_3 < x_4 < x_5) C. (x_3 < x_5 < x_4) D. (x_5 < x_4 < x_3)
[tag_link]
正确答案：C
根据 二叉排序树 的特性：中序遍历（LNR）得到的是一个递增序列。图中二叉排序树的中序遍历序列为xi ,x3 ,x5 ,x4 ,x2, 可知x3 <x5 <x4。
对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。
A. 95，22，91，24，94，71
B. 92，20，91，34，88，35
C. 21，89，77，29，36，38
D. 12，25，71，68，33，34
[tag_link]
正确答案：A
在 二叉排序树 中，左子树结点值小于根结点，右子树结点值大于根结点。在选项 A 中，当查找到 91 后再向 24 查找，说明这一条路径（左子树）之后查找的数都要比 91 小，而后面却查找到了 94（解题过程中，建议配合画图），因此错误。
一棵二叉搜索树如下图所示，K1、K2、K3 分别是对应结点中保存的关键字、三角形表示子树。则子树 T 中任一结点中保存的关键字 X 满足的是（ ）。
A. X < K1 B. X>K2 C. K1 < X < K2 D. K3 < X < K2
[tag_link]
正确答案：D
根据二叉搜索树的性质，K2的左子树的节点关键字均小于K2，可以得出K3 <K2，T中所有节点小于K2，同理也可以得出K3的右子树节点均大于K3，即T中所有节点
K3 ，X是T中节点，由此可以得出K3 <X<K2。
下列二叉树中，可能成为折半查找判定树（不含外部结点）的是（）
A. 树 A B. 树 B C. 树 C D. 树 D
[tag_link]
正确答案：A
折半查找判定树 实际上是一棵 二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，判断哪颗树符合折半查找的规则。折半查找树由于其中序遍历是一个升序序列，因此相比于在以往的序列中进行二分查找，折半查找二叉树的优点在于不用自己去找中点，而是直接将要查找的关键字与根节点相比，小的话再和根节点的左子节点（又是相应的左子树中点，更加方便）比较，大的话则是和根节点的右子节点比较。而对于这道题的解题思路就在于向上或向下取整的问题，也就是说如果升序序列是偶数个，那么中点应该偏左多右少还是左少右多。但是很显然应该进行一个统一，像 B 和 C 选项中间的对称部分明显就是选择了不同的策略。D 则由根节点左子树 4 个节点而点右子树 5 个节点可以确定用的是向下取整策略，但是我们再看它的左子节点在左子树中对应的中点左边 2 个数，右边一个数，明显是向上取整策略，策略没有统一，所以是错的。