这个二叉搜索树算法如何递归

问题描述：

我有以下的二叉搜索树，根节点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（树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（树T，密钥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; 
}

我们先从'T = deleteRoot（吨）'其中't'是初始根节点（20）按照图。其余的从那里开始。 – Programmer

当子树被删除时，父节点会发生什么？不会被设置为空吗？ – Arash

@ 4386427：因为2 * 21 = 42？ ;-) – alk

答

顺便说一句，答案是根节点：21左子11和右子32

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

18与左孩子11和右孩子32也将是一个解决方案。

当删除根，新的根可以被选择作为

在左子树的最高数

或

的在右子树中的最低数量

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

开始=>

答

在缺失的情况下，如果要删除的节点有两个孩子：

找到继任者或前任
替换为接班人的内容节点/前身
呼叫删除后继/前身（这样的尺寸将递减）
返回节点

后继是右侧子树上的最高元素，而前一个元素是左侧子树上的最低元素。在你的情况下，后继将是21和前身是18.

这个二叉搜索树算法如何递归

相关推荐