从二叉搜索树中使用递归删除节点会在 c 中引发分段错误

Question

我正在尝试从具有一个子节点的二叉搜索树中删除一个节点。我想使用递归删除节点。但是，它确实打印了数据，但在删除的下一个值存在的值处抛出

Segmentation fault

错误。我已经浏览了几乎所有的博客和 Stack Overflow 问题，但仍然没有解决我的问题。

• 这就是我的代码的样子：

#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("after deleting:");
    deleteANode(rootNode,6);
    inOrder(rootNode);
    return 0;
}

输出看起来像（有分段错误）：

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

但它应该看起来像：

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

我该如何解决这个问题？

谢谢你。

Answer 1

从二叉搜索树中删除递归节点会在 c 中引发分段错误

但是你不递归地删除节点。你有一些递归辅助函数，但是你的

deleteANode()

不直接或间接地调用自身。

这不一定是问题，但它是您的特定代码的问题。主要问题是父节点指向已删除节点的指针永远不会更新。这是一项由

deleteANode()

的现有行为（返回指向已删除节点的子节点之一的指针）支持的任务，因为在递归版本中，调用者可以使用返回值来更新其子指针。但事实上，该返回值被忽略。

main()

。