Удаление узла в 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, похоже, имеет идентичные проблемы из-за очевидного кода с копированием (кашля!).