二叉排序树后序遍历结果求解：中序遍历、树结构及平均查找长度

(1) 中序遍历结果为：(1, 3, 7, 8, 20, 21, 23, 40)

(2) 二叉排序树如下图所示：

        20
      /    \
     7     23
   /   \      \
  3     8     40
 /           /
1          21

(3) 在等概率情况下，查找成功的平均查找长度为4.25，查找不成功的平均查找长度为4.5。具体计算方法如下：

查找成功的平均查找长度： 在二叉排序树中查找一个元素的平均查找长度，与该元素在树中的深度有关。对于这棵二叉排序树，每个元素的深度分别为1、2、2、3、3、3、4、4，它们在树中出现的概率相等，均为1/8。因此，查找成功的平均查找长度为（1×1/8）+（2×2/8）+（3×3/8）+（4×2/8）=17/4=4.25。

查找不成功的平均查找长度： 若在二叉排序树中查找一个不存在的元素，它会停在某个空结点的位置，这个空结点就是该元素应该插入的位置。因此，查找不成功的平均查找长度，等于从根结点开始，到达某个空结点的平均路径长度。对于这棵二叉排序树，有5个空结点，它们在树中出现的概率均为1/9。因此，查找不成功的平均查找长度为（1×1/9）+（2×2/9）+（3×3/9）+（4×2/9）=13/3=4.5。