对关键码集合K=（53 30 37 12 45 24 96） 从空二叉树开始逐个插入每个关键码 建立与集合K相对应
关键,序列,最小
已帮助 人
对关键码集合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
-
参考答案：B二叉排序树(Binary Sort Tree：BST) 1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③左、右子树本身又各是一棵二叉排序树。 上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。 2、二叉排序树的特点 由BST性质可得： （1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉排序树中，各结点关键字是惟一的。 依照BST性质，我们可知答案为B.