Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
#1

Удаление узла из дерева - C++

13.12.2010, 13:33. Просмотров 553. Ответов 1
Метки нет (Все метки)

сделав функции добавления,поиска,пару обходов и вывод ввиде дерева в консоли(жаль что нельзя размер по x изменить) при тестировании возникла проблема удаления.
суть в том что когда я удаляю элементы если я удалю все элементы левого поддерева то,теоретически,корнем должен стать узел из правого поддерева но! вылетает прога тогда.
вот почти рабочая функция.что не так?
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int rightmost(uzel *root)//Г±Г*ìûé ГЇГ°Г*âûé
{
  while (root->right != NULL)//ïîêГ* Г*ГҐ äîéäåò äî ГЇГ°Г*âîãî Г± ññûëêîé 0
    root = root->right;//ГЇГ® ГЇГ°Г*âûì ïîäóçëГ*Г¬ ГёГ*ГЈГ*ГІГј
  return root->key;//ГўГҐГ°Г*ГїГҐГ¬ ГІГ® Г·ГІГ® ГІГіГ¤Г* Г§Г*ГІГҐГ±Г*ëîñü
}
 
uzel* del_tree(uzel *root, int val)//ГіГ¤Г*ëåГ*ГЁГҐ
{
  if (root==0) return 0;//åñëè 0 ГІГ*ГЄ 0
  if (root->key == val) //åñëè Г*Г*øëè ГІГ®
  {
        //ГЅГІГ® ýëåìåГ*ГІ-ëèñò
     if (root->left==0 && root->right==0) 
     {
      delete root;//äîñòГ*òî÷Г*Г® ïðîñòî ГіГ¤Г*ëèòü
      return 0;
     }
     if (root->right==0 && root->left != 0)//åñëè ГҐГ±ГІГј îäèГ* ïîòîìîê ëåâûé 
     {
      uzel *temp = root->left;//ГІГ® ïåðåìåГ*Г*îé ГІГЁГЇГ* "óçåë" Г§Г*ГЇГЁГёГҐГ¬ Г§Г*Г*Г·ГҐГ*ГЁГҐ óçëГ*-ïîòîìêГ* ñëåâГ*
      delete root;
      return temp;
     }
     if (root->left==0 && root->right != 0) //ГІГ® æå äëÿ ГЇГ°Г*âîãî
     {
      uzel *temp = root->right;
      delete root;
      return temp;
     }
     root->key = rightmost(root->left);//òåïåðü Гў ГіГ¤Г*ëÿåìîé ïîçèöèè áóäåò ñòîÿòü ýëåìåГ*ГІ Г±Г*ìûé ГЇГ°Г*âûé ëåâîãî ïîääåðåâГ*
     root->left = del_tree(root->left, root->key);//ГЁГ№ГҐГ¬ Гў ëåâîì ïîääåðåâå ýëåìåГ*ГІ Г± ГіГ¤Г*ëÿåìûì Г§Г*Г*Г·ГҐГ*ГЁГҐГ¬ ГЁ ïðîâîäèì ГҐГЈГ® äåçèГ*ГІГҐГЈГ°Г*öèþ
     return root;
  }
  if (val < root->key)//åñëè Г§Г*Г*Г·ГҐГ*ГЁГҐ ìåГ*ГјГёГҐ òîãî Г·ГІГ® Гў êîðГ*ГҐ ГІГ® âûïîëГ*ГЁГІГј ГўГ±ГҐ Г*åîáõîäèìûå îïåðГ*öèÿ äëÿ ëåâîãî ïîääåðåâГ* 
  {
   root->left = del_tree(root->left, val);
   return root;
  }
  if (val > root->key)//ГІГ® æå äëÿ ГЇГ°Г*âîãî 
  { 
   root->right = del_tree(root->right, val);
   return root;
  }
 return root;
}
придерживался правила что при удалении корня новым корнем станет самый правый узел левого поддерева.
или же надо проводить проверку на наличие левого поддерева?

Добавлено через 11 часов 16 минут
ошибка найдена.терь работает
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2010, 13:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Удаление узла из дерева (C++):

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

Удаление Узла бинарного дерева - C++
Добрый вечер. Имеем Бинарное дерево поиска. При удалении некоторого узла . возникают три случая. Один из случаев , наличие у...

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

Удаление узла бинарного дерева - C++
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени помогите плиз. .cpp #include &lt;iostream&gt;...

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

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

1
east1
5 / 5 / 1
Регистрация: 08.05.2010
Сообщений: 30
18.12.2010, 17:00 #2
Выложи пожалуйста код без ошибки.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.12.2010, 17:00
Привет! Вот еще темы с ответами:

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

Как сгенерировать ключ для узла дерева? - C++
В C# для создания сквозной нумерации текстовых заметок можно было просто объявить целую static-переменную в описании класса заметки,...

Определение глубины (числа ветвей) непустого дерева от вершины до заданного узла - C++
Подскажите пожалуйста. Никак не могу найти код нахождения глубины бинарного дерева от вершины до заданного узла. тут весь форум перерыл...

RB tree удаление узла - C++
Народ, подсткажите рекурсивный алгоритм удаления узла RB tree, или где найти можно... второй день в гугле сижу, видимо руки не от туда...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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