BST 节点删除函数在递归调用时失败

Question

void search(struct node **root, struct node **cursor,
            struct node **parent, int data, int *found) {
    struct node *iterator = *root;

    *cursor = NULL, *parent = NULL;
    *found = FALSE;

    while (iterator != NULL) {
        if (data == iterator->data) {
            *found = TRUE;
            *cursor = iterator;
            break;
        } else
        if (data <= iterator->data) {
            *parent = iterator;
            iterator = iterator->left;
        } else {
            *parent = iterator;
            iterator = iterator->right;
        }
    }
}

void delete(struct node **root, int data) {
    int found;
    struct node *cursor, *parent;

    if (*root == NULL) {
        printf("ERROR! Binary Search Tree Empty!\n");
        exit(0);
    }
    search(root, &cursor, &parent, data, &found);
    if (found == FALSE) {
        printf("ERROR! Element not found in Binary Tree!\n");
        exit(0);
    }
    //  If the Node has No Children
    if (cursor->left == NULL && cursor->right == NULL) {
        if (parent->left == cursor) {
            parent->left = NULL;
        } else {
            parent->right = NULL;
        }
        free(cursor);
    }
    if (cursor->left == NULL && cursor->right != NULL) {
        if (parent->left == cursor) {
            parent->left = cursor->right;
        } else {
            parent->right = cursor->right;
        }
        free(cursor);
    }
    if (cursor->left != NULL && cursor->right == NULL) {
        if (parent->left == cursor) {
            parent->left = cursor->left;
        } else {
            parent->right = cursor->left;
        }
        free(cursor);
    }
    // If node has two children
    if (cursor->left != NULL && cursor->right != NULL) {
        struct node *iterator = cursor;
        iterator = iterator->right;
        while (iterator->left != NULL) {
            iterator = iterator->left;
        }
        cursor->data = iterator->data;
        printf("\n%i\n", iterator->data);
        delete(&iterator, iterator->data);
    }
}

我正在尝试实现二进制搜索树删除功能。我已经测试了很多 BST，但是当我删除一个有两个 children 的节点时它失败了。它在 recursive 调用时失败。它给出了 分段错误 11。我该怎么办？

Answer 1

您的 delete 函数的问题是您没有在每个 free(cursor); 之后 return。相反，您继续测试下一个案例，取消引用刚刚释放的 cursor。问题主要是当 cursor 有 1 或没有 children.

BST 节点删除函数在递归调用时失败

BST node delete function failing at recursive call

c

algorithm

binary-tree

binary-search-tree

data-structures