国家开放大学
设有一个整数序列d{40，28，6，72，100，3，54}依次取出序列中的数，构造一棵二叉排序树。并对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度。
题目
参考答案和解析
（2）ASL=（1×1+2×2+3×3+4）/7=18/7
略
相似问题和答案
第1题：
第2题：
用关键字序列10、20、30、40、50构造的二叉排序树(二叉查找树)为(63)。
A．
B．
C．
D．
解析：二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：
1．若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。
2．若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。
3．根结点的左、右子树也分别为二叉排序树。
构造二叉排序树过程如下：
首先与根结点比较，如果小于等于则进入左边子树，再与左边子树的根节点比较，直到找到它要放的位置，否则进入右子树，进行上述操作。
第3题：
第4题：
第5题：
已知长度为9的表{16、3、7、11、9、26、18、14、15}，建立二叉排序树后进行查找，则等概率情况下查找成功的平均查找长度为(35)。
A．30/9
B．25/9
C．29/9
D．31/9
解析：本题考查二叉排序树的查找。二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质(BST性质)的二叉树：(1)若它的左子树非空，则左子树上所有结点的值均小于根结点；(2)若它的右子树非空，则右子树上所有结点的值均大于根结点；(3)左、右子树本身又各是一棵二叉排序树。在做该题时，首先将表中的9个元素放进二叉树中构成二叉排序树，在构造二叉排序树时，我们将表中的元素依次按照构造二叉排序树的规则往树中添加元素，在获得二叉排序树后，计算平均长度就变得简单了，为(1+2+2+3+3+4+5+5+6)/9=31/9。
第6题：
在一棵二叉排序树中，按【 】遍历得到的节点序列是有序序列。
中序 解析：二叉排序树的特点是左子树各节点的值小于树根节点，右子树各节点的值大于等于树根节点的值。中序遍历是“左子树—树根节点—右子树”，因此要得到有序节点序列，应进行中序遍历。
第7题：
● 用关键字序列10、20、30、40、50构造的二叉排序树（二叉查找树）为 （63） 。
第8题：
设有关键字n=2h-1,构成二叉排序树,每个关键字查找的概率相等,查找成功的ASL最大是n()
A.对
B.错
第9题：
在一棵非空的二叉排序树（二叉查找树)中，进行__ (41)遍历运算并输出所访问 结点的关键码后，可得到一个有序序列。
A.先序
B.中序
C.后序
D.层序
本题考查数据结构基础知识。根据二叉排序树的定义，对于树中的每个结点，其左子树中的关键字均小于根结点的关键字，其右子树中的关键字均大于根结点的关键字，而中序遍历的次序是左子树、根结点、右子树，因此，对一个非空的二叉排序树进行中序遍历，所输出的关键码序列是递增有序序列。
第10题：
给定数列{8，17，5，9，21，10，7，19，6}，依次取序列中的数构造一棵二叉排序树。并对上述二叉树给出中序遍历得到的序列。
（1）
（2）5，6，7，8，9，10，17，18，19，21
略