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

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

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

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

30.12.2012, 20:32. Просмотров 1670. Ответов 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++
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени помогите плиз. .cpp #include <iostream>...

Удаление Узла Бинарного Дерева. - C++
Добрый День.Возникла проблема с реализацией части функции контейнера для удаления элемента с двумя узлами(по всем правилам бинарных...

Удаление узла бинарного дерева, проблема с функциями, адресацией - C++
код: #include <cstdlib> #include <iostream> typedef struct tree{ // обьявляем тип char data; //дата изьятия в формате xx.xx.xxxx ...

Удаления узла из бинарного дерева поиска - C++
Уже довольно много времени убил на эту задачу, теорию понимаю, на практике реализовать никак не получается. Помогите пожалуйста написать...

Удаление узла дерева - C++
Добрый вечер. У меня маленькая проблема - написал шаблон для работы с бинарным деревом поиска. Вроде асе робит, но возникла проблема с...

Удаление узла из дерева - C++
сделав функции добавления,поиска,пару обходов и вывод ввиде дерева в консоли(жаль что нельзя размер по x изменить) при тестировании...

Функция: удаление узла дерева со всеми потомками - C++
подскажите код функции которая удаляет элемент дерева со всеми его потомками NODE *SEARCH(char *key, NODE *root) { NODE...

Удаление вершины бинарного дерева - C++
Как удалять вершины бинарного дерева вместе с потомками?

Удаление бинарного дерева по слоям - C++
вот задачка такая встала и ни че в голову не приходит. как будет выглядеть функция чтоб удаляла бинарное дерево по слоям? плиззз...

Удаление элемента из бинарного дерева - C++
Ругается компилятор в Visual Studio при выполнении кода удаления элемента, а именно в том месте, где нужно удалить элемент с двумя...

Освобождение памяти, удаление бинарного дерева - 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     Удаление Узла бинарного дерева
Ответ Создать тему
Опции темы

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