Добрый день!
Вот есть такая задачка:
function equal(const tree0, tree1 :TTree ):boolean;, а вот нерекурсивную функцию как то не получается... поиском нашел похожую задачу ( http://forum.pascal.net.ru/index.php?showtopic=20157&hl= ) , но не понял код...
{ 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 }
Вот тут есть алгоритм нерекурсивного обхода в ширину: http://pco.iis.nsk.su/ICP/Practice/dd8-3/node6.html (с использованием очереди)... Дальше справишься?
Сравни: http://forum.pascal.net.ru/index.php?s=&showtopic=4375&view=findpost&p=37418
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 }
Во-первых, почему стек, а не очередь? Я ж говорил про обход в ширину...
А во-вторых, ну, кто ж тебя заставлял делать одни и те же действия 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 }
function equal(const tree0, tree1: TTree): boolean;
var
p0, p1 : TTree;
q0, q1: tqueue;
begin
equal := false;
queue.init(q0); put(q0, tree0);
queue.init(q1); put(q1, tree1);
while not is_empty(q0) do begin
p0 := get(q0); put(q0, p0^.left); put(q0, p0^.right);
if is_empty(q1) then exit;
p1 := get(q1); put(q1, p1^.left); put(q1, p1^.right);
if p0^.data <> p1^.data then exit;
end;
equal := is_empty(q1);
done(q0); done(q1);
end;
Попробуй здесь: http://volvo71.narod.ru/faq_folder/records.htm
Kamagra Jelly Manufacturers
Pharmacy Canadian