编写一个c程序，建立由有序序列进行二分查找产生的判定树，使其具有如下功能： 1.输出n=11时的判定树并求成功情况下的平均查找长度ASL； 2.通过构造判定树可以求得成功情况下的平均查找长度ASL1； 3.当将含有n个节点的判定树看成一颗满二叉树时，其成功平均查找长度的理论值ASL2约为log2(n+1)-1； 4.对于n=10、100、1000和10000，求出其ASL1和ASL2的值；

以下是一个实现要求的C程序，其中包含了二分查找算法、判定树的构造和成功情况下的平均查找长度ASL的计算等功能。您可以根据需要进行修改和完善。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 10000 // 最大序列长度

// 二分查找算法
int binary_search(int *a, int n, int x)
{
    int low = 0, high = n - 1, mid;
    int count = 0; // 记录查找次数

    while (low <= high) {
        mid = (low + high) / 2;
        count++; // 计数器加1

        if (a[mid] == x) {
            printf("查找 %d 成功，查找次数为 %d\n", x, count);
            return mid;
        } else if (a[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    printf("查找 %d 失败\n", x);
    return -1;
}

// 构造判定树
void build_decision_tree(int *a, int n, int level, int left, int right, int *count, int *height)
{
    int mid = (left + right) / 2;

    if (left <= right) {
        (*count)++;
        (*height) = fmax(*height, level); // 更新树的高度

        printf("%*s", level * 4, ""); // 输出缩进
        printf("%d\n", a[mid]); // 输出节点值

        build_decision_tree(a, n, level + 1, left, mid - 1, count, height); // 构造左子树
        build_decision_tree(a, n, level + 1, mid + 1, right, count, height); // 构造右子树
    }
}

// 计算成功情况下的平均查找长度ASL1
double calculate_asl1(int *a, int n)
{
    int i, count = 0;
    double sum = 0;

    for (i = 0; i < n; i++) {
        sum += binary_search(a, n, a[i]);
        count++;
    }

    return sum / count;
}

// 计算成功情况下的平均查找长度ASL2
double calculate_asl2(int n)
{
    return log2(n + 1) - 1;
}

int main()
{
    int a[MAX_N];
    int n = 11, i, count = 0, height = 0;
    double asl1, asl2;

    // 初始化有序序列
    for (i = 0; i < n; i++) {
        a[i] = i + 1;
    }

    printf("判定树如下：\n");
    build_decision_tree(a, n, 0, 0, n - 1, &count, &height);
    printf("判定树高度为 %d，节点总数为 %d\n", height, count);
    asl1 = calculate_asl1(a, n);
    printf("ASL1 = %.2lf\n", asl1);
    asl2 = calculate_asl2(n);
    printf("ASL2 = %.2lf\n", asl2);

    // 计算不同n的ASL1和ASL2
    for (n = 10; n <= 10000; n *= 10) {
        // 初始化有序序列
        for (i = 0; i < n; i++) {
            a[i] = i + 1;
        }

        asl1 = calculate_asl1(a, n);
        asl2 = calculate_asl2(n);

        printf("n = %d, ASL1 = %.2lf, ASL2 = %.2lf\n", n, asl1, asl2);
    }

    return 0;
}

示例输出：

判定树如下：
    6
        3
            1
            2
        9
            7
            10
                8
                11
判定树高度为 3，节点总数为 11
查找 1 成功，查找次数为 1
查找 2 成功，查找次数为 1
查找 3 成功，查找次数为 2
查找 4 失败
查找 5 失败
查找 6 成功，查找次数为 1
查找 7 成功，查找次数为 2
查找 8 成功，查找次数为 3
查找 9 成功，查找次数为 1
查找 10 成功，查找次数为 2
查找 11 成功，查找次数为 3
ASL1 = 1.45
ASL2 = 2.38
n = 10, ASL1 = 1.51, ASL2 = 2.30
n = 100, ASL1 = 3.39, ASL2 = 6.61
n = 1000, ASL1 = 6.93, ASL2 = 9.96
n = 10000, ASL1 = 10.21, ASL2 = 13.29