如何计算二叉树根到所有叶子节点的平均距离（C语言实现）

先看你提供的代码，存在不少语法和逻辑问题，我来逐一拆解，然后给出正确的实现方案：

原代码的核心问题 #

• 语法错误：if条件里的表达式逻辑混乱，运算符优先级和赋值操作完全错误。比如(dist = findDistance(root->left)) >= 0 + (dist = findDistance(root->right)) >= 0，这里>=0 +会先计算加法，而且重复给dist赋值会覆盖之前的结果，完全不符合你的预期。
• 逻辑错误：root->data != NULL是无意义的比较——data是int类型，NULL是指针常量，两者类型不匹配，你应该判断当前节点是否是叶子节点（即left和right都为NULL）。
• 错误的平均计算逻辑：你试图让每个节点直接返回左右子树的平均距离加1，但实际上，平均距离需要统计所有叶子节点到根的距离总和，再除以叶子节点的总数，这种递归方式无法正确累计这两个关键值。
• 边界处理不当：空节点返回-1的逻辑虽然在叶子节点计算时能得到0（叶子的左右为空，返回-1加1等于0），但整体递归逻辑没有围绕“统计总和和叶子数”展开，导致结果错误。

正确实现方案 #

我们的核心目标是统计两个值：所有叶子到根的距离总和、叶子节点的数量，最终平均距离 = 总和 / 叶子数（注意处理浮点数精度）。下面提供两种方案，其中一种用到你提到的“在Node结构体新增字段”的思路：

方案1：修改Node结构体，新增统计字段 #

我们给每个节点新增两个字段，分别记录当前子树的叶子节点数量，以及所有叶子到当前节点的距离总和。递归遍历过程中更新这些字段，最后根节点的统计值就能算出平均距离。

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

// 修改后的二叉树节点结构体，新增统计字段
struct Node {
    int data;
    Node *left, *right;
    int leaf_count;    // 当前子树的叶子节点数量
    int total_dist;    // 当前子树所有叶子到本节点的距离总和
};

// 创建新节点的辅助函数
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    node->leaf_count = 0;
    node->total_dist = 0;
    return node;
}

// 递归更新每个节点的leaf_count和total_dist
void calculateStats(struct Node* root) {
    if (root == NULL) return;

    // 如果是叶子节点，自身就是一个叶子，到自己的距离为0
    if (root->left == NULL && root->right == NULL) {
        root->leaf_count = 1;
        root->total_dist = 0;
        return;
    }

    // 递归处理左右子树
    calculateStats(root->left);
    calculateStats(root->right);

    // 合并左右子树的统计结果：
    // 叶子数是左右叶子数之和
    root->leaf_count = (root->left ? root->left->leaf_count : 0) + 
                       (root->right ? root->right->leaf_count : 0);
    // 总距离是左右子树的总距离 + 左右叶子数（因为每个叶子到当前节点的距离比到子节点多1）
    root->total_dist = (root->left ? root->left->total_dist + root->left->leaf_count : 0) + 
                       (root->right ? root->right->total_dist + root->right->leaf_count : 0);
}

// 计算平均距离的入口函数
double findAverageDistance(struct Node* root) {
    if (root == NULL) return 0.0; // 空树返回0或者根据需求处理

    calculateStats(root);
    // 避免除以0（树只有根节点的情况，叶子数是1，总距离0）
    if (root->leaf_count == 0) return 0.0;
    return (double)root->total_dist / root->leaf_count;
}

// 测试示例
int main() {
    // 构建一个简单的二叉树
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("平均距离：%.2f\n", findAverageDistance(root));
    // 预期结果：叶子是4、5、3，距离分别是2、2、1，总和5，平均5/3≈1.67

    return 0;
}

方案2：不修改结构体，用指针传递统计值 #

如果不想修改Node结构体，可以用两个指针变量（传递总和和叶子数的地址），在递归中累计这两个值：

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

struct Node {
    int data;
    Node *left, *right;
};

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// 递归统计：current_dist是当前节点到根的距离
void countLeavesAndDist(struct Node* root, int current_dist, int* total_dist, int* leaf_count) {
    if (root == NULL) return;

    // 叶子节点：累计距离和叶子数
    if (root->left == NULL && root->right == NULL) {
        *total_dist += current_dist;
        *leaf_count += 1;
        return;
    }

    // 递归处理左右子树，距离加1
    countLeavesAndDist(root->left, current_dist + 1, total_dist, leaf_count);
    countLeavesAndDist(root->right, current_dist + 1, total_dist, leaf_count);
}

double findAverageDistance(struct Node* root) {
    if (root == NULL) return 0.0;

    int total_dist = 0;
    int leaf_count = 0;
    countLeavesAndDist(root, 0, &total_dist, &leaf_count);

    if (leaf_count == 0) return 0.0;
    return (double)total_dist / leaf_count;
}

// 测试示例
int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("平均距离：%.2f\n", findAverageDistance(root));
    return 0;
}

说明 #

两种方案都能正确计算平均距离：

• 方案1通过结构体字段存储子树的统计信息，适合需要多次查询或者需要子树统计数据的场景；
• 方案2更轻量，不需要修改原有结构体，适合一次性计算的场景。

最后注意处理空树或者只有根节点的边界情况，避免除以0的错误。

内容的提问来源于stack exchange，提问作者linorkhbur