对关键码集合K=(53,30, 37,12, 45,24, 96),从空二叉树开始逐个插入每个关键码,建立与集合K相对应

Question

对关键码集合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，96C．12，24, 30, 37，45，53，96 D．30，24, 12, 37，45，96, 53

Answer 1

正确答案：B
二叉排序树(Binary Sort Tree：BST) 　　1、二叉排序树的定义 　　二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： 　　①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 　　②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 　　③左、右子树本身又各是一棵二叉排序树。 　　上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。 　　2、二叉排序树的特点 　　由BST性质可得： 　　（1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉排序树中，各结点关键字是惟一的。 依照BST性质，我们可知答案为B.