二进制搜索树删除（Inorder Pred方法）C++

Question

好吧，所以我认为它是固定的，但我得到完全不一致的结果。 我重写了它从头开始新鲜开始，这里是我的结果。我没有错误，没有崩溃，它只是不删除它们。它只是彻底弄乱了树，给了我更多的叶子，并把所有东西混合起来。不知道还有什么地方去

template <class T> 
void BST<T>::remove(struct Node<T>*& root, const T& x) 
{ 
    Node<T>* ptr = root; 
    bool found = false; 
    Node<T>* parent; 


    while (ptr != NULL && !found) 
    { 
     if (x < ptr->data) 
     { 
      parent = ptr; 
      ptr = ptr->left; 
     } 
     else if (x > ptr->data) 
     { 
      parent = ptr; 
      ptr = ptr->right; 
     } 
     else 
      found = true; 
    } 

    if (found == false) 
     return; 
    else 
    { 
     if(ptr->left != NULL && ptr->right != NULL) 
     { 
      Node<T>* inOrderPtr = ptr->left; 
      parent = ptr; 
      while (inOrderPtr->right != NULL) 
      { 
       parent = inOrderPtr; 
       inOrderPtr = inOrderPtr->right; 
      } 

      ptr->data = inOrderPtr->data; 
      ptr = inOrderPtr; 
     } 
    Node<T>* subPtr = ptr->left; 
    if (subPtr == NULL) 
     subPtr = ptr->right; 

    else if (parent->left == ptr) 
     parent->left = subPtr; 

    else 
     parent->right = subPtr; 

    delete ptr; 
    } 

Answer 1

是否每个T在树中唯一发现的？看起来他们是从你的代码...

看起来这应该工作：

在其他情况下，删除根节点：

Node<T> *tmp_r = root->left; 
Node<T> *parent = root; 
while (tmp_r->right != NULL) 
{ 
    parent = tmp_r; 
    tmp_r = tmp_r->right; 
} 
Node<T> *tmp_l = tmp_r; 
while (tmp_l->left != NULL) 
    tmp_l = tmp_l->left; 

tmp_l->left = root->left; 
tmp_r->right = root->right; 
parent->right = NULL; 

parent = root; 
root = tmp_r; 
delete parent; 

Answer 2

你不应该在递归第三种情况下调用remove()（在您的“不知道这是正确的”的评论是）。在要删除的节点有两个孩子的情况下，您想要做的是找到左侧孩子的最右侧孩子（正如您所做的;所得节点存储在parent中）。此节点没有正确的子节点 - 使其正确的子节点是要删除的节点的正确子节点。然后，只需将root变量更改为其左边的孩子;无需在任何节点中更改data成员或者递归调用remove。

在图片：

 
Before: 
     r <- root points here 
    /\ 
    / \ 
    a  b 
    /\ /\ 
    x c y y 
    /\ 
    x d 
     /
     x 

After: 
     a <-- root points here 
    /\ 
    x c 
    /\ 
     x d 
     /\ 
     x b 
     /\ 
      y y 

Answer 3

究竟发生了什么是可能的搜索被颠倒过来，所以它实际上只是继续向右走，但数据并没有真正匹配，所以它会撞上墙。

if (root->data < x) 
     remove(root->left, x); 
    else 
     remove(root->right, x); 

应该已经

if(x < root->data) 
remove(root->left, x); 
else 
remove(root->right, x);