C语言二叉树计数程序运行触发Segmentation fault段错误排查

编写C语言二叉树遍历程序，目标是统计树中节点值大于等于入参指定阈值的节点总数量。测试运行时程序仅遍历2个节点就触发段错误，错误定位到代码行return count + count_values(value, here) + count_values(value, current);，原始错误代码如下：

typedef struct BinaryTree {
    int val;
    struct BinaryTree *left;
    struct BinaryTree *right;
} BinaryTree;

BinaryTree *build_tree(int value, BinaryTree *leftnode, BinaryTree *rightnode) {
    BinaryTree *out = calloc(1, sizeof(BinaryTree));
    out->val = value;
    out->leftnode = leftnode;
    out->rightnode = rightnode;

    return out;
}

int count_values(int value, BinaryTree *tree) {
  
    BinaryTree *current = tree;
    BinaryTree *here = current;
    int count = 0;

    if (current != NULL) {
        printf("Value in tree is not NULL\n");

        if (current->val < value) {
            printf("%d < %d\n", current->val, value);
            printf("Count value: %d\n", count);
            here = current->leftnode;
            count_values(value, here);
            current = current->rightnode;
            count_values(value, current);

        } else if (current->val == value) {
            printf("%d = %d\n", current->val, value);
            count++;
            printf("Count value: %d\n", count);
            here = current->leftnode;
            count_values(value, here);
            current = current->rightnode;
            count_values(value, current);
        } else {
            printf("%d > %d\n", current->val, value);
            count++;
            printf("Count value: %d\n", count);
            here = current->leftnode;
            count_values(value, here);
            current = current->rightnode;
            count_values(value, current);
        }
    }
        
    return count + count_values(value, here) + count_values(value, current);
}

int main(void) {
    BinaryTree *tree =
        build_tree(14, build_tree(3, NULL, NULL),
                   build_tree(15, NULL, build_tree(42, NULL, NULL)));

    //path is 14->15->42
    int count = count_values(42, tree);
    printf("should have a count of 1, got %d\n", count);

    count = count_values(14, tree);
    printf("should have a count of 3, got %d\n", count);

    return 0;
}

• 结构体成员名笔误：结构体定义中左右子节点指针命名为left、right，但build_tree函数和遍历逻辑中错误使用了leftnode、rightnode访问成员，首先就会触发编译错误。
• 递归无终止条件导致无限递归栈溢出：当递归传入空指针时，函数不会进入current != NULL的分支，但return语句仍然会对here、current（此时均为NULL）再次发起递归调用，递归永远不会终止，很快耗尽栈空间触发段错误，这是崩溃的直接原因。
• 重复递归+返回值丢失：if分支内已经手动调用两次count_values遍历左右子树，return语句又会重复遍历；且分支内的递归调用没有接收返回值，就算不崩溃，子树的计数结果也会全部丢失，统计结果完全错误。
• 缺失必要头文件：代码使用了printf、calloc等标准库函数，但未引入<stdio.h>和<stdlib.h>，会触发隐式声明警告。

1. 统一结构体成员命名，所有位置统一使用left、right访问左右子节点指针
2. 补全缺失的标准库头文件
3. 明确递归终止条件：传入节点为NULL时直接返回0，不再继续递归
4. 简化递归逻辑：去掉重复的递归调用，当前节点的统计值 = 当前节点是否满足阈值（满足为1，不满足为0） + 左子树统计结果 + 右子树统计结果，直接返回累加值即可。

修复后的完整代码：

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

typedef struct BinaryTree {
    int val;
    struct BinaryTree *left;
    struct BinaryTree *right;
} BinaryTree;

BinaryTree *build_tree(int value, BinaryTree *left, BinaryTree *right) {
    BinaryTree *out = calloc(1, sizeof(BinaryTree));
    out->val = value;
    out->left = left;
    out->right = right;
    return out;
}

int count_values(int threshold, BinaryTree *tree) {
    // 递归终止：空节点返回0
    if (tree == NULL) {
        return 0;
    }
    int count = 0;
    // 当前节点满足阈值则计数+1
    if (tree->val >= threshold) {
        count = 1;
    }
    // 累加左右子树的计数结果
    count += count_values(threshold, tree->left);
    count += count_values(threshold, tree->right);
    return count;
}

int main(void) {
    BinaryTree *tree =
        build_tree(14, build_tree(3, NULL, NULL),
                   build_tree(15, NULL, build_tree(42, NULL, NULL)));

    int count = count_values(42, tree);
    printf("should have a count of 1, got %d\n", count);

    count = count_values(14, tree);
    printf("should have a count of 3, got %d\n", count);

    return 0;
}

should have a count of 1, got 1
should have a count of 3, got 3

程序无崩溃，统计结果完全符合预期。

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