求助：实现四叉树中黑色像素下落的Gravity函数

我需要编写一个Gravity函数，让四叉树中的所有黑色像素在下方存在白色像素时“下落”。调用Gravity(Qt1)应得到符合预期的Qt2（黑色像素落到对应列的底部）。

四叉树结构体定义 #

typedef struct Qtree{
    bool allblack;
    struct Qtree * son[4];
}Qtree;

已实现的辅助函数（修正原代码语法错误后） #

• 创建黑色像素：

Qtree* create_Black(){
    Qtree* I = malloc(sizeof(Qtree)); // 修正原代码语法错误：-> 改为 =
    I->allblack = true; // 补充原代码遗漏的全黑标记赋值
    I->son[0] = I->son[1] = I->son[2] = I->son[3] = NULL; // 补充原代码遗漏的分号
    return I;
}

• 创建白色像素：

Qtree* create_White(){ 
    return NULL;
}

• 基于四个子节点创建四叉树：

Qtree* create_Comp(Qtree* i0, Qtree* i1, Qtree* i2, Qtree* i3){ // 修正原代码参数错误：Qtree i3 改为 Qtree* i3
    Qtree* I = malloc(sizeof(Qtree));         
    I->allblack = false; // 复合节点默认非全黑，需后续判断
    I->son[0] = i0;         
    I->son[1] = i1;
    I->son[2] = i2;
    I->son[3] = i3;
    return I;
}

解决方案实现 #

核心思路 #

重力下落逻辑分为两步：

1. 递归处理子树：先深入每个子节点，让子树内部的黑色像素先完成下落，确保子树结构符合重力规则。
2. 列内像素调整：将当前节点视为2x2网格（四个子节点对应左上、右上、左下、右下），对每一列（左列：左上+左下；右列：右上+右下）进行调整，把黑色像素移动到列的底部。
3. 节点合并优化：调整后检查四个子节点是否可合并为单一颜色节点，减少四叉树复杂度。

完整Gravity函数代码 #

// 辅助函数：判断节点是否为黑色（单像素或全黑复合节点）
bool is_black(Qtree* node) {
    if (node == NULL) return false;
    // 单像素节点：son全为NULL且allblack为true
    if (node->son[0] == NULL && node->son[1] == NULL && node->son[2] == NULL && node->son[3] == NULL) {
        return node->allblack;
    }
    // 复合节点：直接读取allblack标记
    return node->allblack;
}

// 辅助函数：判断节点是否为白色
bool is_white(Qtree* node) {
    return node == NULL;
}

Qtree* Gravity(Qtree* root) {
    // 递归终止：白色节点直接返回
    if (is_white(root)) {
        return create_White();
    }

    // 黑色单像素无需移动，直接返回
    if (root->son[0] == NULL && root->son[1] == NULL && root->son[2] == NULL && root->son[3] == NULL) {
        return create_Black();
    }

    // 1. 递归处理四个子节点，完成子树的重力下落
    Qtree* i0 = Gravity(root->son[0]); // 左上
    Qtree* i1 = Gravity(root->son[1]); // 右上
    Qtree* i2 = Gravity(root->son[2]); // 左下
    Qtree* i3 = Gravity(root->son[3]); // 右下

    // 2. 处理左列：左上(i0) 与 左下(i2)，黑色落到下方
    if (is_white(i2) && is_black(i0)) {
        Qtree* temp = i0;
        i0 = i2;
        i2 = temp;
    }

    // 3. 处理右列：右上(i1) 与 右下(i3)，黑色落到下方
    if (is_white(i3) && is_black(i1)) {
        Qtree* temp = i1;
        i1 = i3;
        i3 = temp;
    }

    // 4. 检查是否可合并为单一颜色节点
    bool all_black = is_black(i0) && is_black(i1) && is_black(i2) && is_black(i3);
    bool all_white = is_white(i0) && is_white(i1) && is_white(i2) && is_white(i3);

    if (all_black) {
        free(i0); free(i1); free(i2); free(i3);
        return create_Black();
    }
    if (all_white) {
        free(i0); free(i1); free(i2); free(i3);
        return create_White();
    }

    // 无法合并则创建复合节点
    return create_Comp(i0, i1, i2, i3);
}

关键说明 #

• 递归优先级：必须先处理子节点再调整当前节点，否则子树内部的黑色像素未完成下落，当前节点的调整会失去意义。
• 列调整逻辑：仅当下方为白色、上方为黑色时才交换，其他情况无需操作（比如下方已经是黑色，无需调整）。
• 内存管理：合并节点时释放子节点内存，避免泄漏；可额外实现destroy_Qtree函数用于整体销毁四叉树。

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