| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Поиск пути в бинарном дереве |
| Автор: FasterHarder 23.11.21, 19:37 |
| Всем хай! Сходу к делу! Есть такая структура, описывающая узел ДДП: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> структура "Узел дерева" ключ (целое) ссылка на левое ссылка на правое И надо найти максимальный путь между его 2мя вершинами (любыми), причем эти вершины должны иметь различное число потомков. В бинарном дереве не меньше 2ух узлов. ---------------------------------------- В вики ЭКСПЕРТЫ(!) пишут, что потомки - все узлы, располагающиеся ниже узла, т е прямые дети НЕ РАВНО потомкам, т к прямых детей узла может быть {0; 1; 2}. Но мне кажется, что в анализе достаточно будет смотреть только на прямых детей. Вроде гарантировано, что макс. путь проходит ЧЕРЕЗ корень дерева, даже, если отсутствует какая-либо ветвь у корня, поправьте, если не так это. Находим высоту левого поддерева (от корня). Если левой ветви нет, то высота = 0, ничего страшного, это не мешает алгоритму. Если левая ветвь есть, то гарантировано первый узел, от которого строится искомый путь, является ЛИСТОМ, иначе от корня строится путь и он имеет одного прямого ребенка. Находим высоту правого поддерева (от корня). второй узел, до которого строится путь является листом. Если слева был лист и справа был лист, то макс. путь = высота (слева) + высота(справа) - 1 ?? Если слева нет поддерева от корня, то макс. путь = высота (справа)?? Т е для решения надо применить ТОЛЬКО вспомогательную функцию получения высота заданного дерева, да?? Или здесь все гораздо тоньше? Были мысли делать БФС еще...не знаю... подскажите, как быть-то, буду признателен p.s. не исключаю, что все, что выше написал по своему алгоритму является чушью и алгоритм здесь абсолютно другой нужен) Добавлено кстати, я понял, что макс.путь необязательно должен проходить через корень исходного ДДП...мда..сложнее тут все (как обычно!). значит, надо сначала найти "корень", так сказать точку перегиба макс. пути... |
| Автор: Akina 24.11.21, 05:01 |
| Навскидку рисуется такое. Строим пути от корня ко всем листьям. Дополняем каждый узел его уровнем и, возможно, полным путём. Если что лишнее - потом при оптимизации удалится. Идём обратно. Для каждого не-листа имеем 1 или 2 потомка. У каждого потомка имеется свой текущий максимальный путь. Соответственно получаем два значения - максимальный путь от текущего узла до дальнего листа (тот самый текущий максимальный путь) и длину пути через текущий узел до дальних листьев. Забираемся так по дереву до корня. В результате получаем массив максимальных путей, откуда берём самый-самый максимум. Всё. |
| Автор: FasterHarder 24.11.21, 10:42 |
| ) а неужели нельзя обойтись высотами левого и правого поддерева для текущего узла... если получить ДЛЯ каждого узла исходного ДДП высоту левого и правого поддерева. Разве MAX(left(h) + right(h)) не будут показывать узел, который является точкой перелома макс.пути? Ведь если знать корень поддерева, через который проходит макс.путь, то дальше вроде уже легко становится (вроде!) |
| Автор: Akina 24.11.21, 13:31 |
| Цитата FasterHarder @ а неужели нельзя обойтись высотами левого и правого поддерева для текущего узла... если получить ДЛЯ каждого узла исходного ДДП высоту левого и правого поддерева. Так я именно это и описываю. Просто я изначально предполагаю, что ничего этого - ни максимальной для узла глубины ветви его потомков (по отдельности), ни путей, ни чего-то ещё,- не имеется. То, что ты говоришь - это в моём описании обратный ход. |
| Автор: FasterHarder 24.11.21, 15:45 |
| 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), чтобы подняться на уровень выше от листа. Еще такой момент: мне ведь по задаче надо найти лишь ДЛИНУ макс.пути, при этом не нужно находить между какими узлами он строится. Хотя добавить эти узлы вроде несложно... Если все-таки я где-то прогнал здесь, то просьба поправить) |
| Автор: scrambrella 24.11.21, 17:00 |
| Цитата FasterHarder @ В вики ЭКСПЕРТЫ(!) пишут, что потомки - все узлы, располагающиеся ниже узла, т е прямые дети НЕ РАВНО потомкам, т к прямых детей узла может быть {0; 1; 2}. Но мне кажется, что в анализе достаточно будет смотреть только на прямых детей. Вместо диванных ЭКСПЕРТОВ(!) читайте Кнута. |
| Автор: Akina 25.11.21, 09:39 |
| FasterHarder Ну всё так. Как я понимаю, у тебя вся проблема - это как именно сделать алгоритмически, верно? Я бы делал так. Добавляем каждому узлу свойство "уровень". У корня - 1, у его дочек - 2, и так далее. Заполняем поиском в ширину или в глубину - как захочешь. Добавляем каждому узлу свойство "длина". Обрабатываем полученный список поиском "из глубины к поверхности" (т.е. начинаем с макс. глубины, и в порядке уменьшения послойно). Для узла "длина" = 1 + макс("длина правого", "длина левого"), при отсутствии потомка справа и/или слева считаем его длину за ноль. Также считаем "текущий максимум" = 1 + "длина левого" + "длина правого" и сравниваем его с текущим глобальным (который изначально нулевой), если больше - запоминаем новое значение. Когда дойдём до корня и обработаем его - выводим полученный глобальный "текущий максимум". |
| Автор: FasterHarder 26.11.21, 18:58 |
| В общем у меня вроде(!) все получилось, правда такое чувство, что все это дело можно кодировать гораздо точнее и оптимальнее. Вот главная функция, которая находит узел, через которую пройдет макс.путь удовлетворяющий условиям: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> 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); } } а ведь наверняка это можно реализовать ЧЕРЕЗ функцию, которая в качестве ответа вернет указатель на узел, являющийся "точкой перелома" макс.пути - вообще без понятия, как это реализуют на рекурсии... и так сойдет (с) ) Добавлено Akina, спс за помощь scrambrella, Кнута я бы читал с большим удовольствием, если бы не одно НО... |
| Автор: scrambrella 28.11.21, 20:53 |
| Лень матушка - единственное но, по которому никто не читает Кнута. Чтение Кнута требует ЗНАЧИТЕЛЬНЫХ умственных усилий, а люди стремятся экономить мышление. |
| Автор: FasterHarder 28.11.21, 21:39 |
| Скрытый текст scrambrellaда, все верно...я его НЕ понимаю, тем более он вводит какой-то собственный язык для всех примеров (насколько я помню) + вроде у него оооооочень много всесторонней математики в объяснениях (всякие алгоритмические доказательства - полная жесть и на мое ИМХО это чуть ли не самое сложное - уметь доказывать тот или иной алгоритм Мой автор Г.Шилдт) доступно, авторитетно объясняет... |
| Автор: scrambrella 29.11.21, 16:12 |
| Цитата FasterHarder @ Скрытый текст scrambrellaда, все верно...я его НЕ понимаю, тем более он вводит какой-то собственный язык для всех примеров (насколько я помню) + вроде у него оооооочень много всесторонней математики в объяснениях (всякие алгоритмические доказательства - полная жесть и на мое ИМХО это чуть ли не самое сложное - уметь доказывать тот или иной алгоритм Мой автор Г.Шилдт) доступно, авторитетно объясняет... Даже пропуская тексты программ можно кое-что понять. Математика в Кнуте относительно понятная, часть алгоритмов с поясняющими картинками. Собственный ЯП Кнута раздражает. Сам его пока не освоил. Как он сам пишет - это что-то близкое к ассемблеру. |