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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
scofielcl
4 / 4 / 0
Регистрация: 11.09.2011
Сообщений: 145
#1

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

30.12.2012, 20:32. Просмотров 1514. Ответов 3
Метки нет (Все метки)

Добрый вечер.
Имеем Бинарное дерево поиска.

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

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

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

Пробовал сделать через 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; // иначе если нет левого . бежим вправо , может там найдем крайний левый..
            }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.12.2012, 20:32     Удаление Узла бинарного дерева
Посмотрите здесь:

C++ Удаление узла бинарного дерева, проблема с функциями, адресацией
C++ Удаление бинарного дерева по слоям
Функция: удаление узла дерева со всеми потомками C++
Удаление Узла Бинарного Дерева. C++
C++ Удаление узла бинарного дерева
Удаление узла из дерева C++
Удаление вершины бинарного дерева C++
C++ Удаление узла дерева
Освобождение памяти, удаление бинарного дерева C++
C++ Удаления узла из бинарного дерева поиска
C++ Удаление элемента из бинарного дерева
Удаление из бинарного дерева C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ViktorKozlov
133 / 125 / 2
Регистрация: 13.12.2012
Сообщений: 293
30.12.2012, 23:52     Удаление Узла бинарного дерева #2
Есть исходник курсовой, где добавление, поиск и удаление в дереве, с подробными комментариями. Если нужно, могу скинуть
scofielcl
4 / 4 / 0
Регистрация: 11.09.2011
Сообщений: 145
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     Удаление Узла бинарного дерева
Ответ Создать тему
Опции темы

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