区间二叉树插入合并功能调试及代码优化求助

问题分析 #

当前代码存在两个核心问题导致(8-9)未合并到(4-25)：

1. 插入条件逻辑错误
   原insert函数的左右插入条件仅判断了插入区间完全小于当前节点区间（low < root->low && high < root->high）或完全大于（low > root->low && high > root->high），但对于部分重叠的情况（比如8-9和4-25），虽会进入合并分支，但后续合并逻辑存在执行漏洞。

2. 删除操作未正确更新树结构
   在insertIntersect函数中，调用delete(root, root->low)后未接收返回的新根节点，导致原树中相交节点并未被实际删除，自然无法完成合并。此外，递归遍历过程中直接修改树结构会导致遍历逻辑混乱，遗漏部分相交节点。

修复方案 #

1. 重构插入逻辑（核心修复） #

改为"先收集相交节点→删除相交节点→插入合并区间"的流程，避免遍历中修改树结构：

struct node *insert(struct node *root, int low, int high) {
    // 第一步：收集所有相交节点，计算合并后的区间范围
    int merge_low = low;
    int merge_high = high;
    struct node *intersect_nodes[100]; // 可根据需求改为动态数组
    int node_count = 0;
    collectIntersecting(root, low, high, &merge_low, &merge_high, intersect_nodes, &node_count);

    // 第二步：删除所有相交节点
    for (int i = 0; i < node_count; i++) {
        root = delete(root, intersect_nodes[i]->low);
    }

    // 第三步：插入合并后的新区间
    if (root == NULL) {
        return createNode(merge_low, merge_high);
    }
    struct node *curr = root;
    struct node *parent = NULL;
    // 按low值排序找到插入位置
    while (curr != NULL) {
        parent = curr;
        curr = merge_low < curr->low ? curr->left : curr->right;
    }
    if (merge_low < parent->low) {
        parent->left = createNode(merge_low, merge_high);
    } else {
        parent->right = createNode(merge_low, merge_high);
    }
    return root;
}

2. 添加相交节点收集函数 #

统一收集所有相交节点，避免遍历中修改树结构：

// 收集与目标区间相交的节点，并同步计算合并后的区间范围
void collectIntersecting(struct node *root, int low, int high, int *merge_low, int *merge_high, struct node **nodes, int *count) {
    if (root == NULL) return;
    // 区间重叠判断：[a,b]与[c,d]重叠的条件为 a <= d 且 c <= b
    if (root->low <= high && low <= root->high) {
        *merge_low = min(*merge_low, root->low);
        *merge_high = max(*merge_high, root->high);
        nodes[(*count)++] = root;
    }
    collectIntersecting(root->left, low, high, merge_low, merge_high, nodes, count);
    collectIntersecting(root->right, low, high, merge_low, merge_high, nodes, count);
}

3. 修复delete函数的内存泄漏 #

原delete函数未释放节点内存，添加free操作：

struct node *delete(struct node* root, int key)
{
    if(root == NULL) return root;
    
    if(key < root->low)
        root->left = delete(root->left, key);
    else if(key > root->low)
        root->right = delete(root->right, key);
    else {
        struct node *temp = root;
        if(root->left == NULL) {
            root = root->right;
            free(temp);
            return root;
        }
        else if(root->right == NULL) {
            root = root->left;
            free(temp);
            return root;
        }

        struct node *min = minValue(root->right);
        root->low = min->low;
        root->high = min->high;
        root->id = min->id;

        root->right = delete(root->right, root->low);
        free(temp);
    }
    return root;
}

优化建议 #

1. 统一排序规则：始终基于区间的low值构建二叉搜索树，保持树的有序性，便于后续查找、删除操作。
2. 动态内存优化：相交节点的收集使用malloc/realloc实现动态数组，避免固定大小数组的容量限制。
3. 封装重叠判断函数：将区间重叠逻辑单独封装，提升代码可读性：

   int intersect(int a_low, int a_high, int b_low, int b_high) {
       return (a_low <= b_high && b_low <= a_high);
   }
   

4. 避免递归中修改树：递归遍历过程中修改树结构会导致指针失效，优先采用"先收集后批量修改"的模式。

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