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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Flamе
9 / 9 / 0
Регистрация: 25.10.2009
Сообщений: 152
#1

Как работает алгоритм удаления дерева - C++

29.07.2010, 22:58. Просмотров 1152. Ответов 6
Метки нет (Все метки)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct tree
{
Ti;
tree <T> *l, *r;
}
 
void tree_remove (tree <T> *&r)
{
if (!r) return;
tree_remove (r->l);
tree_remove (r->r);
delete r;
r=NULL;
}
вобщем чё-то клинит меня и никак не могу понять вроде бы элементарную вещь: функции
tree_remove (r->l);
tree_remove (r->r);
вызываются одновременно или последовательно???
и вапще удалит ли вся эта функция дерево полностью сразу или нужно создать для неё цикл, т.к. она будет удалять крайние вершины??
подскажите пожалуйста.... заранее огромное спасибо))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2010, 22:58     Как работает алгоритм удаления дерева
Посмотрите здесь:

C++ Алгоритм реализации двоичного дерева
C++ Алгоритм удаления записи из базы данных
C++ итерационный метод удаления бинарного дерева
C++ Функция удаления элемента из дерева, ошибка в коде
C++ Алгоритм удаления элемента из массива
C++ Удаления узла из бинарного дерева поиска
C++ Функция удаления листа (или ветки) бинарного дерева
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2297 / 1667 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
29.07.2010, 23:02     Как работает алгоритм удаления дерева #2
Цитата Сообщение от Flamе Посмотреть сообщение
вызываются одновременно или последовательно???
Последовательно.
Цитата Сообщение от Flamе Посмотреть сообщение
и вапще удалит ли вся эта функция дерево полностью сразу или нужно создать для неё цикл, т.к. она будет удалять крайние вершины??
Удалит рекурсивно все дерево.

Есть более простое решение без лишних функций. Достаточно в деструкторе узла дерева удалить поддеревья:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename T>
struct TreeNode<T> {
   // ...
   ~TreeNode() {
      delete left;
      delete right;
   }
   TreeNode<T>* left;
   TreeNode<T>* right;
   // ...
};
 
// ...
// root - корень дерева
delete root; // Удаление корня вызовет рекурсивное удаление всего дерева
// ...
Постигайте рекурсию.
Flamе
9 / 9 / 0
Регистрация: 25.10.2009
Сообщений: 152
29.07.2010, 23:08  [ТС]     Как работает алгоритм удаления дерева #3
спасибо)) да, походу с рекурсией у меня проблема... мозг её не осиливает))
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2297 / 1667 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
29.07.2010, 23:10     Как работает алгоритм удаления дерева #4
Цитата Сообщение от Flamе Посмотреть сообщение
спасибо)) да, походу с рекурсией у меня проблема... мозг её не осиливает))
Это наиболее сложная для мозга тема в программировании, так что это нормально. Больше практикуйтесь. Бинарные деревья неплохо подходят для этой цели.
Flamе
9 / 9 / 0
Регистрация: 25.10.2009
Сообщений: 152
29.07.2010, 23:10  [ТС]     Как работает алгоритм удаления дерева #5
всё же спрошу ещё кое-что... как работает эта рекурсия? ведь мы движемся по вершинам вниз, а назад не возвращаемся?? или для каждой вершины, принимая её как корень нового дерева, данная функция работает несколько раз, пока не удалит её??
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2297 / 1667 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
29.07.2010, 23:15     Как работает алгоритм удаления дерева #6
Цитата Сообщение от Flamе Посмотреть сообщение
для каждой вершины, принимая её как корень нового дерева, данная функция работает несколько раз, пока не удалит её??
Именно так, сначала полностью удаляется левое поддерево, затем правое. Попробуйте мысленно развернуть очередь рекурсионных вызовов. Должно помочь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2010, 23:18     Как работает алгоритм удаления дерева
Еще ссылки по теме:

Алгоритм удаления цифр из числа C++
C++ Как работает алгоритм Khazad
C++ Не могли бы объяснить, как работает эта функция для удаления цифр?
C++ Функция удаления всех четных элементов AVL-дерева
C++ Как работает алгоритм ПП рюкзака?

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

Или воспользуйтесь поиском по форуму:
Flamе
9 / 9 / 0
Регистрация: 25.10.2009
Сообщений: 152
29.07.2010, 23:18  [ТС]     Как работает алгоритм удаления дерева #7
ещё раз спасибо))
Yandex
Объявления
29.07.2010, 23:18     Как работает алгоритм удаления дерева
Ответ Создать тему
Опции темы

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