Форум программистов, компьютерный форум CyberForum.ru

Удаление Узла бинарного дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
scofielcl
4 / 4 / 0
Регистрация: 11.09.2011
Сообщений: 143
30.12.2012, 20:32     Удаление Узла бинарного дерева #1
Добрый вечер.
Имеем Бинарное дерево поиска.

При удалении некоторого узла . возникают три случая. Один из случаев , наличие у удаляемого узла обоих дочерних узлов.

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

Вопрос в следующем . как рекурсивно найти самый левый . правого поддерева. и его родителя.

Пробовал сделать через while , но для некоторых случаев данный код не корректен.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
   /*
             * Крайний левый потомок , правого поддерева
             * l будем использовать как родителя крайнего левого узла
             * а  - бегает по циклу
             * p - есть удаляемый узел
             * s - тот самый левый крайний узел
             */
            l = p; 
            bintree *a = p->right;    // переходим на правую ветвь
            bintree *s;                   
            s->inf = (p->right)->inf; // задаем s начальное значение . 
            /*
             * Цикл работает пока есть узлы
             * 
             */
             
            while(a->left || a->right){ 
                if(a->left){ // отдаем предпочтение левому поддереву 
                   l = a;  // родитель крайнего левого
                   a=a->left; // переход в крайний левый
                   s->inf = a->inf; // присваиваем данное значение
                }
                else if(a->right)a=a->right; // иначе если нет левого . бежим вправо , может там найдем крайний левый..
            }
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ViktorKozlov
133 / 125 / 2
Регистрация: 13.12.2012
Сообщений: 293
30.12.2012, 23:52     Удаление Узла бинарного дерева #2
Есть исходник курсовой, где добавление, поиск и удаление в дереве, с подробными комментариями. Если нужно, могу скинуть
scofielcl
4 / 4 / 0
Регистрация: 11.09.2011
Сообщений: 143
31.12.2012, 11:04  [ТС]     Удаление Узла бинарного дерева #3
Но в данном коде . удаление узла с двумя дочерними узлами . организовано не так как нужно.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Delete_Node_BinaryTree(BinaryTree** Node,int Data){
  if ( (*Node) != NULL ){
    if ((*Node)->Data == Data){
      BinaryTree* ptr = (*Node);
      if ( (*Node)->Left == NULL && (*Node)->Right == NULL ) (*Node) = NULL;
      else if ((*Node)->Left == NULL) (*Node) = ptr->Right;
      else if ((*Node)->Right == NULL) (*Node) = ptr->Left;
      else {
        (*Node) = ptr->Right;
        BinaryTree ** ptr1;
        ptr1 = Node;
        while (*ptr1 != NULL) 
          ptr1 = &((*ptr1)->Left);
        (*ptr1) = ptr->Left;
      }
      delete(ptr);
      Delete_Node_BinaryTree(Node,Data);
    }
    else {
      Delete_Node_BinaryTree(&((*Node)->Left),Data);
      Delete_Node_BinaryTree(&((*Node)->Right),Data);
    }
  }
}
ViktorKozlov
133 / 125 / 2
Регистрация: 13.12.2012
Сообщений: 293
31.12.2012, 16:49     Удаление Узла бинарного дерева #4
А как вы пришли к выводу, что некорректно? Какую ошибку выдает?

Добавлено через 21 минуту
Да, и если у узла есть и левый, и правый узел, то удалять нужно не этот узел, а самый левый у его правого узла, т. е. самый минимальный. А этому узлу просто присваивать ЗНАЧЕНИЕ минимального узла (но не его два указателя, иначе наш узел будет ссылаться не туда, куда ссылался до этого, а туда, куда ссылался мин. узел). Минимальный узел удаляется этой же функцией удаления, куда в качестве аргументов передаются указатель на него (в вашем случае, как я понял, указатель на указатель) и его data, по которому будет идти поиск этого узла.
При удалении этого минимального узла могут возникнуть только 2 случая:
1). У этого узла левый и правый узел = null
2). У этого узла левый узел = null, а правый != null
Yandex
Объявления
31.12.2012, 16:49     Удаление Узла бинарного дерева
Ответ Создать тему
Опции темы

Текущее время: 17:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru