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

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

Войти
Регистрация
Восстановить пароль
 
Isantel
13 / 13 / 1
Регистрация: 23.11.2010
Сообщений: 254
#1

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

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

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

Добавлено через 3 часа 5 минут
ап............
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2013, 20:50     Процедура обхода для дерева
Посмотрите здесь:

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

Вывод обхода дерева в файл - C++
Есть бинарное дерево, не могу реализовать в нем вывод обхода дерева в файл из функции show(Node *&der), вроде как-то можно забить данные из...

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
201 / 145 / 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
Кактус
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
_
201 / 145 / 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
Кактус
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++
Кхм. Попытался реализовать итератор для обхода по бинарному дереву... Наткнулся на запару. Дерево должно быть обязательно круговым, чтобы...

Для чего нужна main и в чём принцип обхода массива в цикле - C++
Доброе время суток, хотелось бы услышать ответы на несколько легких вопросов. Зачем писать int main()\void main(), и что за этим стоит;...

Запись бинарного дерева в файл и восстановление из него этого дерева - C++
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на структуру с данными, 2 и 3й указатель на...

Написать шаблон бинарного дерева с функцией распечатки дерева - C++
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного дерева с функцией распечатки дерева *(+(d,e),c) в виде...


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

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

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