Parcurgerea arborilor binari
<![CDATA[
/*****************************************
* Parcurgerea arborilor binari:
* - in preordine
* - in inordine
* - in postordine
* - pe nivele succesive (breadth-first)
*
* Predicatele se pot testa cu:
*
* preordine(arbore, L)
* inordine(arbore, L)
* postordine(arbore, L)
* bf(arbore, L)
*
* Paul Mateescu, grupa 309-Informatica, an III-ZI, 2009.
* Facultatea de Matematica si Informatica, Universitatea Spiru Haret Bucuresti.
******************************************/
CONSTANTS
% arbore de test
arbore = t( t( t(nil, 4, nil), 2, t( t(nil, 8, nil), 5, t(nil, 9, nil)) ), 1, t( t(nil, 6, nil), 3, t( t(nil, 10, nil), 7, t(nil, 11, nil))) )
DOMAINS
tree = t(tree, real, tree); nil % structura arborescenta
lr = real* % lista de reali
ltree = tree* % lista de noduri din arbore
i = integer
r = real
PREDICATES
% Parcurgerea unui arbore in preordine:
preordine(tree, lr) % interfata cu utilizatorul
preordine(tree, lr, lr) % parcurgerea propriu-zisa
% Parcurgerea unui arbore in inordine:
inordine(tree, lr) % interfata cu utilizatorul
inordine(tree, lr, lr) % parcurgerea propriu-zisa
% Parcurgerea unui arbore in postordine:
postordine(tree, lr) % interfata cu utilizatorul
postordine(tree, lr, lr) % parcurgerea propriu-zisa
% Parcurgerea pe nivele (breadth-first):
bf(tree, lr) % interfata cu utilizatorul
bf(ltree, ltree, ltree, lr) % parcurgerea propriu-zisa
CLAUSES
/***************************************************************/
% Interfata cu utilizatorul pentru parcurgerea in preordine:
% (i, o)
% Notand preordine(A, LISTA), semnificatia argumentelor este:
% A - arborele de parcurs
% L - lista rezultata prin parcurgerea arborelui in preordine
% Cheama predicatul care realizeaza parcurgerea propriu-zisa:
preordine(A, LISTA) :- preordine(A, LISTA, []).
/***************************************************************/
% parcurgerea propriu-zisa in preordine a unui arbore
% (i, o, o)
% Notand preordine(NC, ECL, ECNU), semnificatia argumentelor este:
% NC - nodul curent al arborelui de parcurs
% ECL - elementul curent al listei cerute corespunzator nodului in care ne aflam
% ECNU - elementul curent al listei corespunzator nodului urmator in parcurgere
/* Ideea care sta la baza acestui predicat este de a parcurge arborele in ordinea dorita,
si la vizitarea fiecarui nod se adauga eticheta in lista rezultat, daca este cazul.
Abordarea evita concatenarile si parcurgerile multiple.
*/
% daca am ajuns la un nod nil, nu se adauga nimic la lista dorita si se continua din acelasi punct:
preordine(nil, X, X) :- !.
% suntem intr-un nod oarecare al arborelui, adaugam eticheta sa la lista si continuam recursiv:
preordine(t(L, X, R), [X|T], REST) :-
!,
preordine(L, T, REST1),
!,
preordine(R, REST1, REST).
/***************************************************************/
% Interfata cu utilizatorul pentru parcurgerea in inordine:
% (i, o)
% Notand inordine(A, LISTA), semnificatia argumentelor este:
% A - arborele de parcurs
% L - lista rezultata prin parcurgerea arborelui in inordine
/* Am aplicat aceeasi abordare cu parcurgerea in preordine */
% Cheama predicatul care realizeaza parcurgerea propriu-zisa:
inordine(A, LISTA) :- inordine(A, LISTA, []).
/***************************************************************/
% parcurgerea propriu-zisa in inordine a unui arbore
% (i, o, o)
% Notand inordine(NC, ECL, ECNU), semnificatia argumentelor este:
% NC - nodul curent al arborelui de parcurs
% ECL - elementul curent al listei cerute corespunzator nodului in care ne aflam
% ECNU - elementul curent al listei corespunzator nodului urmator in parcurgere
% daca am ajuns la un nod nil, nu se adauga nimic la lista dorita si se continua din acelasi punct:
inordine(nil, X, X) :- !.
% suntem intr-un nod oarecare al arborelui, adaugam eticheta sa la lista si continuam recursiv:
inordine(t(L, X, R), LISTA, REST) :-
!,
inordine(L, LISTA, [X|REST1]),
!,
inordine(R, REST1, REST).
/***************************************************************/
% Interfata cu utilizatorul pentru parcurgerea in postordine:
% (i, o)
% Notand postordine(A, LISTA), semnificatia argumentelor este:
% A - arborele de parcurs
% L - lista rezultata prin parcurgerea arborelui in postordine
/* Am aplicat aceeasi abordare cu parcurgerea in preordine */
% Cheama predicatul care realizeaza parcurgerea propriu-zisa:
postordine(A, LISTA) :- postordine(A, LISTA, []).
/***************************************************************/
% parcurgerea propriu-zisa in postordine a unui arbore
% (i, o, o)
% Notand postordine(NC, ECL, ECNU), semnificatia argumentelor este:
% NC - nodul curent al arborelui de parcurs
% ECL - elementul curent al listei cerute corespunzator nodului in care ne aflam
% ECNU - elementul curent al listei corespunzator nodului urmator in parcurgere
% daca am ajuns la un nod nil, nu se adauga nimic la lista dorita si se continua din acelasi punct:
postordine(nil, X, X) :- !.
% suntem intr-un nod oarecare al arborelui, adaugam eticheta sa la lista si continuam recursiv:
% forma urmatoare, mai intuitiva, a predicatului este refuzata de catre compilator, de aceea
% am fost nevoit sa folosesc variabila VAR:
/*************
postordine(t(L, X, R), LISTA, REST) :-
!,
postordine(L, LISTA, REST1),
!,
postordine(R, REST1, [X|REST]).
*************/
postordine(t(L, X, R), LISTA, REST) :-
!,
postordine(L, LISTA, REST1),
!,
VAR = [X|REST],
postordine(R, REST1, VAR).
/***************************************************************/
% Interfata cu utilizatorul pentru parcurgerea pe nivele (breadth-first):
% (i, o)
% Notand bf(A, LISTA), semnificatia argumentelor este:
% A - arborele de parcurs
% L - lista rezultata prin parcurgerea arborelui pe nivele
% pentru un arbore vid, parcurgerea rezulta in lista vida:
bf(nil, []) :- !.
% Cheama predicatul care realizeaza parcurgerea propriu-zisa:
bf(A, L) :- bf([A], CAP, CAP, L).
/***************************************************************/
% parcurgerea propriu-zisa pe nivele a unui arbore
% (i, o, o, o)
% Notand bf(CRTLNIVCRT, CAPLNIVURM, CRTLNIVURM, CRTLISTAREZ), semnificatia argumentelor este:
% CRTLNIVCRT - elementul curent al listei DE NODURI pe nivelul curent
% CAPLNIVURM - capul listei DE NODURI pe nivelul curent
% CRTLNIVURM - elementul curent al listei DE NODURI pe nivelul urmator
% CRTLISTAREZ - elementul curent al listei de etichete rezultate prin parcurgerea pe nivele
/* Ideea care sta la baza acestui predicat este de a parcurge lista de noduri pe
nivelul curent (incepand cu nivelul radacinii), construind simultan lista de noduri
pentru nivelul urmator si lista de etichete corespunzatoare parcurgerii pe nivele.
Ca si cele de mai sus, abordarea evita concatenarile si parcurgerile multiple.
*/
% Daca nodul curent este frunza, adauga-i eticheta la lista rezultat si continua cu
% restul nodurilor din nivelul curent:
bf([t(nil, R, nil)|REST], CAP, CRT, [R|URM]) :-
!,
bf(REST, CAP, CRT, URM).
% Daca nodul are doar un subarbore drept, adauga nodul-radacina al acestui subarbore la lista
% de noduri pentru nivelul urmator si adauga eticheta la lista rezultat, apoi continua cu
% restul nodurilor din nivelul curent:
bf([t(nil, R, D)|REST], CAP, [D|CRT], [R|URM]) :-
!,
bf(REST, CAP, CRT, URM).
% Daca nodul are doar un subarbore stang, adauga nodul-radacina al acestui subarbore la lista
% de noduri pentru nivelul urmator si adauga eticheta la lista rezultat, apoi continua cu
% restul nodurilor din nivelul curent:
bf([t(S, R, nil)|REST], CAP, [S|CRT], [R|URM]) :-
!,
bf(REST, CAP, CRT, URM).
% Daca nodul are si subarbore stang si subarbore stang, adauga nodurile-radacina ale
% acestor subarbori la lista de noduri pentru nivelul urmator si
% adauga eticheta la lista rezultat, apoi continua cu restul nodurilor din nivelul curent:
bf([t(S, R, D)|REST], CAP, [S, D|CRT], [R|URM]) :-
!,
bf(REST, CAP, CRT, URM).
% Daca am epuizat lista de noduri pentru nivelul curent dar nu am adaugat niciun nod la lista
% de noduri pentru nivelul urmator (capul listei de noduri pentru nivelul urmator a ramas
% o variabila libera), inseamna ca pe nivelul curent am avut de-a face doar cu frunze, deci
% parcurgerea pe nivele s-a incheiat si incheiem lista dorita de etichete cu lista vida:
bf([], CAP, _, []) :- free(CAP), !.
% Daca am epuizat lista de noduri pentru nivelul curent si am ajuns la aceasta clauza inseamna
% ca avem noduri si pentru nivelul urmator, deci inchidem lista de noduri pt nivelul urmator cu lista vida si
% reluam algoritmul cu lista de noduri pentru nivelul urmator:
bf([], CAP, [], URM) :-
!,
bf(CAP, CAPURM, CAPURM, URM).
]]>