二叉排序树的先序遍历、中序遍历、图形绘制及查找长度分析

已知一棵二叉排序树的先序遍历结果为：(20, 7, 3, 1, 8, 23, 21, 40)，请完成下列各题：

(1) 写出这棵二叉排序树的中序遍历结果；

(2) 画出这棵二叉排序树；

(3) 求在等概率情况下的查找成功和不成功情况下的平均查找长度。

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

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

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

(3) 在等概率情况下的查找成功情况下的平均查找长度为3.125，不成功情况下的平均查找长度为4.375。