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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Flamе
9 / 9 / 0
Регистрация: 25.10.2009
Сообщений: 152
29.07.2010, 22:58     Как работает алгоритм удаления дерева #1
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);
вызываются одновременно или последовательно???
и вапще удалит ли вся эта функция дерево полностью сразу или нужно создать для неё цикл, т.к. она будет удалять крайние вершины??
подскажите пожалуйста.... заранее огромное спасибо))
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 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
2293 / 1663 / 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
2293 / 1663 / 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++
C++ Не могли бы объяснить, как работает эта функция для удаления цифр?

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

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

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