以非遞歸方式刪除BST中的節點

Question

以下是我從BST中刪除節點的一​​段代碼。它是一個非遞歸的代碼。 我已經應用了所有可能的條件。 但是，當我運行我的代碼時，它停止，因爲如果卡在無限循環某處或結束在我的指針指向NULL的點。但我無法識別它。

任何幫助，將不勝感激。

template <class T> 
void bst<T>::delete_node(T key1) 
bst_node<T>* delNode = search(key1); //delNode is the node I wish to delete 

if(delNode!=root) 
{ 
    if((delNode->left == NULL) && (delNode->right == NULL)) // node to be deleted has no children 
    { 
     delNode = NULL; 
    } 

else if((delNode->left!=NULL) && (delNode->right == NULL)) //node to be deleted has exactly one child 
    { 
     if(delNode->parent->left == delNode) 
     { 
      delNode->parent->left = delNode->left; 
      delNode = NULL; 
     } 
     else if(delNode->parent->right == delNode) 
     { 
      delNode->parent->right = delNode->left; 
      delNode = NULL; 
     } 
    } 
    else if((delNode->right!= NULL) && (delNode->left == NULL)) 
    { 
     if(delNode->parent->left == delNode) 
     { 
      delNode->parent->left = delNode->right; 
      delNode = NULL; 
     } 
     else if(delNode->parent->right == delNode) 
     { 
      delNode->parent->right = delNode->right; 
      delNode = NULL; 
     } 
    } 
    else if((delNode->right!=NULL)&&(delNode->left != NULL)) //if has two children 
    { 
     bst_node<T>* temp = delNode; 
     bst_node<T>* trav = delNode->right; 
     if((trav->right == NULL)&&(trav->left == NULL)) 
     { 
      delNode->value = trav->value; 
      delNode->key = trav->key; 
      trav = NULL; 
     } 
     else 
     { 
      bst_node<T>* pred = trav; 
      while(trav!=NULL) 
      { 
       pred = trav; //smallest node in right subtree 
       trav=trav->left; 
      } 
      delNode->value = pred->value; 
      delNode->key = pred->key; 
      pred = NULL; 
     } 

    } 
} 
    else if(delNode==root)//node to be deleted is Root 
    { 
     if((delNode->left==NULL)&&(delNode->right==NULL)) 
      root = NULL; 
     else if((delNode->left!=NULL) && (delNode->right == NULL)) //root has exactly one child 
     { 
      root = delNode->left; 
      delNode = NULL; 

     } 
     else if((delNode->right!= NULL) && (delNode->left == NULL)) 
     { 
      root = delNode->right; 
      delNode = NULL; 
     } 
     else if((delNode->right!=NULL)&&(delNode->left!=NULL)) { 
     bst_node<T>* temp = delNode; 
     bst_node<T>* trav = delNode->right; 
     if((trav->right == NULL)&&(trav->left == NULL)) 
     { 
      delNode->value = trav->value; 
      delNode->key = trav->key; 
      trav = NULL; 
     } 
     else 
     { 
      bst_node<T>* pred = trav; 
      while(trav!=NULL) 
      { 
       pred = trav; //smallest node in right subtree 
       trav=trav->left; 
      } 
      delNode->value = pred->value; 
      delNode->key = pred->key; 
      pred = NULL; 
     } 

    } 
} 

} 

Answer 1

在部分：

else if((delNode->right!=NULL)&&(delNode->left != NULL)) //if has two children 

時如果不採取：

if((trav->right == NULL)&&(trav->left == NULL)) 

代碼副本從trav到delNode的值，並設置trav到NULL：

delNode->value = trav->value; 
delNode->key = trav->key; 
trav = NULL; 

，但沒有設置delNode->right到NULL，因爲它應該是因爲trav沒有任何孩子。

非常接下來的else查找最左邊節點的語句提交一個類似的錯誤，因爲父節點的成員left未設置爲NULL。

由於表面複製粘貼（咳嗽！）代碼，處理僅刪除root節點的代碼的下一個大部分似乎具有相同的問題。