7/22/2019 aplicatie arbori Prolog

http://slidepdf.com/reader/full/aplicatie-arbori-prolog 1/3

%% Pentru a porni aceasta aplicatie, efectuati urmatoarele operatii:%%%% 1) Porniti swipl%%%% > swipl%%%% 2) Incarcati acest fisier sursa:%%%% > [arbori]%%%% 3) Apelati%%%% ?- meniu(nil).%%

%% Arbori binari%% Un arbore binar este o structura definita recursiv astfel:%% Arb ::= nil % arborele vid%% | arb(C, D, Arb1, Arb2) % arbore a carui radacina are%% % cheia C asociata cu datele D%% % iar Arb1 este subarborele stang%% % si Arb2 este subarborele drept%% unde C este intreg iar D este un simbol.%% Se presupune ca nodurile arborelui au chei diferite si ca pentru fiecare nod

cu cheia C:%% cheile din subarborele stang sunt mai mici decat C%% cheile din subarborele drept sunt mai mari decat C/* preordine(A) afiseaza continutul arborelui A prin traversare in preordine. inordine(A) afiseaza continutul arborelui A prin traversare in inordine. postordine(A) afiseaza continutul arborelui A prin traversare in postordine.

 Pentru fiecare nod din A se afiseaza pe o linie noua sirul "C D" undeC este cheia nodului

  D sunt datele asociate cu cheia respectiva.*/

preordine(nil).preordine(arb(C,D,Stanga,Dreapta)):-  write(C), write(' '), writeln(D), % se afiseaza continutul nodului vizitat  preordine(Stanga), % se traverseaza subarborele stang  preordine(Dreapta). % se traverseaza subarborele drept.

inordine(nil).inordine(arb(C,D,Stanga,Dreapta)):-  inordine(Stanga), % se traverseaza mai intai subarborele stang  write(C), write(' '), writeln(D), % se afiseaza continutul nodului vizitat  inordine(Dreapta). % se traverseaza subarborele drept.

postordine(nil).

postordine(arb(C,D,Stanga,Dreapta)):-  postordine(Stanga), % se traverseaza subarborele stang  postordine(Dreapta), % se traverseaza subarborele drept.  write(C), write(' '), writeln(D). % se afiseaza continutul nodului vizitat

/* caut(+C,+A,-D) ia ca argumente de intrare o cheie C si un arbore binar A si incearca sa gaseasca nodul lui A care are cheia C.Daca un astfel de nod este gasit, D este instantiat cu sirul de date din nodulgasit.

7/22/2019 aplicatie arbori Prolog

http://slidepdf.com/reader/full/aplicatie-arbori-prolog 2/3

 Daca nici un nod nu are cheia C, apelul caut(C,A,D) esueaza.*/

caut(C,arb(C,D,_,_),D) :- !. % cazul de baza: a fost gasit nodul cu cheia C% --> al doilea argument se instantiaza cu datel

e din nodul gasit.caut(C,arb(R,_,Stanga,_),D) :- % cazul recursiv cand caut in subarborele stang

C < R, !,caut(C,Stanga,D).

caut(C,arb(_,_,_,Dreapta),D) :- % cazul recursiv cand caut in subarborele drept.  caut(C,Dreapta,D).

/* inserez(+C,+D,+A,-B), - are loc daca B este arborele binar de cautare obtinut prin inserareain arborele binar de cautare A a unui nod cu cheia C si datele D.*/

inserez(C,D, nil, arb(C,D,nil,nil)):-!.inserez(C,D,arb(C1,D1,L,R),arb(C1,D1,L1,R)):-  C<C1,!,  inserez(C,D,L,L1).inserez(C,D,arb(C1,D1,L,R),arb(C1,D1,L,R1)):-  inserez(C,D,R,R1).

/* elim(+C,+A,-B) are loc daca B este arborele binar de cautare obtinut prin stergerea nodului cucheia C din arborele A.

 Acest predicat utilizeaza predicatul auxiliar

drept(+A,-C,-D,-L)

care cauta cel mai din dreapta subarbore al lui A care nu are subarbore drept.OBSERVATII:

1) Arbore gasit este de forma arb(C,D,L,nil)

  2) C este cheia cea mai mare din arborele A.*/

elim(C,arb(C,_,nil,nil),nil):-!. % cazul de baza 1:% stergerea radacinii dintr-un arbore cu

 un singur nod

elim(C,arb(C,_,L,nil),L):-!. % cazul de baza 2:  % stergerea radacinii dintr-un arbore fara subarbore drept

elim(C,arb(C,_,nil,R),R):-!. % cazul de baza 3:  % stergerea radacinii dintr-un arbore fa

ra subarbore stang

elim(C,arb(C,_,L,R),arb(C1,D,L1,R)):- % cazul de baza 4  !,drept(L,C1,D,L1).

elim(C,arb(C1,D,L,R), arb(C1,D,L1,R)):- % caz recursiv 1: eliminare din subarborele stang L  C<C1,!,  elim(C,L,L1).

7/22/2019 aplicatie arbori Prolog

http://slidepdf.com/reader/full/aplicatie-arbori-prolog 3/3

elim(C,arb(C1,D,L,R), arb(C1,D,L,R1)):- % caz recursiv 2: eliminare din subarborele drept R  elim(C,R,R1).

drept(arb(C,D,L,nil),C,D,L):-!. % cazul de bazadrept(arb(C1,D,L,R),C,D1,arb(C1,D,L,R1)):- % cazul recursiv  drept(R,C,D1,R1).

/*  creare(+A,-B) este un predicat auxiliar pentru inserarea repetata de noduri in arborelebinar de cautare A.B este instantiat cu arborele nou obtinut.

*/creare(A,B):-

write('Introduceti o cheie cu punct la sfarsit (0. pentru terminare): '),read(C),C\= 0,!,

  write('Introduceti datele cu punct la sfarsit: '),read(D),  inserez(C,D,A,A1), creare(A1,B).creare(A,A).

/* Meniul aplicatiei

*/meniu(Arb):-nl,  writeln('1. Sfarsit'),  writeln('2. Creeaza arbore'),  writeln('3. Cauta nod'),  writeln('4. Insereaza nod'),  writeln('5. Sterge nod'),

writeln('6. Afiseaza arbore in preordine'),  writeln('7. Afiseaza arbore in inordine'),  writeln('8. Afiseaza arbore in postordine'),nl,  writeln('Selecteaza numar optiune cu punct la sfarsit: '),  read(Opt),

Opt \= 1,

  actiune(Opt,Arb,ArbNou),!,  meniu(ArbNou).meniu(_):- writeln('Sfarsit').

/* Actiunile aplicatiei*/actiune(2,A,B):-creare(A,B).actiune(3,A,A):- write('Introduceti cheia cu punct la sfarsit: '),

read(C), caut(C,A,D),write('Datele asociate sunt: '), write(D),nl.

actiune(3,_,_):-write('Cheia nu a fost gasita'),nl.actiune(4,A,B):- write('Introduceti cheia cu punct la sfarsit: '),

read(C),write('Introduceti datele asociate cu punct la sfarsit: '),  read(D),inserez(C,D,A,B).actiune(5,A,B):-write('Introduceti cheia cu punct la sfarsit: '),

read(C),elim(C,A,B).actiune(6,A,A):-preordine(A).actiune(7,A,A):-inordine(A).actiune(8,A,A):-postordine(A).actiune(X,A,A):-write(X),  write(' nu este o comanda valida. Reincearca.').