在BST中删除节点

林波仙

以下代码是该网站

我在这里的部分代码有一些问题。我对此行有疑问:

root->left = deleteNode(root->left, key);

为什么我不能deleteNode(root->left, key);在这里简单地使用我想问一下root->left这行的功能

/* Given a binary search tree and a key, this function deletes the key
   and returns the new root */
struct node* deleteNode(struct node* root, int key)
{
    // base case
    if (root == NULL) return root;

    // If the key to be deleted is smaller than the root's key,
    // then it lies in left subtree
    if (key < root->key)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted is greater than the root's key,
    // then it lies in right subtree
    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    // if key is same as root's key, then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest
        // in the right subtree)
        struct node* temp = minValueNode(root->right);

        // Copy the inorder successor's content to this node
        root->key = temp->key;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}
莎妮·克莱因

首先,您需要注意到该函数不是无效的,因此您不能简单地使用deleteNode(root->left, key)

如果我不太正确,您想知道返回的值是什么以及为什么将其放在左侧(或右侧)节点中。

如果您未到达要删除的节点,root->left = deleteNode(root->left, key);则类似于使用`deleteNode(root-> left,key),即-向左走。

找到要删除的节点后,有几种选择:1.如果到达的节点只有一个孩子或没有孩子,则将节点值更新为该孩子。因此,通过键入root->left = deleteNode(root->left, key);您可以更新此值。

  1. 如果有两个儿子,您会发现有序的后继者(并且是叶子),并且在这些值之间“交换”,然后删除叶子。因此现在root->left = deleteNode(root->left, key);意味着您将值更新为后继节点并删除该节点。

希望对您有所帮助。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章