Поиск наидлиннейшего пути в бинарном дереве поиска
|
|
Четверг, 10 Декабря 2020 г. 09:22
+ в цитатник
FasterHarder: В общем у меня ВРОДЕ получилось, но сделал я, конечно, не так, как мне тут подсказывали, т к в приведенных подсказках везде нужно было подниматься от потомка к родителю. Разумеется, алгоритм неоптимальный получился) + я вот далеко не уверен, что он работает корректно на всех конфигах ДДП
Просто находил ДЛЯ КАЖДОГО УЗЛА ДДП высоты левого и правого поддерева, суммировал их и проверял с максимальной. На рис., как я понимаю, длиннейший путь = 6, ну, прожка так и выдает.
Единственное, что мне не оч.нравится, что пришлось задействовать глобальную переменную, т е не чистая рекурсия получилась.
int maxP = 0;
int GMP(const TREE* root)
{
if(root != NULL)
{
LPK(root->left);
LPK(root->right);
int currentP = GH(root->left) + GH(root->right) - 1; // вот эта "-1" связана с логикой функции G(et)H(eight) + потомки не должны быть листьями оба одновременно, поэтому одного из потомка "поднимаем" на 1 уровень вверх, отбирая у пути одну единицу движения
if(currentP > maxP)
maxP = currentP;
return maxP;
}
else
return 0;
}
зы: когда ДДП-ЛОС, то в пути теряется 1, печалька) Хотя тут может проблема не только в этом...
https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842716
-
Запись понравилась
-
0
Процитировали
-
0
Сохранили
-
