Дерево

← →
_Oleg © (2002-05-28 21:27) [0]

Наверное, это очень просто. Но что-то сразу не сообразить не получается.
Есть дерево. Вершины нумеруются так:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
...
Надо найти фунцию f=f(i,j) , которая определяет расстояние между вершинами i и j. Расстояние определяется количеством ребер, которые надо пройти, чтобы попасть из i-й вершины в j-ю.
Может, кто-нибудь подскажет?
Заранее спасибо за ответы.

← →
AlexMey © (2002-05-28 23:28) [1]

Если Вам необходимо найти расстояние между двумя вершинами внутри одной ветви - то всё, конечно, просто(Например 3 - 15). Но если элементы могут быть в разных ветвях (7 - 9), то Я бы не сказал, что "это очень просто". И нумерация здесь не при чём.
Это можно решить так...

Любая древовидная структура - это частный случай неориентированного графа. Про графы Вы можете почитать здесь - http://book.itep.ru/10/grap1021.htm ( нашёл специально для Вас).
Так вот, существует уже дано разработанный (помоему в 60-х годах) алгоритм, позволяющий найти оптимальное растояние от одной вершины графа до другой, (понятно, что в Вашем случае расстояние будет только одно). не, помнится, его в институте давали. Он работает через "Матрицу смежности графа" - про неё Вы можете прочитать по указанному URL. Если Вам интересно - дайте знать, а то я уже устал писать :-(

С уважением, Александр.

← →
Владислав © (2002-05-29 06:23) [2]

Почитай здесь:
http://sdm.viptop.ru/articles/sqltrees.html

← →
MBo © (2002-05-29 06:56) [3]

function dist(i,j:integer):integer;
var leveldiff:integer;
begin
if i=j then begin
result:=0;
exit;
end;
// trunc(log2(i))- фактически номер старшего ненулевого бита
leveldiff:=trunc(log2(i))-trunc(log2(j));
if leveldiff>0 then i:=i shr leveldiff;
if leveldiff<0 then j:=j shr (-leveldiff);
result:=abs(leveldiff);
while i<>j do begin
i:=i shr 1;
j:=j shr 1;
result:=result+2;
end;
end;

>AlexMey © (28.05.02 23:28)
Спасибо, но поиск пути в графах (например, метод Дейкстры или "фронт волны") работает слишком долго.

>MBo © (29.05.02 06:56)
А вот это действительно то, что нужно. Большое спасибо!
P.S. Сразу видно "мастера" :)

>Oleg
первый if в принципе и не нужен

Дерево Найти похожие ветки