1. Заголовок темы должен быть информативным. В противном случае тема удаляется ... 2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения. 3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали! 4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора). 5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM! 6. Одна тема - один вопрос (задача) 7.Проверяйте программы перед тем, как разместить их на форуме!!! 8.Спрашивайте и отвечайте четко и по существу!!!
бинарные деревья, не рекурсивная проверка на равенство
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! ) , но не понял код... помогите пожалуйста... в атаче моя программа целиком. заранее благодарен.
Во-первых, почему стек, а не очередь? Я ж говорил про обход в ширину...
А во-вторых, ну, кто ж тебя заставлял делать одни и те же действия 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 }
При желании можно еще "ужать", но я бы не стал этого делать - читабельность ухудшится.