C语言递归删除二叉搜索树节点触发Segmentation fault问题求助

架构老林

2026-7-3

二叉搜索树单子女节点删除的段错误修复

尝试用递归方式删除二叉搜索树中带有一个子节点的节点时，程序能打印部分数据，但在删除节点的后续值处触发Segmentation fault错误。以下是问题代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node {
    int i;
    struct Node *leftChild;
    struct Node *rightChild;
};

struct Node *insertANodeInBST(struct Node *node, int currentValue) {
    if (node == NULL) {
        node = (struct Node *) malloc(sizeof(struct Node));
        node->i = currentValue;
        node->leftChild = NULL;
        node->rightChild = NULL;
        return node;
    }

    if (currentValue == node->i) {
        return node;
    }
    if (currentValue < node->i) {
        node->leftChild = insertANodeInBST(node->leftChild, currentValue);
    }
    if (currentValue > node->i) {
        node->rightChild = insertANodeInBST(node->rightChild, currentValue);
    }
    return node;
}

struct Node *insertDataInBST(struct Node *node) {
    node = insertANodeInBST(node, 8);
    node = insertANodeInBST(node, 3);
    node = insertANodeInBST(node, 1);
    node = insertANodeInBST(node, 6);
    node = insertANodeInBST(node, 10);
    node = insertANodeInBST(node, 14);
    node = insertANodeInBST(node, 7);
    return node;
}

void inOrder(struct Node *node) {
    if (node == NULL) {
        return;
    }
    inOrder(node->leftChild);
    printf("%d ", node->i);
    inOrder(node->rightChild);
}

struct Node *searchForANode(struct Node *node, int value) {
    if (node == NULL || node->i == value) {
        return node;
    }

    if (value < node->i) {
        return searchForANode(node->leftChild, value);
    }
    if (value > node->i) {
        return searchForANode(node->rightChild, value);
    }
}


bool doesThisNodeExist(struct Node *node, int value) {
    if (node == NULL) {
        return false;
    }
    if (node->i == value) {
        return true;
    }

    if (value < node->i) {
        return doesThisNodeExist(node->leftChild, value);
    }

    if (value > node->i) {
        return doesThisNodeExist(node->rightChild, value);
    }
}

struct Node *deleteANode(struct Node *node, int value) {
    if (!doesThisNodeExist(node, value) || node == NULL) {
        return NULL;
    }

    struct Node *searchedNode = searchForANode(node, value);

    // case 1: node with no children
    if (searchedNode->leftChild == NULL && searchedNode->rightChild == NULL) {
        free(searchedNode);
        return node;
    }

    // case 2: node with a single child
    if (searchedNode->rightChild == NULL) {
        struct Node *refNode = searchedNode->leftChild;
        free(searchedNode);
        return refNode;
    } else if (searchedNode->leftChild == NULL) {
        struct Node *refNode = searchedNode->rightChild;
        free(searchedNode);
        return refNode;
    }
    return node;
}

int main() {
    struct Node *rootNode = NULL;
    printf("before deleting:");
    rootNode=insertDataInBST(rootNode);
    inOrder(rootNode);
    printf("\nafter deleting:");
    deleteANode(rootNode,6);
    inOrder(rootNode);
    return 0;
}

当前输出（含Segmentation fault）：

before deleting:1 3 6 7 8 10 14 
after deleting:1 3 
Segmentation fault (core dumped)

期望输出：

before deleting:1 3 6 7 8 10 14 
after deleting:1 3 7 8 10 14

问题根源及修复方案

1. 未正确更新父节点的指针

原deleteANode函数直接找到目标节点并释放，但没有修改父节点中指向该节点的指针。比如删除节点6时，节点3的rightChild仍然指向已被释放的6的内存地址，后续遍历访问该地址时触发段错误。

正确的做法是递归遍历树，在找到目标节点时，返回子节点来更新父节点的对应指针，而不是直接操作搜索到的节点。

2. 冗余的节点查找与错误的边界判断

原代码中doesThisNodeExist和searchForANode重复遍历树，且deleteANode开头的判断逻辑错误：若节点存在但不是根节点，直接返回原节点，未处理中间节点的递归更新。

3. 未接收删除后的根节点指针

main函数中调用deleteANode后，没有将返回的更新后根节点赋值给rootNode，若删除的是根节点会直接丢失树的引用，同时也无法更新父节点的指针。

修改后的完整代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node {
    int i;
    struct Node *leftChild;
    struct Node *rightChild;
};

struct Node *insertANodeInBST(struct Node *node, int currentValue) {
    if (node == NULL) {
        node = (struct Node *) malloc(sizeof(struct Node));
        node->i = currentValue;
        node->leftChild = NULL;
        node->rightChild = NULL;
        return node;
    }

    if (currentValue == node->i) {
        return node;
    }
    if (currentValue < node->i) {
        node->leftChild = insertANodeInBST(node->leftChild, currentValue);
    } else if (currentValue > node->i) {
        node->rightChild = insertANodeInBST(node->rightChild, currentValue);
    }
    return node;
}

struct Node *insertDataInBST(struct Node *node) {
    node = insertANodeInBST(node, 8);
    node = insertANodeInBST(node, 3);
    node = insertANodeInBST(node, 1);
    node = insertANodeInBST(node, 6);
    node = insertANodeInBST(node, 10);
    node = insertANodeInBST(node, 14);
    node = insertANodeInBST(node, 7);
    return node;
}

void inOrder(struct Node *node) {
    if (node == NULL) {
        return;
    }
    inOrder(node->leftChild);
    printf("%d ", node->i);
    inOrder(node->rightChild);
}

struct Node *deleteANode(struct Node *node, int value) {
    // 空树直接返回
    if (node == NULL) {
        return NULL;
    }

    // 递归查找目标节点
    if (value < node->i) {
        node->leftChild = deleteANode(node->leftChild, value);
        return node;
    } else if (value > node->i) {
        node->rightChild = deleteANode(node->rightChild, value);
        return node;
    }

    // 当前节点就是要删除的节点
    // 情况1：无子女
    if (node->leftChild == NULL && node->rightChild == NULL) {
        free(node);
        return NULL;
    }
    // 情况2：只有右子女
    else if (node->leftChild == NULL) {
        struct Node *temp = node->rightChild;
        free(node);
        return temp;
    }
    // 情况3：只有左子女
    else if (node->rightChild == NULL) {
        struct Node *temp = node->leftChild;
        free(node);
        return temp;
    }
    // 情况4：有两个子女（可选实现，这里先保留框架）
    else {
        // 可以找右子树最小节点或左子树最大节点替换，此处暂不实现
        return node;
    }
}

int main() {
    struct Node *rootNode = NULL;
    printf("before deleting:");
    rootNode = insertDataInBST(rootNode);
    inOrder(rootNode);
    printf("\nafter deleting:");
    // 接收更新后的根节点
    rootNode = deleteANode(rootNode, 6);
    inOrder(rootNode);
    printf("\n");
    return 0;
}

修改说明

重构deleteANode为递归逻辑：遍历树时，通过返回值更新父节点的leftChild或rightChild，确保指针指向正确的子节点。
移除冗余的searchForANode和doesThisNodeExist函数，合并到删除逻辑中，减少重复遍历。
main函数接收deleteANode的返回值，更新根节点指针。

运行修改后的代码，即可得到期望输出，且无段错误。

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