1

我正在将二叉搜索树的函数放在一起，然后撞到了墙上。我正在处理需要从树中删除持有指定值的节点时可能遇到的每种情况。如果节点没有左右子节点，我不确定如何处理释放节点。该函数必须返回一个节点。我是否备份，检查每个左右孩子，并在孩子的时候删除价值？但是，如果该值在根目录中，我不会在如何删除它方面遇到类似的问题吗？只是作为解释，程序使用 void 指针，然后将 TYPE val 转换为单独的函数 compare()，该函数计算两个值并返回 -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;
}
4

1 回答 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);

因此，当节点是根时，这可以解决您的问题。

于 2013-02-19T19:19:17.080 回答