求二叉树查找成功的平均长度，用C语言实现

二叉树查找成功的平均长度可以通过以下公式计算：

$ASL = \frac{\sum_{i=1}^{n} d_i}{n}$

其中，$ASL$表示平均查找长度，$d_i$表示查找成功的第$i$个元素的深度，$n$表示元素个数。

下面是用C语言实现二叉树的代码，包括插入、查找和计算平均查找长度的函数：

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

// 二叉树节点结构体
typedef struct node {
    int value;
    struct node *left, *right;
} Node;

// 二叉树插入函数
void insert(Node **root, int value) {
    if (*root == NULL) {
        *root = (Node *) malloc(sizeof(Node));
        (*root)->value = value;
        (*root)->left = (*root)->right = NULL;
        return;
    }

    if (value < (*root)->value)
        insert(&((*root)->left), value);
    else
        insert(&((*root)->right), value);
}

// 二叉树查找函数
int search(Node *root, int value, int depth) {
    if (root == NULL)
        return -1;

    if (root->value == value)
        return depth;

    if (value < root->value)
        return search(root->left, value, depth + 1);
    else
        return search(root->right, value, depth + 1);
}

// 计算二叉树查找成功的平均长度
float average_search_length(Node *root, int n) {
    int sum_depth = 0;
    for (int i = 1; i <= n; i++) {
        int depth = search(root, i, 0);
        if (depth == -1) {
            printf("Error: value %d not found in tree!\n", i);
            return -1;
        }
        sum_depth += depth;
    }
    return (float) sum_depth / n;
}

int main() {
    Node *root = NULL;

    // 插入元素
    insert(&root, 5);
    insert(&root, 3);
    insert(&root, 7);
    insert(&root, 1);
    insert(&root, 4);
    insert(&root, 6);
    insert(&root, 8);

    // 计算平均查找长度
    float asl = average_search_length(root, 8);
    printf("Average search length: %.2f\n", asl);

    return 0;
}

以上代码中，我们首先定义了二叉树节点的结构体，包含一个值和左右子节点指针。插入函数使用递归实现，查找函数也使用递归实现，返回查找成功的元素深度。计算平均查找长度的函数则遍历所有元素，依次调用查找函数，累加深度并计算平均值。