Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855254 Mon, 29 Nov 2021 16:12:11 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855254 Цитата FasterHarder @ 28.11.21, 21:39

Скрытый текст

scrambrellaда, все верно...я его НЕ понимаю, тем более он вводит какой-то собственный язык для всех примеров (насколько я помню) + вроде у него оооооочень много всесторонней математики в объяснениях (всякие алгоритмические доказательства - полная жесть и на мое ИМХО это чуть ли не самое сложное - уметь доказывать тот или иной алгоритм
Мой автор Г.Шилдт) доступно, авторитетно объясняет...

Даже пропуская тексты программ можно кое-что понять. Математика в Кнуте относительно понятная, часть алгоритмов с поясняющими картинками. Собственный ЯП Кнута раздражает. Сам его пока не освоил. Как он сам пишет - это что-то близкое к ассемблеру.]]> scrambrella Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855200 Sun, 28 Nov 2021 21:39:56 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855200

Скрытый текст

]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855194 Sun, 28 Nov 2021 20:53:18 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855194 Цитата FasterHarder @ 26.11.21, 18:58

scrambrella, Кнута я бы читал с большим удовольствием, если бы не одно НО...

Лень матушка - единственное но, по которому никто не читает Кнута. Чтение Кнута требует ЗНАЧИТЕЛЬНЫХ умственных усилий, а люди стремятся экономить мышление.]]> scrambrella Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855105 Fri, 26 Nov 2021 18:58:41 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855105 Вот главная функция, которая находит узел, через которую пройдет макс.путь удовлетворяющий условиям:

void Find_root_max_path(BST *proot, BST **pnode_path, int pmax_height)

{

if(proot != NULL)

{

int current_height = Height(proot->left) + Height(proot->right);

if(current_height > pmax_height)

{

pmax_height = current_height;

*pnode_path = proot;

}

Find_root_max_path(proot->left, pnode_path, pmax_height);

Find_root_max_path(proot->right, pnode_path, pmax_height);

}

а ведь наверняка это можно реализовать ЧЕРЕЗ функцию, которая в качестве ответа вернет указатель на узел, являющийся "точкой перелома" макс.пути - вообще без понятия, как это реализуют на рекурсии... и так сойдет (с) )

Добавлено 26.11.21, 19:00
Akina, спс за помощь

scrambrella, Кнута я бы читал с большим удовольствием, если бы не одно НО...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855014 Thu, 25 Nov 2021 09:39:04 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3855014 FasterHarder
Ну всё так.
Как я понимаю, у тебя вся проблема - это как именно сделать алгоритмически, верно? Я бы делал так.

Добавляем каждому узлу свойство "уровень". У корня - 1, у его дочек - 2, и так далее. Заполняем поиском в ширину или в глубину - как захочешь. Добавляем каждому узлу свойство "длина". Обрабатываем полученный список поиском "из глубины к поверхности" (т.е. начинаем с макс. глубины, и в порядке уменьшения послойно). Для узла "длина" = 1 + макс("длина правого", "длина левого"), при отсутствии потомка справа и/или слева считаем его длину за ноль. Также считаем "текущий максимум" = 1 + "длина левого" + "длина правого" и сравниваем его с текущим глобальным (который изначально нулевой), если больше - запоминаем новое значение. Когда дойдём до корня и обработаем его - выводим полученный глобальный "текущий максимум".]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854980 Wed, 24 Nov 2021 17:00:55 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854980 Цитата FasterHarder @ 23.11.21, 19:37

В вики ЭКСПЕРТЫ(!) пишут, что потомки - все узлы, располагающиеся ниже узла, т е прямые дети НЕ РАВНО потомкам, т к прямых детей узла может быть {0; 1; 2}. Но мне кажется, что в анализе достаточно будет смотреть только на прямых детей.

Вместо диванных ЭКСПЕРТОВ(!) читайте Кнута.]]> scrambrella Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854971 Wed, 24 Nov 2021 15:45:01 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854971 Akina, у меня есть уже готовая (и работающая) функция нахождение высоты дерева.
В итоге резюмирую алгоритм.
Надо найти среди всех узлов исходного ДДП вершину, у которой left(h) + right(h) --> max. Как это сделать? Обходом (любым), как я понимаю рекурсивным. Думаю, что справлюсь, на крайняк заведу глобальную переменную max_height.

После этого 3 случая имеем:
1. если левое поддерево пустое, то ответ right(h).
2. если правое поддерево пустое, то ответ left(h).
3. если есть оба сына, то ответ: right(h) + left(h) - 1.

Один из концов макс. пути - ЛИСТ(!), другой с 1 или 2 детьми. Поэтому в формуле п3 (-1), чтобы подняться на уровень выше от листа.
Еще такой момент: мне ведь по задаче надо найти лишь ДЛИНУ макс.пути, при этом не нужно находить между какими узлами он строится. Хотя добавить эти узлы вроде несложно...

Если все-таки я где-то прогнал здесь, то просьба поправить)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854961 Wed, 24 Nov 2021 13:31:29 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854961 Цитата FasterHarder @ 24.11.21, 10:42

а неужели нельзя обойтись высотами левого и правого поддерева для текущего узла...
если получить ДЛЯ каждого узла исходного ДДП высоту левого и правого поддерева.

Так я именно это и описываю. Просто я изначально предполагаю, что ничего этого - ни максимальной для узла глубины ветви его потомков (по отдельности), ни путей, ни чего-то ещё,- не имеется.

То, что ты говоришь - это в моём описании обратный ход.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854943 Wed, 24 Nov 2021 10:42:34 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854943 Цитата Akina @ 24.11.21, 05:01

Всё

)

а неужели нельзя обойтись высотами левого и правого поддерева для текущего узла...
если получить ДЛЯ каждого узла исходного ДДП высоту левого и правого поддерева. Разве MAX(left(h) + right(h)) не будут показывать узел, который является точкой перелома макс.пути? Ведь если знать корень поддерева, через который проходит макс.путь, то дальше вроде уже легко становится (вроде!)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854908 Wed, 24 Nov 2021 05:01:46 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854908
Строим пути от корня ко всем листьям. Дополняем каждый узел его уровнем и, возможно, полным путём. Если что лишнее - потом при оптимизации удалится. Идём обратно. Для каждого не-листа имеем 1 или 2 потомка. У каждого потомка имеется свой текущий максимальный путь. Соответственно получаем два значения - максимальный путь от текущего узла до дальнего листа (тот самый текущий максимальный путь) и длину пути через текущий узел до дальних листьев. Забираемся так по дереву до корня. В результате получаем массив максимальных путей, откуда берём самый-самый максимум. Всё.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854903 Tue, 23 Nov 2021 19:37:15 +0000 Поиск пути в бинарном дереве https://forum.sources.ru/index.php?showtopic=424283&view=findpost&p=3854903
Есть такая структура, описывающая узел ДДП:

структура "Узел дерева"

ключ (целое)

ссылка на левое

ссылка на правое

И надо найти максимальный путь между его 2мя вершинами (любыми), причем эти вершины должны иметь различное число потомков. В бинарном дереве не меньше 2ух узлов.
----------------------------------------
В вики ЭКСПЕРТЫ(!) пишут, что потомки - все узлы, располагающиеся ниже узла, т е прямые дети НЕ РАВНО потомкам, т к прямых детей узла может быть {0; 1; 2}. Но мне кажется, что в анализе достаточно будет смотреть только на прямых детей.

Вроде гарантировано, что макс. путь проходит ЧЕРЕЗ корень дерева, даже, если отсутствует какая-либо ветвь у корня, поправьте, если не так это.
Находим высоту левого поддерева (от корня). Если левой ветви нет, то высота = 0, ничего страшного, это не мешает алгоритму. Если левая ветвь есть, то гарантировано первый узел, от которого строится искомый путь, является ЛИСТОМ, иначе от корня строится путь и он имеет одного прямого ребенка.

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

Т е для решения надо применить ТОЛЬКО вспомогательную функцию получения высота заданного дерева, да?? Или здесь все гораздо тоньше? Были мысли делать БФС еще...не знаю...

подскажите, как быть-то, буду признателен

p.s. не исключаю, что все, что выше написал по своему алгоритму является чушью и алгоритм здесь абсолютно другой нужен)

Добавлено 23.11.21, 19:45
кстати, я понял, что макс.путь необязательно должен проходить через корень исходного ДДП...мда..сложнее тут все (как обычно!).
значит, надо сначала найти "корень", так сказать точку перегиба макс. пути...]]> FasterHarder Алгоритмы