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

@Isantel · Регистрация: 23.11.2010

Студворк — интернет-сервис помощи студентам

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

Добавлено через 3 часа 5 минут
ап............

@ya_noob · 25.03.2013, 09:07

и в чем сложности?
алгоритм примерно такой:
{
проверяете не постое ли дерево
рекурсивно обходите левое поддерево и запоминаете его высоту
рекурсивно обходите правое поддерево и запоминаете его высоту
сравниваете эти высоты и что-то делаете с этой информацией("...подсчитайте показатель сбалансированности...")
возвращаете максимальную из высот поддеревьев + 1
}

@Isantel · 25.03.2013, 17:20 **[ТС]**

ya_noob, а не могли бы вы помочь это реализовать? ранее с деревьями вообще дела не имел, да и в дальнейшем врятли пригодится...

@eocron · 25.03.2013, 17:35

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 · 25.03.2013, 17:53

Сообщение от Isantel

в дальнейшем врятли пригодится...

опрометчивый вывод.

Сообщение от eocron

C++
1
return (height_left > height_right)? height_left : height_right;

надо +1 добавить, а то все поддеревья будут иметь нулевую высоту

@eocron · 25.03.2013, 18:02

Сообщение от ya_noob

опрометчивый вывод.

надо +1 добавить, а то все поддеревья будут иметь нулевую высоту

Да, да. Моя ошибка.

@Isantel · 03.04.2013, 15:38 **[ТС]**

Сообщение от ya_noob

опрометчивый вывод.

надо +1 добавить, а то все поддеревья будут иметь нулевую высоту

не могли бы вы в коде показать куда +1 добавлять, а то я не бум-бум в деревьях совсем...))

@eocron · 03.04.2013, 20:15

Сообщение от Isantel

не могли бы вы в коде показать куда +1 добавлять, а то я не бум-бум в деревьях совсем...))

Например, return 1 + (...)?...:...;

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@Isantel 13 / 13 / 1 Регистрация: 23.11.2010 Сообщений: 254

	Процедура обхода для дерева 24.03.2013, 20:50. Показов 1215. Ответов 7 Метки нет (Все метки) Постройте процедуру обхода для получения следующей информации о деревьях - подсчитайте показатель сбалансированности для бинарного дерева (т.е. максимальную разницу между длинами правого и левого поддеревьев для каждой вершины) Добавлено через 3 часа 5 минут ап............ 0

@ya_noob _ 317 / 151 / 27 Регистрация: 08.10.2011 Сообщений: 432
	25.03.2013, 09:07
	и в чем сложности? алгоритм примерно такой: { проверяете не постое ли дерево рекурсивно обходите левое поддерево и запоминаете его высоту рекурсивно обходите правое поддерево и запоминаете его высоту сравниваете эти высоты и что-то делаете с этой информацией("...подсчитайте показатель сбалансированности...") возвращаете максимальную из высот поддеревьев + 1 } 1

@Isantel 13 / 13 / 1 Регистрация: 23.11.2010 Сообщений: 254
	25.03.2013, 17:20 [ТС]
	ya_noob, а не могли бы вы помочь это реализовать? ранее с деревьями вообще дела не имел, да и в дальнейшем врятли пригодится... 0