递归函数传递双指针时触发Segmentation Fault的问题排查

1. 双指针成员设计错误：将QuadTree的子节点NW/NE/SW/SE定义为QuadTree**是核心问题。双指针在此场景下完全没必要，反而会打乱内存访问逻辑——比如需要先给一级指针分配空间才能访问二级指针，稍不注意就会触发空指针解引用，这就是后续调用出现段错误的主要原因。之前单指针时丢失引用，根本问题不在结构体成员类型，而是递归函数传递指针的方式不对。

2. 空指针未校验：调用AABB_cotains_point或QuadTree_points_size前，没有检查当前QuadTree指针是否为NULL，直接解引用空指针必然触发段错误。

3. 细分函数内存分配逻辑错误：如果坚持用双指针，你可能错误地直接给NW（QuadTree**类型）赋值malloc的结果，而非给*NW赋值，导致NW本身指向非法内存区域，后续访问子节点时出错。

1. 修正QuadTree结构体，子节点改回单指针 #

把结构体里的子节点成员从QuadTree**改回QuadTree*，让内存管理回归清晰：

typedef struct AABB {
    float x, y;
    float width, height;
} AABB;

typedef struct Point {
    float x, y;
} Point;

typedef struct QuadTree {
    AABB boundary;
    int capacity;
    Point* points;
    int point_count;
    struct QuadTree* NW; // 改回单指针
    struct QuadTree* NE;
    struct QuadTree* SW;
    struct QuadTree* SE;
} QuadTree;

2. 调整递归插入函数，用双指针参数传递节点 #

之前单指针丢失引用，是因为递归时修改的是形参指针，父节点的子节点指针不会同步。现在通过传递QuadTree**（指向子节点指针的指针），让子节点的修改能同步到父节点：

void QuadTree_insert(QuadTree** node, Point p) {
    // 初始化空节点
    if (*node == NULL) {
        *node = malloc(sizeof(QuadTree));
        // 根据业务逻辑初始化boundary、capacity等成员
        (*node)->point_count = 0;
        (*node)->NW = NULL;
        (*node)->NE = NULL;
        (*node)->SW = NULL;
        (*node)->SE = NULL;
        (*node)->points = malloc(sizeof(Point) * (*node)->capacity);
    }

    // 检查点是否在当前节点边界内
    if (!AABB_contains_point(&(*node)->boundary, p)) {
        return;
    }

    // 当前节点还有空间，直接添加点
    if ((*node)->point_count < (*node)->capacity) {
        (*node)->points[(*node)->point_count++] = p;
        return;
    }

    // 细分节点（如果还没细分）
    if ((*node)->NW == NULL) {
        QuadTree_subdivide(*node);
    }

    // 递归插入到子节点
    QuadTree_insert(&(*node)->NW, p);
    QuadTree_insert(&(*node)->NE, p);
    QuadTree_insert(&(*node)->SW, p);
    QuadTree_insert(&(*node)->SE, p);
}

3. 完善细分函数的内存分配 #

细分时为每个子节点分配内存并初始化边界，确保子节点指针不为NULL：

void QuadTree_subdivide(QuadTree* node) {
    float cx = node->boundary.x;
    float cy = node->boundary.y;
    float half_w = node->boundary.width / 2.0f;
    float half_h = node->boundary.height / 2.0f;

    // 初始化NW子节点
    node->NW = malloc(sizeof(QuadTree));
    node->NW->boundary = (AABB){cx - half_w, cy + half_h, half_w, half_h};
    node->NW->capacity = node->capacity;
    node->NW->points = malloc(sizeof(Point) * node->capacity);
    node->NW->point_count = 0;
    node->NW->NW = NULL;
    node->NW->NE = NULL;
    node->NW->SW = NULL;
    node->NW->SE = NULL;

    // 同理初始化NE、SW、SE子节点
    node->NE = malloc(sizeof(QuadTree));
    node->NE->boundary = (AABB){cx + half_w, cy + half_h, half_w, half_h};
    node->NE->capacity = node->capacity;
    node->NE->points = malloc(sizeof(Point) * node->capacity);
    node->NE->point_count = 0;
    node->NE->NW = NULL;
    node->NE->NE = NULL;
    node->NE->SW = NULL;
    node->NE->SE = NULL;

    node->SW = malloc(sizeof(QuadTree));
    node->SW->boundary = (AABB){cx - half_w, cy - half_h, half_w, half_h};
    node->SW->capacity = node->capacity;
    node->SW->points = malloc(sizeof(Point) * node->capacity);
    node->SW->point_count = 0;
    node->SW->NW = NULL;
    node->SW->NE = NULL;
    node->SW->SW = NULL;
    node->SW->SE = NULL;

    node->SE = malloc(sizeof(QuadTree));
    node->SE->boundary = (AABB){cx + half_w, cy - half_h, half_w, half_h};
    node->SE->capacity = node->capacity;
    node->SE->points = malloc(sizeof(Point) * node->capacity);
    node->SE->point_count = 0;
    node->SE->NW = NULL;
    node->SE->NE = NULL;
    node->SE->SW = NULL;
    node->SE->SE = NULL;
}

4. 全局添加空指针校验 #

在所有访问QuadTree成员的函数里，先检查指针是否为NULL，避免非法访问：

bool AABB_contains_point(AABB* aabb, Point p) {
    if (aabb == NULL) return false;
    return (p.x >= aabb->x - aabb->width &&
            p.x <= aabb->x + aabb->width &&
            p.y >= aabb->y - aabb->height &&
            p.y <= aabb->y + aabb->height);
}

int QuadTree_points_size(QuadTree* node) {
    if (node == NULL) return 0;
    int count = node->point_count;
    count += QuadTree_points_size(node->NW);
    count += QuadTree_points_size(node->NE);
    count += QuadTree_points_size(node->SW);
    count += QuadTree_points_size(node->SE);
    return count;
}

5. 添加内存清理函数（避免泄漏） #

使用完四叉树后，递归释放所有节点的内存：

void QuadTree_destroy(QuadTree* node) {
    if (node == NULL) return;
    QuadTree_destroy(node->NW);
    QuadTree_destroy(node->NE);
    QuadTree_destroy(node->SW);
    QuadTree_destroy(node->SE);
    free(node->points);
    free(node);
}

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