Arbori binari — parcurgeri
Considerăm predicatele tree/3 pentru reprezentarea arborilor binari, respectiv nil/0 pentru reprezentarea arborelui vid. De exemplu, tree(Anything, nil, nil) este o frunză.
Implementați:
- Cele trei tipuri de parcurgeri ale arborilor binari (in-ordine, pre-ordine, post-ordine).
- Scrieți un predicat care să determine toate frunzele din arbore.
Convenția din materiale:
srd— stânga-rădăcină-dreapta (in-ordine)rsd— rădăcină-stânga-dreapta (pre-ordine)sdr— stânga-dreapta-rădăcină (post-ordine)
Testați scriind:
?- def(myTree, Tree), srd(Tree, Result).
și schimbați srd cu rsd și sdr.
Te-ai blocat?
editor
soluție
def(myTree,
tree(1,
tree(2, tree(4, nil, tree(7, nil, nil)), nil),
tree(3, tree(5, nil, nil), tree(6, nil, nil)))).
% inordine
srd(nil, []).
srd(tree(Root, Left, Right), Result) :-
srd(Left, ResultLeft),
srd(Right, ResultRight),
append(ResultLeft, [Root | ResultRight], Result).
% preordine
rsd(nil, []).
rsd(tree(Root, Left, Right), Result) :-
rsd(Left, ResultLeft),
rsd(Right, ResultRight),
append([Root | ResultLeft], ResultRight, Result).
% postordine
sdr(nil, []).
sdr(tree(Root, Left, Right), Result) :-
sdr(Left, ResultLeft),
sdr(Right, ResultRight),
append(ResultLeft, ResultRight, ResultWithoutRoot),
append(ResultWithoutRoot, [Root], Result).
?-
Tastează o interogare (ex. father_of(sandra, X).) și apasă Enter — sau apasă pe un caz de test de mai jos.
Cazuri de test (3 — apasă pe unul ca să îl rulezi, sau Verifică pentru toate)
?
def(myTree, T), srd(T, R).
așteptat: T = tree(1,tree(2,tree(4,nil,tree(7,nil,nil)),nil),tree(3,tree(5,nil,nil),tree(6,nil,nil))), R = [4,7,2,1,5,3,6]
?
def(myTree, T), rsd(T, R).
așteptat: T = tree(1,tree(2,tree(4,nil,tree(7,nil,nil)),nil),tree(3,tree(5,nil,nil),tree(6,nil,nil))), R = [1,2,4,7,3,5,6]
?
def(myTree, T), sdr(T, R).
așteptat: T = tree(1,tree(2,tree(4,nil,tree(7,nil,nil)),nil),tree(3,tree(5,nil,nil),tree(6,nil,nil))), R = [7,4,2,5,6,3,1]