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

问题描述:

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

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

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

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

解答:

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

(2) 根据后序遍历结果，可以确定根节点为20，然后从后往前遍历后序遍历结果，可以确定右子树为(40, 23, 21)，左子树为(8, 7, 3, 1)。因此，可以画出如下的二叉排序树：

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

(3) 由于是二叉排序树，因此在等概率情况下，每个节点的查找概率均为1/n，其中n为节点数。因此，查找成功和不成功情况下的平均查找长度分别为：

• 查找成功的平均查找长度：(1+2+3+4+5+6+7+8)/8=4.5；
• 查找不成功的平均查找长度：(1+2+3+4+5+6+7+8)/9=4。