C语言迭代实现二叉搜索树节点删除的问题排查与修复

结构体定义 #

typedef int element;
typedef struct node
{
    element data;
    struct node *left,*right;
} *Btree;
typedef Btree BST;

问题描述 #

要求实现递归函数删除BST中的元素e，删除成功返回1，失败返回0。将递归代码转为迭代实现后，运行指定输入（初始BST以6为根，左子节点3、右子节点8；3的左子节点1、右子节点5，依次删除1、5、8、-5、0、4、23）时，结果为空，而预期结果为根6的左子节点3。

用户提供的代码 #

迭代实现（存在问题） #

int delete_BST(BST *B , element e)
{
    if(!(*B)) return 0;
    BST t = *B;
    while(1)
    {
        if(t->data < e) t = t->right;
        if(t->data > e) t = t->left;
        else
        {
            if(t->left && t->right)
            {
                BST maxleft = t->left;
                while(maxleft->right)
                    maxleft = maxleft->right;
                t->data = maxleft->data;
                t = t->left;
                e = maxleft->data;
            }
            else
            {
                BST temp = t;
                if(!t->left) t = t->right;
                else if(!t->right) t = t->left;
                free(temp);
                break;
            }
        }
    }
    return 1;
}

递归实现（正确） #

int delete_BST(BST *B , element e)
{
    if(!(*B)) return 0;
    if((*B)->data < e) return delete_BST(&(*B)->right, e);
    else if((*B)->data > e) return delete_BST(&(*B)->left, e);
    else
    {
        BST temp;
        if((*B)->left && (*B)->right)
        {
            temp = max_BST((*B)->left);
            (*B)->data = temp->data;
            delete_BST(&((*B)->left), temp->data);
        }
        else
        {
            temp = *B;
            if(!(*B)->left) *B = (*B)->right;
            else if(!(*B)->right) *B = (*B)->left;
            free(temp);
        }   
    }
    return 1;
}

问题分析 #

迭代代码的核心问题在于没有维护父节点指针，也没有正确更新原树的指针链接：

• 递归实现通过传递指针的指针（如&(*B)->left）直接修改树的节点链接；但迭代代码仅操作局部变量t，修改t不会改变原树的实际结构，导致删除操作未真正生效，后续逻辑还会破坏树结构。
• 未处理目标元素不存在的情况：查找不存在的元素（如-5、0）时，t会逐步变为NULL，此时访问t->data会触发空指针错误，且函数错误返回1（表示删除成功）。
• 处理双子女节点时，仅将t指向左子树，但未跟踪父节点来删除左子树的最大节点，导致该节点无法被正确移除，后续逻辑混乱。

修复方案 #

修复后的迭代代码需要：

• 跟踪当前节点的父节点，以及当前节点是父节点的左子还是右子节点；
• 正确处理元素不存在的情况；
• 通过父节点的指针链接更新树的结构；
• 处理双子女节点时，维护父节点信息来删除左子树的最大节点。

修复后的迭代代码 #

// 辅助函数：查找BST中最大值节点的父节点和节点本身
void findMax(BST node, BST *parent, BST *maxNode) {
    *parent = NULL;
    *maxNode = node;
    while ((*maxNode)->right != NULL) {
        *parent = *maxNode;
        *maxNode = (*maxNode)->right;
    }
}

int delete_BST(BST *B, element e) {
    BST current = *B;
    BST parent = NULL;
    // 第一步：查找目标节点及其父节点
    while (current != NULL && current->data != e) {
        parent = current;
        if (e < current->data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    // 目标元素不存在
    if (current == NULL) {
        return 0;
    }

    // 情况1：目标节点有两个子节点
    if (current->left != NULL && current->right != NULL) {
        BST maxParent, maxNode;
        findMax(current->left, &maxParent, &maxNode);
        // 替换当前节点的值
        current->data = maxNode->data;
        // 现在需要删除maxNode，将其视为单节点或叶子节点的情况
        current = maxNode;
        parent = maxParent;
    }

    // 情况2：目标节点只有一个子节点或没有子节点
    BST child = NULL;
    if (current->left != NULL) {
        child = current->left;
    } else {
        child = current->right;
    }

    // 更新父节点的链接
    if (parent == NULL) {
        // 删除的是根节点
        *B = child;
    } else if (parent->left == current) {
        parent->left = child;
    } else {
        parent->right = child;
    }

    free(current);
    return 1;
}

修复点说明 #

1. 增加父节点跟踪：通过parent变量记录当前节点的父节点，确保能正确更新树的指针链接；
2. 处理元素不存在的情况：查找循环结束后判断current是否为NULL，直接返回0；
3. 双子女节点处理优化：通过辅助函数找到左子树的最大节点及其父节点，替换值后将问题转化为删除该最大节点（单节点或叶子节点）；
4. 正确更新树结构：根据父节点的位置（左子/右子/根节点），修改对应的指针，确保树的链接正确。

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