假设一个有序序列 { 12, 25, 46, 62, 78, 80 }, 画出进行二分查找的判定树，并计算查找成功的ASL和查找不成功的ASL。

二分查找的判定树如下图所示：

        62
       /  \
     25   78
    /  \    \
  12  46   80

对于成功的查找，每个关键字的ASL均为该节点的深度，因此：

- 12: 1
- 25: 2
- 46: 2
- 62: 1
- 78: 2
- 80: 3

ASL = (1 + 2 + 2 + 1 + 2 + 3) / 6 = 1.83

对于不成功的查找，每次查找都要走到叶子节点，因此所有关键字的ASL均为深度加一，即：

ASL = (1 + 2 + 2 + 2 + 2 + 2 + 1) / 7 = 1.71

相关问题

有序关键字序列{13, 18, 25, 39, 42, 55, 62, 87}，画出其二分查找判定树，并计算查找成功的平均查找长度（ASL）。

好的，我知道了。这是一个关于二分查找的问题。首先，我们来画出这个有序关键字序列的二分查找判定树。根据二分查找的原理，我们可以将序列分成左右两个子序列，然后在其中一个子序列中继续查找，直到找到目标元素或者序列为空为止。

下面是判定树的示意图：

                             42
                            /  \
                          25    62
                         /  \   / \
                       18   39 55  87
                      /  \
                     13  (NIL)

其中，NIL表示空节点。根据判定树，我们可以得到以下查找成功的平均查找长度（ASL）：

ASL = (1/8)*[1 + 2 + 2 + 3 + 3 + 3 + 3 + 4] = 2.625

所以，对于这个有序关键字序列，二分查找的平均查找长度为2.625。

二分查找判定树怎么画

二分查找判定树的画法如下：

1. 首先，根据给定的序列长度n，确定二分查找判定树的最大满二叉树结构。最大满二叉树是指除了最底层的叶子节点外，每一层都是满的二叉树。

2. 然后，计算剩余的结点个数。如果序列长度n为奇数，左右子树的结点个数相等；如果序列长度n为偶数，左子树的结点个数等于右子树的结点个数减1。

3. 接下来，按照上述规律将剩余的结点依次填入最底层，形成二分查找判定树的树形。

4. 最后，按照中序遍历的顺序，将给定的序列依次填入各个结点。

通过以上步骤，就可以画出二分查找判定树。