二叉排序树的不成功的平均查找长度怎么求?

比如：

             62
            /   \
          30     74
        /    \
     15       56
    /
  48

找到所有的外结点，也就是查找失败的点，然后计算ASL
就你的BST，结果如下：

• 15的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15一共3次
• 48的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15、48一共4次
• 56的右子树为空，也就是右子树是外结点，失败时需要比较62、30、56一共3次
• 74的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、74一共2次

因此外结点总数为2 *3 + 1 = 7 （其实这个数量一定是关键字个数加1）
所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3