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

Процедура обхода для дерева - C++

Восстановить пароль Регистрация
 
Isantel
13 / 13 / 1
Регистрация: 23.11.2010
Сообщений: 254
24.03.2013, 20:50     Процедура обхода для дерева #1
Постройте процедуру обхода для получения следующей информации о деревьях
- подсчитайте показатель сбалансированности для бинарного дерева (т.е. максимальную разницу между длинами правого и левого поддеревьев для каждой вершины)

Добавлено через 3 часа 5 минут
ап............
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
25.03.2013, 09:07     Процедура обхода для дерева #2
и в чем сложности?
алгоритм примерно такой:
{
проверяете не постое ли дерево
рекурсивно обходите левое поддерево и запоминаете его высоту
рекурсивно обходите правое поддерево и запоминаете его высоту
сравниваете эти высоты и что-то делаете с этой информацией("...подсчитайте показатель сбалансированности...")
возвращаете максимальную из высот поддеревьев + 1
}
Isantel
13 / 13 / 1
Регистрация: 23.11.2010
Сообщений: 254
25.03.2013, 17:20  [ТС]     Процедура обхода для дерева #3
ya_noob, а не могли бы вы помочь это реализовать? ранее с деревьями вообще дела не имел, да и в дальнейшем врятли пригодится...
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
25.03.2013, 17:35     Процедура обхода для дерева #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>// T - Тип твоего узла, например называется node
int h(T *a)//рекурсивная функция
{
    if(a)
    {
         int height_left = h(a->l);
         int height_right = h(a->r);
         
         //здесь делай что-хочешь обращайся к данным узла [a] или высчитывай разницу между высотами или еще что
         //собственно, просто повторенный точь в точь алгоритм сверху
 
         return (height_left > height_right)? height_left : height_right;
    }
    return 0;
}
Пихаешь в функцию корень дерева - на выходе получаешь высоту максимального поддерева.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
25.03.2013, 17:53     Процедура обхода для дерева #5
Цитата Сообщение от Isantel Посмотреть сообщение
в дальнейшем врятли пригодится...
опрометчивый вывод.


Цитата Сообщение от eocron Посмотреть сообщение
C++
1
return (height_left > height_right)? height_left : height_right;
надо +1 добавить, а то все поддеревья будут иметь нулевую высоту
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
25.03.2013, 18:02     Процедура обхода для дерева #6
Цитата Сообщение от ya_noob Посмотреть сообщение
опрометчивый вывод.



надо +1 добавить, а то все поддеревья будут иметь нулевую высоту
Да, да. Моя ошибка.
Isantel
13 / 13 / 1
Регистрация: 23.11.2010
Сообщений: 254
03.04.2013, 15:38  [ТС]     Процедура обхода для дерева #7
Цитата Сообщение от ya_noob Посмотреть сообщение
опрометчивый вывод.



надо +1 добавить, а то все поддеревья будут иметь нулевую высоту
не могли бы вы в коде показать куда +1 добавлять, а то я не бум-бум в деревьях совсем...))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.04.2013, 20:15     Процедура обхода для дерева
Еще ссылки по теме:

Разработать алгоритм и написать программу прошивания дерева при симметричном порядке обхода его C++
Деструктор для дерева C++
C++ Разобраться с рекурсивной функцией обхода бинарного дерева

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

Или воспользуйтесь поиском по форуму:
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
03.04.2013, 20:15     Процедура обхода для дерева #8
Цитата Сообщение от Isantel Посмотреть сообщение
не могли бы вы в коде показать куда +1 добавлять, а то я не бум-бум в деревьях совсем...))
Например, return 1 + (...)?...:...;
Yandex
Объявления
03.04.2013, 20:15     Процедура обхода для дерева
Ответ Создать тему
Опции темы

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