Дерево в зеркальном отражении Опции

[Jekaterina]

Доброго всем утра!
Попалась задача: дано дерево, в узлах которого записаны неповторяющиеся числа. Задача: вывести в выходной файл зеркальное отражение дерева. При этом во входном файле дерево может быть записано двумя способами:1)в каждой строчке содержится информация об узле, не являющемся листом (внутренним узлом); либо 2) в записи первое число есть номер внутреннего узла, за которым выписаны дети в порядке с левой стороны в правую. Если, напр.б дан граф, как в пиложенном рисунке, то во входном файле запись его может быть и
1 2 3 4 5
3 6 7
5 8
8 9 10 11
и
5 8
3 6 7
8 9 10 11
1 2 3 4 5
В выходном файле граф выводистя подобным образом, но при условии, что внутренние узлы в порядке preoder (т.е. запись о родителе предшествует записи о ребенке). Я нашла решение задачи на с++, но очень плохо знаю этот язык. Если у кого-то будет время и желание, помогите, пожалуйста, перевести на паскаль эту программу. Прилагаю также тесты: из 8 тестов корректо выполняются 6.
 PD4.cpp ( 4.64 килобайт ) Кол-во скачиваний: 931
 testiPD4.zip ( 2.69 килобайт ) Кол-во скачиваний: 412

[Jekaterina]

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

[Lapp]

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

Если подходить с позиций списков, то, боюсь, без указателей нельзя . Но это не единственный возможный подход. Использование списков помогает при решении подобных задач, но конкретно тут вполне можно обойтись. Более того, решение на основе обычных массивов тут мне показалось интересным и не вполне тривиальным..

Отражение действительно напоминает операции со строками, но лучше все же оперировать обычными числовыми массивами - отражение все равно делается в пару строчек.. Главная изюминка в этой задаче, имхо, как ни странно - это то дополнительное условие упорядоченности. Оно заняло у меня 90% времени написания проги (которое, кстати, оказалось больше, чем я полагал).

Оговорки:
1. Я сильно полагаюсь на корректность данных, которая в программе не проверяется. Если в данных ошибка (граф зациклен, например) - результат непредсказуем.
2. Я ничуть не заботился об экономии времени и ресурсов. Но это исправимо при желании

{Зеркальное отражение графа с упорядочиванием}
{for jekaterina by Lapp}
{Jan 3, 2007}
const
  Nx=200;
  Mx=200;

type
  tBranch=record
    Dad,Num:integer;
    Kid:array[1..Mx]of integer
  end;

var
  n,i,j,k,r,Top:integer;
  a,c:array[1..Nx]of tBranch;
  b:tBranch;
  f:text;
  Flag:boolean;

procedure Add(p:integer);
var
  i,j:integer;
begin
  Inc®;
  c[r]:=a[p];
  with a[p] do for i:=1 to Num do for j:=1 to n-1 do if Kid[i]=a[j].Dad then Add(j)
end;


begin
  Assign(f,'test-i.txt');
  ReSet(f);
  n:=0;
  repeat
    Inc(n);
    with a[n] do begin
      Read(f,Dad);
      i:=0;
      while not EoLn(f) do begin
        Inc(i);
        Read(f,Kid[i])
      end;
      Num:=i
    end;
  until a[n].Dad=0;
  Close(f);

  {Отражение}
  for i:=1 to n-1 do begin
    b:=a[i];
    with a[i] do for j:=1 to Num do Kid[j]:=b.Kid[Num-j+1]
  end;

  {Упорядочивание от вершины}
  for i:=1 to n-1 do begin
    Flag:=false;
    for j:=1 to n-1 do with a[j] do
      for k:=1 to Num do Flag:=Flag or(Kid[k]=a[i].Dad);
    if not Flag then Top:=i
  end;
  Add(Top);    {рекурсивное добавление строк в упорядоченный массив}
  a:=c;

  Assign(f,'test-o.txt');
  ReWrite(f);
  for i:=1 to n do with a[i] do begin
    Write(f,Dad);
    for j:=1 to Num do begin
      Write(f,' ');
      Write(f,Kid[j])
    end;
    WriteLn(f)
  end;
  Close(f)
end.

PS
1. удалил лишний кусок кода уже после отправки; извиняюсь.
2. Добавил ReWrite(f) (замечено volvo, thnx)

Сообщение отредактировано: Lapp - 4.01.2007 14:17