对关键码集合K=53，30，37，12，45，24，96)，从空二叉树开始逐

问题单项选择题

对关键码集合K=53，30，37，12，45，24，96)，从空二叉树开始逐个插入每个关键码，建立与集合K相对应的二叉排序树(又称二叉查找树)BST，若希望得到的BST高度最小，应选择下列哪种输入序列 ( )。

A) 45，24，53，12，37，96，30
B) 37，24，12，30，53，45，96
C) 12，24，30，37，45，53，96
D) 30，24，12，37，45，96，53

答案

参考答案：B

解析：要使BST的高度最小，应把尽量把中间值作为树根节点。也就是说中间值先插入。在关键码集合K中，37是中间值，因此选项B可能是最小：再仔细观察发现B选项中每个子树的各节点的插入都是中间值，如37是中间值，24是30、24，12中的中间值，先插入：53是45、53、96的中间值先插入。从而保证了其高度最小。另外通过画各树的示意图也可知A的高度为4、B的高度为3、C的高度为7、D的高度为5。