gistfile1.txt

mod! EXCUARBORI{ ** exercitii cu arbori oarecare

extending (NAT)

[Nat < Lista , Arbore < Listarb]

op nil : -> Arbore ** arborele vid
op _{_} : Nat Listarb -> Arbore {prec 20} ** radacina si lista subarborilor
op frunza : -> Listarb ** lista de arbori vida
op _,_ : Listarb Listarb -> Listarb {assoc id: frunza prec 30}
op null : -> Lista ** lista de numere naturale vida
op __ : Lista Lista -> Lista {assoc id: null}
op bfds : Arbore -> Lista ** parcurgerea pe niveluri de la dreapta la stanga
op bflds : Listarb Lista -> Lista ** operatia ajutatoare pentru bfds, care, ca si bfl din
** modulul ARBOREBF din lectia3_1011.doc, simuleaza o coada, dar aici coada va
** ”merge” invers, adica de la dreapta la stanga listei de arbori prin care va fi
** reprezentata
op lf : Arbore -> Lista ** lista frunzelor
op listalf : Listarb -> Lista ** lista frunzelor unei liste de arbori
op h : Arbore -> Nat ** inaltimea
op listah : Listarb -> Lista ** transforma o lista de arbori in lista inaltimilor lor
op max : Nat Nat -> Nat
op maxlist : Lista -> Nat

op ex : -> Arbore

vars X Y : Nat
var L : Lista
var A : Arbore
vars La La1 : Listarb

eq bflds(nil,L) = L .
eq bflds(frunza,L) = L .
eq bflds((La, X{La1}),L) = bflds((La1,La),L X) .
** ca si in cazul operatiei bfl din modulul ARBOREBF din lectia3_1011.doc, mai
** exista cazul in care coada de arbori este nevida si are ca prim element arborele vid,
** care aici s-ar putea trata prin ecuatia:
** eq bflds((La,nil),L) = bflds(La,L) .
** iar, in cazul operatiei bfl din modulul ARBOREBF, prin ecuatia:
** eq bfl((nil,La),L) = bfl(La,L) .
** acest caz nu a fost tratat pentru ca nu poate aparea intr-o recurenta care porneste de
** la un arbore nevid, iar cazul arborelui vid a fost tratat prin prima ecuatie; aceasta 
** operatie fiind auxiliara, servind unicului scop de a face posibila implementarea lui
** bfds si nu scopului de a fi chemata in reduceri date la prompter, este de inteles ca
** tratarea in ecuatiile care o definesc a celui de-al patrulea caz, mentionat mai sus,
** este inutila   

eq bfds(A) = bflds(A,null) .

eq lf(nil) = null .
eq lf(X{frunza}) = X .
eq lf(X{A,La}) = lf(A) listalf(La) .

eq listalf(frunza) = null .
eq listalf(A,La) = lf(A) listalf(La) .

ceq max(X,Y) = X if X >= Y .
ceq max(X,Y) = Y if X < Y .

eq maxlist(null) = 0 .
eq maxlist(X L) = max(X,maxlist(L)) .

eq h(nil) = 0 .
eq h(X{La}) = s(maxlist(listah(La))) .

eq listah(frunza) = null .
eq listah(A,La) = h(A) listah(La) .

eq ex = 1{2{3{frunza},4{frunza}},5{6{frunza}},7{frunza}} .
}