Re: Лазанье по деревьям

From

Andrey Tarasevich ()

To

Alexander Kazak

Date

2002-06-08T10:07:28Z

Area

RU.ALGORITHMS

From: Andrey Tarasevich <atarasevich@telocity.com>

Alexander Kazak wrote:
> ...
> Люди, подскажите плс чайнику, как решить следующую задачку.
> Как известно, кратчайший путь между двумя вершинами произвольного графа
> находится по алгоритму Дейкстры. Но, если этот граф есть отбинаренное
> дерево, то путь-то всего один; веса рёбер в этом случае не имеют
> никакого значения. Как бы побыстрее и поэффективнее найти этот путь?
> Неужели без Дейкстры не обойтись?
> ...

Не нужен тут никакой Дийкстра. Если в твоем дереве есть выделенная
корневая вершина R (а она у тебя, по-видимому, есть, раз ты называешь
свое дерево бинарным), то в каждой паре соседних вершин одна вершина
является предком (та, что ближе к корню), а другая - потомком (та, что
дальше от корня). 

Если в исходной структуре данных, представляющей твое дерево, есть
ссылки от потомков к предкам, то построить путь от вершины A к вершине B
несложно - надо просто строить пути, двигаясь из обоих вершин по ссылкам
к предкам до тех пор пока эти пути не сойдутся в некоторой вершине C
(они могут сойтись в корне, а могут сойтись и раньше). Путь A - ... - C
- ... - B и есть искомый путь.

Если же ссылок от потомков к предка в структуре данных нет, то придется
делать поиск путей к вершинам A и B из корневой вершины R. Если вершины
обладают ключами и дерево упорядочено, то поиск может быть
целенапрваленным. В противном случае придется делать обход дерева. Два
найденных пути будут сходиться в некоторой вершине C и т.д. (см. выше)

Есть и другие варианты. Все во многом зависит от конкретной струкуры
данных, представляющей дерево. Как оно у тебя представлено?

Best regards,
Андрей.
--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)