二叉搜索树递归删除

当我试图找到我的删除功能的最大值时，我的程序不断破坏。我想要做的是用最大的左树覆盖用户想要删除的内容，然后删除该节点。一旦到达第一个Else，它就会一直断裂。递归正在打破我的想法。我的缺点在哪里？二叉搜索树递归删除

这是带有其私有递归兄弟的remove函数。

template<typename TYPE> 
bool BinarySearchTree<TYPE>::remove(TYPE& data) 
{ 
    bool found = search(dataOut); 
    if(found) 
     TRoot = Premove(TRoot, data); 
    return found; 
} 

template<typename TYPE> 
Node<TYPE>* BinarySearchTree<TYPE>::Premove(Node<TYPE>* root, TYPE& data) 
{ 
    Node<TYPE>* del; 
    Node<TYPE>* max; 
    if(root) 
    { 
     if(root->data > data) 
      root->left = Premove(root->left, data); 
     else if(root->data < data) 
      root->right = Premove(root->right, data); 
     else 
     { 
      if(root->left && root->right) 
      { 
       max = root->left; 
       while(max->data < max->right->data) 
        max = max->right; 
       root->data = max->data; 
       max = Premove(root, max->data); 

      } 
      else 
      { 
       del = root; 
       root = (root->right) ? root->right : root->left; 
       delete pDel; 
      } 
     } 
    } 
    return root; 
}

来源

2013-04-14 Derp

你能描述一下“破”的含义吗？（关于代码，而不是你的想法） –

好吧，它似乎很好地通过了一段时间，但当我试图删除'max'它只是进入一个无限循环。 – Derp

问题是最有可能在这里： while(max->data < max->right->data) max = max->right;

您正在运行从树上（max->right将成为最终NULL）。其实，因为它是二叉搜索树，所以不需要比较data。只要在可能的情况下向右走即可：while (max->right) max=max->right;

另请注意此分支中的最后一项分配：还有两个问题。首先，而不是max = Premove(...)你应该做root->left = Premove(...)（否则你不会修改根 - >左引用）。其次，您应该拨打Premove获得root->left而不是root：root->left = Premove(root->left, max->data);（否则您只能获得无限递归）。

来源

2013-04-14 20:20:19 Inspired

我觉得你的while语句应该是这样的：

while(max && max->right && max->data < max->right->data)

在某些情况下，在你的代码，max或max->right可能是NULL，并导致RUN_TIME错误。

来源

2013-04-14 20:22:31

二叉搜索树递归删除

回答

相关问题