首页 文章

C中的二进制搜索树：删除节点功能

提问于
浏览 次
1

我正在为二元搜索树组合函数并遇到一堵墙 . 我正在处理需要从树中删除保存指定值的节点时可能遇到的每种情况 . 我不确定如果它没有左右孩子，如何处理释放节点 . 该函数必须返回一个节点 . 我是否会备份，检查每个左右孩子，并在孩子身上移除该值？但是，如果值在根目录中，我是否会遇到与删除它类似的问题？仅作为解释，程序使用void指针然后在单独的函数compare（）中强制转换TYPE值，该函数计算两个值并返回-1表示<，0表示==，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;
}
c data-structures binary-search-tree

1 回答

  • 2

    如果节点既没有子节点，则可以简单地删除它 . 为了使其他情况下的递归起作用，您应该从_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;

    函数_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);

    因此，当节点是根时，处理您的问题 .

    回复于

相关问题