c语言求已知二叉排序树的平均查找长度

已知一棵二叉排序树，我们可以通过计算其平均查找长度（Average Search Length，ASL）来评估其查找效率。二叉排序树的ASL计算公式如下：

ASL = (sum_depth + n) / n

其中，sum_depth为所有节点的深度之和，n为节点总数。

下面是一个C语言求已知二叉排序树平均查找长度的代码：

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

/* 定义二叉树节点结构体 */
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

/* 插入节点 */
void insert(TreeNode** root, int val) {
    if (*root == NULL) {
        *root = (TreeNode*)malloc(sizeof(TreeNode));
        (*root)->val = val;
        (*root)->left = NULL;
        (*root)->right = NULL;
    } else if (val < (*root)->val) {
        insert(&((*root)->left), val);
    } else {
        insert(&((*root)->right), val);
    }
}

/* 计算二叉排序树的节点总数 */
int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else {
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
}

/* 计算二叉排序树所有节点的深度之和 */
int sumDepth(TreeNode* root, int depth) {
    if (root == NULL) {
        return 0;
    } else {
        return depth + sumDepth(root->left, depth + 1) + sumDepth(root->right, depth + 1);
    }
}

/* 计算二叉排序树的平均查找长度 */
float calculateASL(TreeNode* root) {
    int n = countNodes(root);
    int sum_depth = sumDepth(root, 0);
    float asl = (float)(sum_depth + n) / n;
    return asl;
}

int main() {
    TreeNode* root = NULL;
    insert(&root, 5);
    insert(&root, 3);
    insert(&root, 1);
    insert(&root, 4);
    insert(&root, 7);
    insert(&root, 6);
    insert(&root, 9);

    float asl = calculateASL(root);
    printf("ASL = %.2f\n", asl);

    return 0;
}

在这个代码中，我们先定义了二叉树节点结构体，然后实现了插入节点、计算节点总数、计算所有节点的深度之和和计算平均查找长度的函数。在主函数中，我们创建了一棵二叉排序树，并计算了其平均查找长度。