1、将序列(30，18，15，25，28，66，40, 70，80)的各元素依次插入一棵初始为空的二叉排序树中, 要求构造（画出）一棵二叉排序树,要求计算出查找关键字66时的比较次数并计算出查找成功与不成功时的平均查找长度。

好的，我可以帮你解决这个问题。

首先，我们来构造这棵二叉排序树：

            30
           /  \
         18    66
        / \    / \
      15  25  40  80
            \    
            28   

按照二叉排序树的性质，左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。因此，按照题目给出的序列，我们先将30作为根节点插入，然后依次插入18、15、25、28、66、40、70、80。

接下来，我们计算查找关键字66时的比较次数。从根节点30开始比较，发现66比30大，于是到右子树查找。在右子树中，先比较66和66，相等，查找成功，比较次数为2。

最后，我们计算查找成功和不成功时的平均查找长度。平均查找长度定义为：查找成功时从根节点到目标节点的路径长度，查找不成功时从根节点到最后一个被访问节点的路径长度。对于这棵二叉排序树，查找成功的节点有：30、66、80，它们的路径长度分别为1、1、3，因此查找成功时平均查找长度为(1+1+3)/3=1.67。查找不成功时，最后一个被访问的节点是40，因此平均查找长度为(1+1+1+1+2+2+3+3)/8=1.875。

希望这个回答对你有所帮助。

相关问题

已知关键字序列（50，39，66，98，77，14，28，49），在用小顶堆排序算法排序。

首先，将关键字序列构建成一个小顶堆。具体步骤如下：

1. 将关键字序列依次插入小顶堆中，插入时保持小顶堆的性质，即每个节点的值都小于或等于其子节点的值。

2. 依次取出堆顶元素，将其放到一个新的序列中，并从小顶堆中删除该元素，然后再次调整小顶堆，使其满足小顶堆的性质。

3. 重复步骤2，直到小顶堆为空，所有元素都已经被取出。

最终得到的排序结果为：14，28，39，49，50，66，77，98。

利用过滤法将关键字序列 { 37, 66, 48, 29, 31, 75 } 建成的最大堆为 __

首先需要了解最大堆的性质：在最大堆中，父节点的值总是大于或等于其子节点的值。

利用过滤法建立最大堆的步骤如下：

1. 将第一个元素放入堆中，此时堆中只有一个元素，也就是根节点。
2. 依次将剩余的元素插入堆中，每插入一个元素都要保证堆的性质。具体做法是将该元素插入堆的末尾，然后与其父节点比较，如果该元素的值大于其父节点的值，则交换该元素与其父节点的位置，一直重复这个过程直到该元素的值小于或等于其父节点的值或者该元素成为了根节点。
3. 重复步骤2直到所有元素都插入堆中。

根据这个方法，我们可以将关键字序列 { 37, 66, 48, 29, 31, 75 } 建成的最大堆如下：

       75
      /  \
    66    48
   /  \   / \
  29  31 37

其中根节点为75，左子节点为66，右子节点为48，66的左子节点为29，右子节点为31，48的左子节点为37。这个堆满足最大堆的性质，即父节点的值总是大于或等于其子节点的值。