了解从二叉搜索树中删除节点的递归调用

Question

使用给定键删除BST中节点的函数如下：

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;
}

考虑前序遍历的树为：50 30 20 40 70 60 80

我想删除节点20，函数调用如下：

deleteNode(root=50, 20) 
deleteNode(root=30, 20)
deleteNode(root=20, 20)

当到达这个调用(deleteNode(20, 20))时，执行else部分。由于root->left == NULL，截取的代码执行为：

temp = root->right (which is NULL)
free (root)
return temp (returning NULL)

返回上次调用root->left = deleteNode(20, 20) = NULL。其他调用（即 deleteNode(30, 20) and deleteNode(50, 20)）会发生什么，在执行结束时返回根。实际上返回了哪些根？

Answer 1

回答"which of the roots is actually returned" ...他们都是。问题是它们 return 到哪里去了，最终值是多少。

当您向前追踪代码时，您看到了递归函数调用的执行位置，并了解到您创建了具有不同值的函数的新副本，然后再次从顶部追踪。您现在正在取消该过程。

从您停止的地方开始，您 return temp 的值是 NULL 到 root->left = deletenode(20, 20) 的函数调用，正如您所意识到的。您现在从该点恢复执行。 else if 和 else 条件不是神奇的 re-evaluated，你下降到 return root 其左节点被设置为 NULL。然后将此根 returned 为 deletenode(30,20)，然后将左侧或右侧部分替换为 returned 值。

此模式一直持续到所有函数调用都已解决。名称 root 可能令人困惑，但它是递归期间创建的每个 sub-tree 的 "root"，它只形成原始树的分支。

为了提供一些说明，请使用您的值：

       50             <- root for deletenode("node 50", x)
     /    \
   30      70         <- root for deletenode("node 50"-> left or right, x)
  /  \    /  \
20   40 60    80      <- root for deletenote("node 50"->left/right->left/right,x)

为您尝试追踪：

删除节点( "node 50", 20 )
if (root == NULL) 为假，跳过语句（让我们调用root "node 50"）
if ( 20 < 50 ) 为真所以执行 "node 50"->left = deleteNode( "node 50"->left, 20 )
- if ( root == NULL ) 为假，跳过语句（此处的 root 现在 "node 50"->left，或 "node 30"）
- if ( 20 < 30 ) 为真所以执行 "node 30"->left = deleteNode( "node 30"->left, 20)
  - if (root == NULL) 为假，跳过语句（root is "node 20"）
  - 如果 ( 20 < 20 ) 为假，跳过块
  - 否则，如果 ( 20 > 20 ) 为假，则跳过块
  - 其他块：
    - 如果（"node 20"->left == NULL）为真
    - 用"node 20"的右边child创建临时节点（恰好为NULL）
    - 删除"node 20"
    - return临时节点的地址
- 将 returned 值 (NULL) 分配给 "node 30"->left
- 控制流绕过if结构的其余部分，执行return "node 30"
"node 30" 被 returned，赋值给 "node 50"->left
控制流绕过if结构的其余部分，执行return "node 50"

跟踪结束。

您的 returned 树现在看起来像：

         50             <- root for deletenode("node 50", x)
       /    \
     30      70         <- root for deletenode("node 50"-> left or right, x)
    /  \    /  \
NULL    40 60    80      <- root for deletenote("node 50"->left/right->left/right,x)

Answer 2

我认为 "trick" 理解递归函数首先要理解非递归函数，然后认识到递归函数的工作方式完全相同。

假设树的每一层都有一个函数 - deleteNode_1、deleteNode_2、deleteNode_3，等等。

您可以通过将树的根传递给 deleteNode_1 来进行第一次调用。

如果要删除的节点在其参数的子树中，deleteNode_1 使用该子树调用 deleteNode_2 并用结果替换其参数的子树之一。

对deleteNode_2的调用可能会调用deleteNode_3，依此类推，但是deleteNode_1不需要关心这些，它只关心从中获取合适的子树deleteNode_2.

它们看起来像这样：

// Delete a node when 'current' is at level 1
struct node* deleteNode_1(struct node* current, int key);
// Delete a node when 'current' is at level 2
struct node* deleteNode_2(struct node* current, int key);
// Delete a node when 'current' is at level 3
struct node* deleteNode_3(struct node* current, int key);

// .. and so on, as many as you need.

并像这样实现：

struct node* deleteNode_1(struct node* current, int key)
{
    if (current == NULL) return current;
    if (key < current->key)
        current->left = deleteNode_2(current->left, key);
    else if (key > current->key)
        current->right = deleteNode_2(current->right, key);
    else
    {
        if (current->left == NULL)
        {
            struct node *temp = current->right;
            free(current);
            return temp;
        }
        else if (current->right == NULL)
        {
            struct node *temp = current->left;
            free(current);
            return temp;
        }

        struct node* temp = minValueNode(current->right);
        current->key = temp->key;
        current->right = deleteNode_2(current->right, temp->key);
    }
    return current;
}


struct node* deleteNode_2(struct node* current, int key)
{
    if (current == NULL) return current;
    if (key < current->key)
        current->left = deleteNode_3(current->left, key);
    else if (key > current->key)
        current->right = deleteNode_3(current->right, key);
    else
    {
        if (current->left == NULL)
        {
            struct node *temp = current->right;
            free(current);
            return temp;
        }
        else if (current->right == NULL)
        {
            struct node *temp = current->left;
            free(current);
            return temp;
        }

        struct node* temp = minValueNode(current->right);
        current->key = temp->key;
        current->right = deleteNode_3(current->right, temp->key);
    }
    return current;
}

// ...

如果您了解这些函数的工作原理，那么理解递归函数的步骤就非常小了。

了解从二叉搜索树中删除节点的递归调用

Understanding recursive calls in deleting a node from a Binary Search Tree

c

recursion

binary-search-tree