Проблема с удалением двоичного дерева не рекурсивно

Question

Alex Allain's Jumping Into C++ присвоил мне недопустимую задачу по дереву двоичного дерева поиска не рекурсивно (глава 17). Я придумал способ упростить эту задачу, изменив определение моей структуры, чтобы он включал указатель на узел parent, а не на указатели слева и справа. Я стараюсь избегать использования структуры данных стека/связанного списка.

Мой алгоритм для выполнения этого:

1. Проверка L и R указатели текущего узла являются как NULL
2. Если так удалить этот узел и перейти к родительскому узлу.
3. Если нет, перейдите к узлам L и R до тех пор, пока не будет достигнут шаг 1 (слева идет первым, если оба указателя L/R заняты)
4. Мой алгоритм завершается, когда мы нанесли родительский узел NULL (корневой узел parent имеет значение NULL)

Проблема в том, что я застреваю в бесконечном цикле. Я сомневаюсь, что моя функция insert() неисправна, но я могу ошибаться.

Следующий код включает в себя все функции/структуру, упомянутые до сих пор:

struct node 
{ 
    int key_value; 
    node *p_left; 
    node *p_right; 
    node *parent; 
}; 

node* insert (node *p_tree, int key, node* parent) 
{ 
    if (p_tree == NULL) 
    { 
     node* p_new_tree = new node; 
     p_new_tree->p_left = NULL; 
     p_new_tree->p_right = NULL; 
     p_new_tree->key_value = key; 
     p_new_tree->parent = parent; 
     return p_new_tree; 
    } 

    else if(key < p_tree->key_value) 
     p_tree->p_left = insert(p_tree->p_left, key, p_tree); 

    else 
     p_tree->p_right = insert(p_tree->p_right, key, p_tree); 

    return p_tree; 
} 

void destroy_tree_Iteratively(node* p_tree) 
{ 
    int nodesDestroyed = 0; //checking to see if I delete the right amount 

    while (p_tree != NULL) 
    { 
     if (p_tree->p_left == NULL && p_tree->p_right == NULL) 
     { 
      node* placeHolder = p_tree->parent; 
      delete p_tree; 
      p_tree = placeHolder; 
     } 
     else if (p_tree->p_left != NULL) 
      p_tree = p_tree->p_left; 
     else if (p_tree->p_right != NULL) 
      p_tree = p_tree->p_right; 
    } 

    cout << "You've deleted " << nodesDestroyed << " nodes!" << endl; 
} 

Answer 1

При удалении узла вы должны обнулять свой указатель от родителя, в зависимости от того из левых и правых указателей указуют на него , Если есть родитель. В противном случае первый тест if никогда не будет правдой, и вы просто продолжите движение навсегда.