已知长度为8的表（34，76，45，20，25，54，93 66），按照依次插入结点的方法生成一棵二叉排序树，写出构造过程，求出等概率下查找成功的平均查找长度。

二叉排序树的构造过程如下：

1. 将第一个结点 34 作为根结点。
2. 将第二个结点 76 与根结点比较，大于根结点，作为右子结点。
3. 将第三个结点 45 与根结点比较，小于根结点，作为左子结点。
4. 将第四个结点 20 与根结点比较，小于根结点，继续与左子结点比较，作为左子结点的左子结点。
5. 将第五个结点 25 与根结点比较，小于根结点，继续与左子结点比较，作为左子结点的右子结点。
6. 将第六个结点 54 与根结点比较，大于根结点，继续与右子结点比较，作为右子结点的左子结点。
7. 将第七个结点 93 与根结点比较，大于根结点，继续与右子结点比较，作为右子结点的右子结点。
8. 将第八个结点 66 与根结点比较，大于根结点，继续与右子结点比较，作为右子结点的左子结点的右子结点。

构造完成的二叉排序树如下：

       34
      /   \
    20     76
     \     / \
     25   54  93
              /
            66

等概率下查找成功的平均查找长度为树中每个结点深度的平均值。对于这棵二叉排序树，每个结点的深度分别为 1，2，2，3，3，3，4，所以平均查找长度为：

(1+2+2+3+3+3+4)/8 = 2.5

相关问题

已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉搜索树后，最后两层上的结点总数为： A. 1 B. 2 C. 3 D. 4

按照依次插入结点的方法生成一棵二叉搜索树后，树的结构取决于插入顺序。对于这8个数据元素，我们可以按照从左到右的顺序依次插入，生成如下的二叉搜索树：

        34
       /  \
     18   76
      \   / \
      26 45 92
         \
         54
          \
          65

最后两层上的结点分别为：92、54、65，共计3个，因此答案为 C. 3。

已知序列{50，72，43，85，75，20，35，45，65，30}请画出依次插入结点构造二叉排序树的过程

好的，我会根据您的要求画出依次插入节点构造二叉排序树的过程。下面是每一次插入节点后的二叉排序树：

50

50
 \
  72

50    72
 \      \
  43     85

50    72
 \      \
  43     85
   \     /
    75  75

50     72
 \       \
  43      85
   \     /  \
    75  75  20

50     72
 \       \
  43      85
 / \     /  \
20  45  75  20

50     72     35
 \       \       \
  43      85      45
 / \     /  \     / \
20  45  75  20  35  65

50     72     35
 \       \       \
  43      85      45
 / \     /  \     / \
20  45  75  20  35  65
             \
              30

希望这个过程可以帮助您更好地理解二叉排序树的构造过程。