在含有 15 个结点的平衡二叉树上，查找关键字为 28（存在该结点）的结点，则依次比较的关键字有可能是（　）。

A. 30,36 B. 38,48,28 C. 48,18,38,28 D. 60,20,50,40,38,28

平衡二叉树

[tag_link]

正确答案：C

在平衡二叉树（如AVL树）中查找结点时，比较序列必须遵循二叉搜索树的性质：若目标值小于当前结点值，则进入左子树； 若大于，则进入右子树。 同时，树有15个结点且平衡，高度约为 log₂15≈4，因此查找路径上的结点数通常不超过4个（对应高度为3）。

• 选项A：比较30后，28<30应进入左子树，但下一个比较36>30，不可能进入左子树，违反二叉搜索树性质。
• 选项B：比较38后，28<38应进入左子树，但下一个比较48>38，不可能进入左子树，同样违反性质。
• 选项C：序列48,18,38,28符合二叉搜索树性质：28<48进入左子树； 28>18进入右子树； 28<38进入左子树； 找到28。 路径长度为4，对应树高度为3，对于15个结点的平衡二叉树是可能的，可以通过调整其他结点保持平衡。
• 选项D：序列60,20,50,40,38,28虽符合二叉搜索树性质，但路径长度为6，对应树高度至少为5。 对于15个结点的平衡二叉树，高度为5至少需要20个结点（如AVL树的最小结点数要求），因此不可能在保持平衡的前提下存在这样的查找路径。

综上，只有选项C可能。