Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/22: Рейтинг темы: голосов - 22, средняя оценка - 4.86
144 / 144 / 32
Регистрация: 26.10.2008
Сообщений: 782
1

Найти путь максимальной длины между вершинами разной высоты бинарного дерева

20.02.2010, 18:12. Просмотров 4587. Ответов 6
Метки нет (Все метки)

Я уже задавал аналогичный вопрос в другом разделе форума, но там просмотров меньше чем в этом разделе и ответа нет. Так что прошу прощения.

Задача заключается в том, что нужно найти в бинарном поисковом дереве путь максимальной длины между вершинами разной высоты с минимальной суммой конечных вершин. Если таких путей несколько, то выбрать из них тот, у которого корневая вершина имеет наименьшее ключевое значение. Удалить (правым удалением), если существует, среднюю по значению вершину этого пути.
Замечание.
В случае неоднозначности выбора удаляемой вершины (например, несколько путей максимальной длины между вершинами разной высоты и с минимальной суммой ключей конечных вершин имеют один и тот же корень, но средние по значению вершины этих путей не совпадают) ничего из дерева удалять не нужно.
Пример входных данных
10, 5, 12, 11
Пример выходных данных, полученных прямым левым обходом итогового дерева
11, 5, 12

Не могу понять, как получились выходные данные.
Исходя из входных данных, дерево имеет следующий вид:
[ссылка невалидна]

Возможные пути, насколько я понимаю, имеют вид:
5-10, 10-12, 10-12-11, 5-10-12-11

Самый длинный путь здесь: 5-10-12-11.
Средней вершины в нём вообще не существует, т.к. длина пути чётная.
Но в выходных данных удалена вершина 10, которая вообще не является средней ни в каком из путей.

Вероятности того, что входные данные некорректные скорее всего нет.
Скажите, пожалуйста, в чём я ошибаюсь?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.02.2010, 18:12
Ответы с готовыми решениями:

В БПД найти путь максимальной длины между вершинами разной высоты с минимальной суммой конечных вершин.
Есть такая задача: Найти путь максимальной длины между вершинами разной высоты с минимальной...

Найти на графе путь между двумя вершинами, который содержит ребра как можно большей длины
Может кто-нибудь написать последовательность действий или, если у такого алгоритма есть название,...

Определить путь максимальной длины от корня до листа дерева
Дано дерево (необязательно бинарное). Определить путь максимальной длины от корня до листа. Кому...

Найти вид зависимости горизонтальной длины полета тела и максимальной высоты траектории
Найти вид зависимости горизонтальной длины полета тела и максимальной высоты траектории от одного...

6
║XLR8║
1098 / 840 / 256
Регистрация: 25.07.2009
Сообщений: 4,161
Записей в блоге: 5
20.02.2010, 18:38 2
пройдись по всех предках одной из вершин, и если их конечно не очень много и занеси параметры в масив а потом выбери наиболее подходящий вариант.
0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
20.02.2010, 18:47 3
удалить среднюю по значению
(5+10+12+11)/4 = 9.5, то есть ближе всего к этому 10
0
144 / 144 / 32
Регистрация: 26.10.2008
Сообщений: 782
20.02.2010, 19:13  [ТС] 4
Lolcht0, средней по значению вершиной является такая, что найдётся ровно x вершин большьх по значению заданной и ровно x меньших заданной. Из этого следует, что средняя вершина есть только у пути нечётной длины.

outoftime, это и понятно. Только можно не заносить все пути сразу, а по очереди искать пути, при этом запоминая длину. Если какой-нибудь из путей больше, то стереть прежний и занести текущий.

Я сомневаюсь, что правильно нашёл все пути. Скажите, в чём я ошибаюсь?
0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
20.02.2010, 19:16 5
но, если следовать твоим предположениям, то решения нет)) а если моим - то есть и оно согласуется с выводом)) метод подгона
0
144 / 144 / 32
Регистрация: 26.10.2008
Сообщений: 782
20.02.2010, 19:41  [ТС] 6
Думаю, "метод подгона" не действует, тем более, когда есть точное определение.
Возможно, я неправильно нашёл возможные пути.
Может быть, кто-нибудь знает в чём ошибка.
0
kuperrr
04.12.2012, 22:10 7
Дима скинь мне плиз эту прогу если осталась у тебя!!
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.12.2012, 22:10

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

Графы. Найти путь максимальной длины
Есть два входных файла, в первом вершина - и ее координаты. Во втором, какая вершина с какой...

Найти путь максимальной длины, и проходящий через заданное множество вершин
5)Дано бинарное дерево. Найти путь максимальной длины, и проходящий через заданное множество...

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

Найти путь максимальной длины и отразить дерево зеркально относительно этого пути
Найти путь максимальной длины и отразить дерево зеркально относительно этого пути.Буду благодарен:)


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

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

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