使用指针的C语言递归函数为何崩溃？

核心错误：内存分配大小错误 #

你的createNode函数里，malloc的参数用了sizeof(tree)，这是致命问题：

tree node = (tree) malloc(sizeof(tree));

因为tree是struct node *的别名，也就是指针类型，sizeof(tree)得到的是指针的字节数（通常是4或8字节，取决于系统），但struct node的实际大小是int + 两个指针，远大于指针的大小。这会导致你只分配了一小块内存，后续给node->key、node->left、node->right赋值时，会越界写入堆内存，破坏堆的结构，进而导致程序在后续操作（比如递归访问节点、free内存）时随机崩溃，这就是为什么你看到的输出不稳定的原因。

修复方法很简单，把sizeof(tree)改成sizeof(struct node)，或者更稳妥的sizeof(*node)（因为node是指向struct node的指针，*node就是结构体本身，这样即使typedef修改了，代码也不会出错）：

tree createNode(int n, tree l, tree r){
    tree node = (tree) malloc(sizeof(struct node));
    // 或者用 sizeof(*node)，更鲁棒
    // tree node = (tree) malloc(sizeof(*node));
    node->key = n;
    node->left = l;
    node->right = r;
    return node;
}

次要问题：未处理空指针访问 #

你的leafprod函数没有判断输入的t是否为NULL，如果某个递归调用传入了NULL（比如极端情况，树是空的），直接访问t->key会触发空指针异常。另外，从逻辑上来说，空树的叶子节点乘积应该是1（乘法的单位元），所以可以在函数开头加上空指针判断：

int leafprod(tree t){
    if (t == NULL) return 1; // 空节点返回1，不影响乘积结果
    printf("%d\n", t->key);

    if (t->left == NULL){
        if (t->right == NULL){
            printf("$1\n\n");
            return t->key;
        }
        printf("$2\n\n");
        return leafprod(t->right);
    }
    if (t->right == NULL){
        printf("$3\n\n");
        return leafprod(t->left);
    }
    printf("$4\n\n");
    return leafprod(t->left) * leafprod(t->right);
}

修复后的测试结果 #

把这两处修改后，你的main函数运行会稳定输出正确结果：
运行流程会输出：

4
$4

2
$1

3
$3

1
$1

end: 2

（叶子节点是2和1，乘积是2*1=2，符合预期）

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