依次读入给定的整数序列{7，16，4，8，20，9} 1)构造一棵二叉排序树,计算在等概率情况下该二又排序树的平均查找长度 ASL; 2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。

1) 构造二叉排序树的过程：

首先将7作为根节点，然后依次将16、4、8、20、9插入到二叉排序树中。

插入16时，由于16比7大，所以将16作为7的右子节点。

插入4时，由于4比7小，所以将4作为7的左子节点。

插入8时，由于8比7大，所以将8作为16的左子节点。

插入20时，由于20比7大，所以将20作为根节点的右子节点，由于20比16大，所以将20作为16的右子节点。

插入9时，由于9比7大，所以将9作为8的右子节点，由于9比16小，所以将9作为7的右子节点的左子节点。

最终构造出的二叉排序树如下所示：

       7
      / \
     4   16
        /  \
       8   20
           /
          9

在等概率情况下，该二叉排序树的平均查找长度 ASL = (1+2+2+3+3+3)/6 = 2.33

2) 构造平均查找长度最小的二叉排序树的过程：

首先将序列按照非降序排列，得到序列{4，7，8，9，16，20}。

接着可以使用动态规划的方法构造平均查找长度最小的二叉排序树，具体过程如下：

1. 对于序列中的每一个元素i，将其作为根节点构造一棵二叉排序树，此时二叉排序树的平均查找长度为wi。

2. 对于序列中的每一个子序列[i,j]，计算出所有可能的二叉排序树的平均查找长度之和，选取其中最小的作为子序列[i,j]的平均查找长度w(i,j)。

3. 根据递推式计算出序列的平均查找长度，即W(1,n)，其中n为序列中元素的个数。

递推式为: W(i,j) = min{W(i,r-1)+W(r+1,j)+w(i,j)} (i<=r<=j)

最终得到的平均查找长度最小的二叉排序树如下所示：

       9
      / \
     7   16
    / \    \
   4   8   20

满足要求的序列中的第一个元素为4。