Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
13 / 13 / 1
Регистрация: 23.11.2010
Сообщений: 254
1

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

24.03.2013, 20:50. Просмотров 634. Ответов 7
Метки нет (Все метки)


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

Добавлено через 3 часа 5 минут
ап............
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.03.2013, 20:50
Ответы с готовыми решениями:

Процедура обхода для дерева
постройте процедуру обхода для определения длины бинарного(или произвольного) дерева (т.е. длину...

Вывод обхода дерева в файл
Есть бинарное дерево, не могу реализовать в нем вывод обхода дерева в файл из функции show(Node...

Разобраться с рекурсивной функцией обхода бинарного дерева
Люди, помогите разобраться с рекурсивной функцией обхода бинарного дерева. Бьюсь головой об стену,...

Реализация обхода в ширину и глубину бинарного дерева
Как реализовать обход дерева (глубины три, т.е. трех уровневое) в глубину и ширину и что под этим...

7
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
25.03.2013, 09:07 2
и в чем сложности?
алгоритм примерно такой:
{
проверяете не постое ли дерево
рекурсивно обходите левое поддерево и запоминаете его высоту
рекурсивно обходите правое поддерево и запоминаете его высоту
сравниваете эти высоты и что-то делаете с этой информацией("...подсчитайте показатель сбалансированности...")
возвращаете максимальную из высот поддеревьев + 1
}
1
13 / 13 / 1
Регистрация: 23.11.2010
Сообщений: 254
25.03.2013, 17:20  [ТС] 3
ya_noob, а не могли бы вы помочь это реализовать? ранее с деревьями вообще дела не имел, да и в дальнейшем врятли пригодится...
0
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
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;
}
Пихаешь в функцию корень дерева - на выходе получаешь высоту максимального поддерева.
1
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
25.03.2013, 17:53 5
Цитата Сообщение от Isantel Посмотреть сообщение
в дальнейшем врятли пригодится...
опрометчивый вывод.


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



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



надо +1 добавить, а то все поддеревья будут иметь нулевую высоту
не могли бы вы в коде показать куда +1 добавлять, а то я не бум-бум в деревьях совсем...))
0
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
03.04.2013, 20:15 8
Цитата Сообщение от Isantel Посмотреть сообщение
не могли бы вы в коде показать куда +1 добавлять, а то я не бум-бум в деревьях совсем...))
Например, return 1 + (...)?...:...;
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.04.2013, 20:15

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Пронумеровать вершины бинарного дерева в соответствии с порядком концевого обхода
Здравствуйте!!!! Помогите пожалуйста решить задачу. Построить бинарное дерево поиска для заданного...

Разработать алгоритм и написать программу прошивания дерева при симметричном порядке обхода его
Народ интересует такое задание нужно срочно или что по быстрому почитать, чтоб сделать это.

Процедура Create (построение дерева)
Описать процедуру Create(T,n), где n- положительное целое число, которая строит дерево Т: Вроде не...

Построение дерева и процедура обхода дерева
написать программу использующую процедуру построения дерева и процедуру обхода дерева


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

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

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