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

[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]

А имеет ли смысл проверять проверять не совпадют ли у них адреса?

Хм... Ну, во-первых, адреса-то совпадать и не будут, ты ж идешь не по одному и тому же дереву, а по разным, созданным по-отдельности.

Я уж не говорю ничего о том, что наверняка сравнивать значения указателей можно только с нулем, но никак не друг с другом (я про Турбо Паскаль, мы вроде в его разделе)...

[compiler]

Я уж не говорю ничего о том, что наверняка сравнивать значения указателей можно только с нулем, но никак не друг с другом (я про Турбо Паскаль, мы вроде в его разделе)...

упс.. осечка вышла.. прошу прощения..

Что-то написал, но как-то коряво оно все..

function q(const tree0, tree1 : TTree ):boolean;
var
   S0, S1 : LIFO;
   p0, p1 : TTree;
   b	  : boolean;
begin
   b:=true;
   
   stack.init(S0);
   stack.init(S1);
   
   p0:=tree0;
   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   
	 if ((p0^.left = nil) xor  (p1^.left = nil)) then b:=false else
	    if (p0^.left <> nil) and  (p1^.left <> nil) then begin
		  push(S1, p1^.left);  push(S0, p0^.left);
	       end;
	 
	 if b then if   ((p0^.right = nil) xor  (p1^.right = nil)) then b:=false else
	    if (p0^.right <> nil) and  (p1^.right <> nil)then  begin
		  push(S1, p1^.right);  push(S0, p0^.right);
	       end;	    
      end else b:=false;
   end;
   q:=b and isEmpty(S1) and isEmpty(S0);
   stack.free(S0);
   stack.free(S1);
end;   { q }

вроде какие-то тесты проходит... но наверняка можно лучше....
в атаче вся программа(main.pas) и модуль(stack.pas), они реализованны еще хуже, так как писались для тестирования этой функции...

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