Двоичное дерево поиска Рекурсивное удаление

Question

Моя программа продолжает ломаться, когда я пытаюсь найти максимум моей функции удаления. То, что я пытаюсь сделать, это перезаписать то, что пользователь хочет удалить с максимальным левым деревом, а затем удалить этот узел. Он продолжает ломаться, когда достигает первого. Рекурсия разрушает мой разум. Где мой недостаток?

Это функция удаления со своим частным рекурсивным родным братом.

template<typename TYPE> 
bool BinarySearchTree<TYPE>::remove(TYPE& data) 
{ 
    bool found = search(dataOut); 
    if(found) 
     TRoot = Premove(TRoot, data); 
    return found; 
} 

template<typename TYPE> 
Node<TYPE>* BinarySearchTree<TYPE>::Premove(Node<TYPE>* root, TYPE& data) 
{ 
    Node<TYPE>* del; 
    Node<TYPE>* max; 
    if(root) 
    { 
     if(root->data > data) 
      root->left = Premove(root->left, data); 
     else if(root->data < data) 
      root->right = Premove(root->right, data); 
     else 
     { 
      if(root->left && root->right) 
      { 
       max = root->left; 
       while(max->data < max->right->data) 
        max = max->right; 
       root->data = max->data; 
       max = Premove(root, max->data); 

      } 
      else 
      { 
       del = root; 
       root = (root->right) ? root->right : root->left; 
       delete pDel; 
      } 
     } 
    } 
    return root; 
} 

Answer 1

Проблема, скорее всего, здесь: while(max->data < max->right->data) max = max->right;

Вы работаете из дерева (max->right будет NULL в конце концов). На самом деле, поскольку это двоичное дерево поиска, нет необходимости сравнивать data. Достаточно просто повернуть направо, пока это возможно: while (max->right) max=max->right;

Также обратите внимание на последнее задание в этой ветке: есть еще две проблемы. Прежде всего, вместо max = Premove(...) вы должны сделать root->left = Premove(...) (иначе вы не будете изменять ссылку root-> left). Во-вторых, вы должны позвонить Premove за root->left, а не за root: root->left = Premove(root->left, max->data); (иначе вы просто получите бесконечную рекурсию).

Answer 2

Я думаю, что ваше время заявление должно быть так:

while(max && max->right && max->data < max->right->data) 

В некоторых случаях в вашем коде, max или max->right может быть NULL и вызвать run_time ошибку.