c - 递归如何用于二叉搜索树算法

Question

我有以下二叉搜索树，根节点为 20。我要回答的问题是，如果我们应用函数 t = deleteRoot(t)，其值将是多少新根节点及其直接左子节点和右子节点(例如，当前根节点为 20，直接左子节点为 11，直接右子节点为 32)。在过去的 2 个小时里，我写了至少 10 页试图解决这个问题，但递归快要了我的命。有人可以帮我想象一下这一点吗——即某种允许我处理递归的思维方式。我不太擅长想象递归是如何工作的，但我可以在某种程度上实现它。非常感谢。顺便说一句，答案是根节点:21，左子节点为 11，右子节点为 32。

我的尝试:

问题告诉我们从t=deleteRoot(t)开始。

parent = node containing 25 
succ = node containing 21
succval = 21

然后我们就到了

t = TreeDelete(t, succval)

然后我对 TreeDelete 函数的工作原理有点迷惑

t->left = TreeDelete(t->left, key) ...etc

<小时/>

deleteRoot(Tree t)函数

// delete root of tree
Tree deleteRoot(Tree t)
{
    Link newRoot;
    // if no subtrees, tree empty after delete
    if (t->left == NULL && t->right == NULL) {
        free(t);
        return NULL;
    }
    // if only right subtree, make it the new root
    else if (t->left == NULL && t->right != NULL) {
        newRoot = t->right;
        free(t);
        return newRoot;
    }
    // if only left subtree, make it the new root
    else if (t->left != NULL && t->right == NULL) {
        newRoot = t->left;
        free(t);
        return newRoot;
    }
    // else (t->left != NULL && t->right != NULL)
    // so has two subtrees
    // - find inorder successor (grab value)
    // - delete inorder successor node
    // - move its value to root
    Link parent = t;
    Link succ = t->right; // not null!
    while (succ->left != NULL) {
        parent = succ;
        succ = succ->left;
    }
    int succVal = succ->value;
    t = TreeDelete(t,succVal);
    t->value = succVal;
    return t;
}

树TreeDelete(Tree t, Key k)函数:

Tree TreeDelete(Tree t, Key k)
{
    Tree deleteRoot(Tree);

    if (t == NULL)
        return NULL;
    int diff = cmp(k,key(t->value));
    if (diff == 0)
        t = deleteRoot(t);
    else if (diff < 0)
        t->left = TreeDelete(t->left, k);
    else if (diff > 0)
        t->right = TreeDelete(t->right, k);
    return t;
}

Answer 1

By the way, the answer is root node: 21 with left child 11 and right child 32.

嗯，这是一个解决方案，但不是唯一的解决方案。

18 左 child 11 右 child 32 也将是一个解决方案。

删除根时，可以选择新的根为

1. 左子树中最大的数字

或

右子树中最小的数字

因此将所选节点的值复制到当前根。然后删除选中的节点。如果所选节点有子节点，则可以递归地重复该过程。