二進制搜索樹刪除（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);