бинарные деревья, не рекурсивная проверка на равенство Опции

[compiler]

Добрый день!
Вот есть такая задачка:

10. Создайте программой два числовых двоичных дерева. Опишите рекурсивно и нерекурсивно логическую функцию, входными параметрами которой являются два дерева, проверяющую на равенство эти деревья. В программе используйте подпрограммы.

рекурсивный вариант у меня получился такой:

function equal(const tree0, tree1 :TTree ):boolean;
{ pre-order }
begin
   if tree0 = tree1 then equal:=true else
      if (tree0 = nil) and (tree1 <> nil) then equal:=false else
	 if (tree1 = nil) and (tree0 <> nil) then equal:=false else
	    equal:=(( tree0^.data =  tree1^.data) and
		    equal(tree0^.left, tree1^.left) and
		    equal(tree0^.right, tree1^.right));
end; { equal }

, а вот нерекурсивную функцию как то не получается... поиском нашел похожую задачу ( Help Me! ) , но не понял код...
помогите пожалуйста...
в атаче моя программа целиком.
заранее благодарен.

Сообщение отредактировано: compiler - 1.06.2008 20:29

[volvo]

Во-первых, почему стек, а не очередь? Я ж говорил про обход в ширину...

А во-вторых, ну, кто ж тебя заставлял делать одни и те же действия 2 раза? Смотри:

Чуть-чуть меняем описание типа TTree (добавляем в него вариантные поля, чтоб можно было обращаться и по имени - Left/Right, и по индексу - where[False]/where[True]):

  TTree = ^element;
  element = record
    data: integer;
    case boolean of
      false: (left, right : TTree);
      { where[false] => left, where[true] => right }
      true: (where: array[boolean] of TTree);
  end;

, и теперь твоя функция сравнения элементарно переписывается вот так (функциональность полностью сохранена):

function q(const tree0, tree1: TTree): boolean;

var
  S0, S1 : LIFO;
  p0, p1 : TTree;

  function f(index: boolean): boolean;
  begin
    f := true;
    if (p0^.where[index] = nil) xor (p1^.where[index] = nil) then f := false
    else
      if (p0^.where[index] <> nil) and (p1^.where[index] <> nil) then
      begin
        push(S1, p1^.where[index]);  push(S0, p0^.where[index]);
      end;
  end;

var
  b: boolean;

begin
  b := true;
  stack.init(S0); p0:=tree0;
  stack.init(S1); p1:=tree1;

  push(S0, p0);
  push(S1, p1);

  while b and not(isEmpty(S1) and isEmpty(S0)) do begin
    p0 := pop(S0);
    p1 := pop(S1);

    if p0^.data = p1^.data then begin
      b := f(false); { left child }

      if b then
        b := f(true); { right child }
    end
    else b :=false;

  end;

  q := b and isEmpty(S1) and isEmpty(S0);
  stack.free(S0);
  stack.free(S1);
end;   { q }

При желании можно еще "ужать", но я бы не стал этого делать - читабельность ухудшится.

Сообщение отредактировано: volvo - 1.06.2008 20:57