Игорь Пашев - March 2nd, 2011

Mar. 2nd, 2011

06:31 pm - Поиск общего предка в двоичном дереве

Даны два элемента дерева, надо найти их ближайшего общего предка.

Решение такое. Начинаем с корня.
Если один слева, а другой справа — предок найден (корень).
Если слева никого — идём рекурсивно направо.
Если справа никого — идёи рекурсивно налево.

Если оба элемента на одной ветви, то этот алгоритм не работает.
Ну и фиг с ним, ибо тогда один из элементов является предком другого.

Код на Си и пример с картинкой )

Tags: ,
(1 комментарий | Оставить комментарий)
Previous day (Calendar) Next day