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

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) 和 deleteNode(50, 20))发生了什么，在执行结束时返回根。实际上返回了哪些根？

Answer 1

要回答“实际上返回了哪些根”……它们都是。问题是它们返回到哪里，最终值是多少。

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

从您离开的地方开始，您返回值为 NULL 的 temp 到 root->left = deletenode(20, 20) 的函数调用，正如您意识到的那样.您现在从该点恢复执行。 else if 和 else 条件没有神奇地重新求值，你回到 return root 其左节点被设置为 NULL。然后将此根返回到 deletenode(30,20)，然后用返回值替换左侧或右侧部分。

这种模式一直持续到所有函数调用都已解决。名称 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)

尝试为您追踪:

• deleteNode( "节点 50", 20 )
• 如果 (root == NULL) 为假，则跳过语句(我们称 root 为“节点 50”)
• 如果 ( 20 < 50 ) 为真那么执行 "node 50"->left = deleteNode( "node 50"->left, 20 )
  • 如果 ( root == NULL ) 为假，则跳过语句(这里的 root 现在是“node 50”->left，或“node 30”)
  • 如果 ( 20 < 30 ) 为真，那么执行 "node 30"->left = deleteNode( "node 30"->left, 20)
    • if (root == NULL) 为假，跳过语句(root is "node 20")
    • 如果 ( 20 < 20 ) 为假，跳过 block
    • else if ( 20 > 20 ) 为假，跳过 block
    • 其他 block :
      • if ( "node 20"->left == NULL ) 为真
      • 用“node 20”的右 child 创建一个临时节点(恰好为NULL)
      • 删除“节点20”
      • 返回临时节点的地址
  • 将返回值(NULL)赋值给“node 30”->left
  • 控制流绕过if结构的其余部分，执行return "node 30"
• 返回“node 30”，赋值给“node 50”->left
• 控制流绕过if结构的其余部分，执行return "node 50"

跟踪结束。

您返回的树现在看起来像:

         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)