Удаление узла бинарного дерева - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Бьюсь над задачей битый час, в функцию передаю указатель на узел, который и хотим удалить. И в зависимости от того как удалился возвращаю различные задачи. вот функция , чистый си
Листинг программы 
  1. int del(struct treeNode **tempPtr)
  2. {
  3.     struct treeNode *ptr=NULL,*ptrX=NULL;
  4.  
  5.     if (*tempPtr == NULL)
  6.         return -1;
  7.  
  8.          else if ((*tempPtr)->leftPtr == NULL && (*tempPtr)->rightPtr == NULL){
  9.                 free(*tempPtr);
  10.                 *tempPtr = NULL;
  11.                 tempPtr = NULL;
  12.  
  13.                  return 1;
  14.          }
  15.                 else if ((*tempPtr)->leftPtr != NULL && (*tempPtr)->rightPtr == NULL){
  16.                            ptr = *tempPtr;
  17.                            *tempPtr = ptr->leftPtr;
  18.                            free(ptr);
  19.                            return 2;
  20.  
  21.                 }
  22.                         else if((*tempPtr)->leftPtr == NULL && (*tempPtr)->rightPtr != NULL){
  23.                                    ptr = *tempPtr;
  24.                                    tempPtr=ptr->rightPtr);
  25.                                    free(ptr);
  26.                                    return 3;
  27.                         }
  28.                                    else {
  29.                                          *ptr  = *tempPtr;
  30.                                          ptrX = *tempPtr;
  31.                                          ptr = ptr->leftPtr;
  32.  
  33.                                          while(ptr->rightPtr != NULL)
  34.                                                ptr=ptr->rightPtr;
  35.  
  36.                                          if (ptr->leftPtr == NULL ){
  37.                                             tempPtr = &ptr;
  38.                                             ptrX->rightPtr=(*tempPtr)->rightPtr;
  39.                                             ptr = NULL;
  40.                                          }
  41.                                              else {
  42.                                                     tempPtr  = &ptr;
  43.                                                     ptr      =  ptr->leftPtr ;
  44.                                                     ptr->rightPtr = PtrX->rightPtr;
  45.                                              }
  46.                                          free(ptr);
  47.                                          return 4;
  48.                                    }
  49.  
  50. }

Решение задачи: «Удаление узла бинарного дерева»

textual
Листинг программы 
  1. void BinaryTree::Remove(int value)
  2. {
  3.     Node * pointer = _root;
  4.     Node * parent  = NULL;
  5.  
  6.     while (pointer != NULL && pointer->value != value)
  7.     {
  8.         parent = pointer;
  9.         if (value < pointer->value)
  10.             pointer = pointer->left;
  11.         else
  12.             pointer = pointer->right;
  13.     }
  14.  
  15.     if (pointer != NULL)
  16.     {
  17.         Node * removed = NULL;
  18.  
  19.         if (pointer->left == NULL || pointer->right == NULL)
  20.         {   
  21.             Node * child = NULL;
  22.             removed = pointer;
  23.  
  24.             if (pointer->left != NULL)
  25.                 child = pointer->left;
  26.             else if (pointer->right != NULL)
  27.                 child = pointer->right;
  28.  
  29.             if (parent == NULL)
  30.                 _root = child;
  31.             else
  32.             {
  33.                 if (parent->left == pointer)
  34.                     parent->left = child;
  35.                 else
  36.                     parent->right = child;
  37.             }
  38.         }
  39.         else // (pointer->left != NULL && pointer->right != NULL)
  40.         {
  41.             Node * mostLeft = pointer->right;
  42.             Node * mostLeftParent = pointer;
  43.             
  44.             while (mostLeft->left != NULL)
  45.             {
  46.                 mostLeftParent = mostLeft;
  47.                 mostLeft = mostLeft->left;
  48.             }
  49.  
  50.             pointer->value = mostLeft->value;
  51.             removed = mostLeft;
  52.  
  53.             if (mostLeftParent->left == mostLeft)
  54.                 mostLeftParent->left = NULL;
  55.             else
  56.                 mostLeftParent->right = NULL;
  57.         }
  58.  
  59.         cout << removed << " deleted" << endl;
  60.         delete removed;
  61.     }
  62. }

Объяснение кода листинга программы

Код удаляет узел из бинарного дерева.

  1. Переменная root содержит указатель на корень дерева.
  2. Переменная pointer инициализируется значением root и используется для обхода дерева в ширину.
  3. Переменная parent инициализируется значением NULL и используется для хранения родительского узла текущего узла.
  4. В цикле while происходит обход дерева в ширину до тех пор, пока не будет найдено совпадение или не будут проверены все узлы.
  5. Если узел, который нужно удалить, является листовым узлом (у него нет потомков), то он удаляется и заменяется на NULL.
  6. Если узел имеет только одного потомка, то этот потомк становится новым узлом на месте текущего узла.
  7. Если узел имеет двух потомков, то нужно найти наиболее левый узел в правой поддереве и заменить текущий узел на этот наиболее левый узел.
  8. После удаления узла, pointer и parent сбрасываются в NULL.
  9. Выводится сообщение об удалении узла и сам удаленный узел освобождается с помощью delete.

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 4.1 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы