二叉搜索树叶子节点递归计数运行时错误排查求助

Hey there! Let's dig into why your leaf count function is crashing after working for empty and single-node trees. The fact that those basic cases pass tells us your baseline logic for null nodes and leaves is partially working—but something breaks when handling trees with more than one node. Here are the most likely issues and fixes:

1. Incorrect Order of Baseline Conditions #

The most common culprit here is checking if a node is a leaf before checking if the node itself is NULL. For example, if your code looks like this:

int number_of_leaves(Node* p) {
    // ❌ Wrong order: Accesses p->left/p->right before checking if p is NULL
    if (p->left == NULL && p->right == NULL) {
        return 1;
    }
    if (p == NULL) {
        return 0;
    }
    return number_of_leaves(p->left) + number_of_leaves(p->right);
}

When p is NULL, the first condition tries to dereference p->left, which triggers a segmentation fault. Even if your empty tree test works, this will crash when a non-leaf node has a NULL child (since the recursive call will pass NULL to the function).

Fix: #

Always check for NULL first, then check if the node is a leaf:

int number_of_leaves(Node* p) {
    // ✅ Handle null nodes first
    if (p == NULL) {
        return 0;
    }
    // Check if current node is a leaf
    if (p->left == NULL && p->right == NULL) {
        return 1;
    }
    // Recurse on left and right subtrees
    return number_of_leaves(p->left) + number_of_leaves(p->right);
}

2. Uninitialized Pointers (Wild Pointers) in Your Tree #

If your baseline logic is correct, the crash might come from invalid memory access due to uninitialized child pointers. When you create a non-leaf node, you must explicitly set any unused child pointers to NULL. For example:

// ❌ Bad: root->right is uninitialized (points to random memory)
Node* root = create_node(10);
root->left = create_node(5);

// ✅ Good: Explicitly set unused children to NULL
Node* root = create_node(10);
root->left = create_node(5);
root->right = NULL;

If a child pointer is left uninitialized, it becomes a "wild pointer" pointing to arbitrary memory. When your recursive function tries to access p->left or p->right on this invalid address, the program crashes.

3. Debugging Tips to Confirm the Issue #

Add simple debug prints to track which nodes your function is processing:

int number_of_leaves(Node* p) {
    printf("Processing node: %p | Left: %p, Right: %p\n", 
           p, 
           p ? p->left : NULL, 
           p ? p->right : NULL);
    if (p == NULL) {
        return 0;
    }
    if (p->left == NULL && p->right == NULL) {
        return 1;
    }
    return number_of_leaves(p->left) + number_of_leaves(p->right);
}

Right before the crash, you'll likely see a line where Left or Right is a random non-NULL address (indicating a wild pointer) or a NULL being accessed out of order.

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