C语言中的二叉搜索树：删除节点函数

Question

我正在为二元搜索树组装函数，结果遇到了麻烦。我正在研究当需要从树中删除包含指定值的节点时可能遇到的每种情况。如果节点没有左右子节点，我不确定如何处理释放节点。函数必须返回节点。我是否备份、检查每个左、右子级，并在子级中删除该值？但是如果该值在根中，我是否会遇到类似的问题，即如何删除它？作为解释，程序使用一个void指针，然后在一个单独的函数compare（）中强制转换类型val，该函数计算两个值并为返回-1

struct Node *_removeNode(struct Node *cur, TYPE val)
{
    if (compare(cur->val, val) == 0) { //if val == cur->val
        if (cur->right != NULL && cur->left != NULL) { //if cur has right and left
            cur = _leftMost(cur->right);
            free(_leftMost(cur->right));
        }
        else if (cur->right == NULL && cur->left != NULL) {  //if cur has left
            cur = cur->left;
            free(cur->left);
        }
        else if (cur->right != NULL && cur->left == NULL){ //if cur has right
            cur = cur->right;
            free(cur->right);
        }
        else if (cur->right == NULL && cur->left == NULL){ //if cur has no child
                //free cur if cur = val

        }
    }
    else if (compare(cur->val, val) == -1) {
        cur->right = _removeNode(cur->right, val);
    }
    else if (compare(cur->val, val) == 1) {
        cur->left = _removeNode(cur->left, val);
    }

    return cur;
}

Answer 1

如果节点没有子节点，则可以简单地将其删除。为了使递归在其他情况下工作，应该从\u removeNode返回NULL。在所有情况下，cur都应该被删除（释放），因为它不再需要。在每种情况下，都需要返回替换子树。并发症发生在第一种情况下，即右侧儿童的最左侧后代被拉起。拉起后，需要将其从右子树中删除（请注意，它可能是右子树）。

我在脑海中写下了以下所有内容，所以要为一些错误/一点调试做好准备。此外，_leftMost和_removeLeftMost可以与一些工作合并。

所讨论的块应该是这样的：

    Node *replacement;
    if (cur->right != NULL && cur->left != NULL) { //if cur has right and left    
        replacement = _leftMost(cur->right);
        replacement->right = _removeLeftMost(cur->right,replacement);
        replacement->left = cur->left;
    }
    else if (cur->right == NULL && cur->left != NULL) {  //if cur has left
        replacement = cur->left;
    }
    else if (cur->right != NULL && cur->left == NULL){ //if cur has right
        replacement = cur->right;
    }
    else if (cur->right == NULL && cur->left == NULL){ //if cur has no child
        replacement = NULL;
    }
    free(cur);
    cur = replacement;

函数\u removeLeftMost向下遍历左子指针，直到看到要替换的节点，然后用该节点的右子节点替换它。类似于：

Node *_removeLeftMost(node, remove) {
    if (node == remove) {
       return node->right; // Note that remove->left should be null
    }
    else {
       node->left = _removeLeftMost(node->left,remove);
       return node;
    }
}

另外，主要的电话是这样的

root = _removeNode(root, val);

这样，当节点是根节点时，就可以处理您的问题。