Поиск пути в бинарном дереве

[FasterHarder]

Всем хай! Сходу к делу!

Есть такая структура, описывающая узел ДДП:

структура "Узел дерева"
  ключ (целое)
  ссылка на левое
  ссылка на правое

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

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

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

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

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

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

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

[Akina]

Навскидку рисуется такое.

Строим пути от корня ко всем листьям. Дополняем каждый узел его уровнем и, возможно, полным путём. Если что лишнее - потом при оптимизации удалится. Идём обратно. Для каждого не-листа имеем 1 или 2 потомка. У каждого потомка имеется свой текущий максимальный путь. Соответственно получаем два значения - максимальный путь от текущего узла до дальнего листа (тот самый текущий максимальный путь) и длину пути через текущий узел до дальних листьев. Забираемся так по дереву до корня. В результате получаем массив максимальных путей, откуда берём самый-самый максимум. Всё.

[FasterHarder]

Цитата Akina @ 24.11.21, 05:01

Всё

)

а неужели нельзя обойтись высотами левого и правого поддерева для текущего узла...
если получить ДЛЯ каждого узла исходного ДДП высоту левого и правого поддерева. Разве MAX(left(h) + right(h)) не будут показывать узел, который является точкой перелома макс.пути? Ведь если знать корень поддерева, через который проходит макс.путь, то дальше вроде уже легко становится (вроде!)

[Akina]

Цитата FasterHarder @ 24.11.21, 10:42

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

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

То, что ты говоришь - это в моём описании обратный ход.

Сообщение отредактировано: Akina - 24.11.21, 13:32

[FasterHarder]

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]

Цитата FasterHarder @ 23.11.21, 19:37

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

Вместо диванных ЭКСПЕРТОВ(!) читайте Кнута.

[Akina]

FasterHarder
Ну всё так.
Как я понимаю, у тебя вся проблема - это как именно сделать алгоритмически, верно? Я бы делал так.

Добавляем каждому узлу свойство "уровень". У корня - 1, у его дочек - 2, и так далее. Заполняем поиском в ширину или в глубину - как захочешь. Добавляем каждому узлу свойство "длина". Обрабатываем полученный список поиском "из глубины к поверхности" (т.е. начинаем с макс. глубины, и в порядке уменьшения послойно). Для узла "длина" = 1 + макс("длина правого", "длина левого"), при отсутствии потомка справа и/или слева считаем его длину за ноль. Также считаем "текущий максимум" = 1 + "длина левого" + "длина правого" и сравниваем его с текущим глобальным (который изначально нулевой), если больше - запоминаем новое значение. Когда дойдём до корня и обработаем его - выводим полученный глобальный "текущий максимум".

[FasterHarder]

В общем у меня вроде(!) все получилось, правда такое чувство, что все это дело можно кодировать гораздо точнее и оптимальнее.
Вот главная функция, которая находит узел, через которую пройдет макс.путь удовлетворяющий условиям:

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, Кнута я бы читал с большим удовольствием, если бы не одно НО...

[scrambrella]

Цитата FasterHarder @ 26.11.21, 18:58

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

Лень матушка - единственное но, по которому никто не читает Кнута. Чтение Кнута требует ЗНАЧИТЕЛЬНЫХ умственных усилий, а люди стремятся экономить мышление.

[FasterHarder]

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

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

[scrambrella]

Цитата FasterHarder @ 28.11.21, 21:39

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

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

Даже пропуская тексты программ можно кое-что понять. Математика в Кнуте относительно понятная, часть алгоритмов с поясняющими картинками. Собственный ЯП Кнута раздражает. Сам его пока не освоил. Как он сам пишет - это что-то близкое к ассемблеру.