(* -----------------------------------------------------------------------------
Модуль описания класса деревьев
Каждый элемент дерева содержит:
• Ссылку на родителя (равно NIL - если элемент является корневым)
• Массив ссылок на детей
• Индекс - уникальный номер от корневого элемента до каждого младшего сына дерева
• Возраст - некое значение, определяемое элемента до его родителя

В данной задаче Возраст используется как расстояние от одного города до другого. 
----------------------------------------------------------------------------- *)

unit BinaryTrees;

interface

type
  TIntArray = Array of Integer;       // Одномерный массив целых чисел
  TIntMatrix = Array of TIntArray;    // Двумерный массив целых чисел

  // Класс дерева //
  TBinaryTree = class
    Index: Integer;
    Child: Array of TBinaryTree;
    Parent: TBinaryTree;
    LengthToParent: Integer;

    constructor Create(AIndex, ALengthToParent: Integer; AParent: TBinaryTree);
    destructor Destroy;
    function FindParent(AIndex: Integer): Boolean;
    function GetRoot: TBinaryTree;
    procedure AddChild(AChild: TBinaryTree);
    function LengthToChild(AIndex: Integer): Integer;
    function PathToChild(AIndex: Integer): TIntArray;
    function FindChild(AIndex: Integer): TBinaryTree;
  end;

implementation

constructor TBinaryTree.Create;
begin
  Index:=AIndex;
  LengthToParent:=ALengthToParent;
  Parent:=AParent;
  if(Parent<>nil)then
    Parent.AddChild(Self);
  SetLength(Child, 0);
end;

destructor TBinaryTree.Destroy;
var
  I: Integer;
begin
  For I:=Low(Child)to High(Child)do
    if(Child[I]<>nil)then
      Child[I].Destroy;
end;

function TBinaryTree.FindParent;
begin
  Result:=(Index = AIndex);
  if(Result)then Exit;

  if(Parent<>nil)then
    Result:=Parent.FindParent(AIndex);
end;

function TBinaryTree.GetRoot;
begin
  if(Parent=nil)then
    Result:=Self
      else
    Result:=Parent.GetRoot;
end;

procedure TBinaryTree.AddChild;
begin
  SetLength(Child, High(Child)+2);
  Child[ High(Child) ]:=AChild;
  Child[ High(Child) ].Parent:=Self;
end;

function TBinaryTree.LengthToChild;
begin
end;

function TBinaryTree.PathToChild;
var
  I, J,
  MinLen,
  FindLen: Integer;
  FindPath: TIntArray;
  FChild: TBinaryTree;
begin
  MinLen:=0;
  SetLength(Result, 0);

  if(Index=AIndex)then
    begin
      SetLength(Result, 1);
      Result[0]:=Index;
      Exit;
    end
      else

  for I:=Low(Child)to High(Child)do
    begin
      FindPath:=Child[I].PathToChild(AIndex);
      FindLen:=0;
      FChild:=Self;
      for J:=High(FindPath)downto Low(FindPath)do
        begin
          FChild:=FChild.FindChild(FindPath[J]);
          FindLen:=FindLen+FChild.LengthToParent;
        end;
      if(FindLen>0)then
        if(MinLen=0)or(FindLen<MinLen)then
          begin
            MinLen:=FindLen;
            Result:=FindPath;
          end;
    end;

  if(MinLen>0)then
    begin
      SetLength(Result, High(Result)+2 );
      Result[ High(Result) ]:=Index;
    end;
end;

function TBinaryTree.FindChild;
var
  I: Integer;
begin
  Result:=nil;
  For I:=Low(Child)to High(Child)do
    if(Child[I].Index=AIndex)then
      Result:=Child[I];
end;

end.