Arbori binari

Reprezentare

Din breviar + Lab 5:

% tree(Rădăcină, Stânga, Dreapta)
% nil pentru arborele vid

% exemplu
def(myTree,
    tree(1,
         tree(2, tree(4, nil, tree(7, nil, nil)), nil),
         tree(3, tree(5, nil, nil), tree(6, nil, nil)))).

O frunză este un arbore de forma tree(X, nil, nil).

Parcurgeri

Cele trei parcurgeri clasice. 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)

In-ordine (srd)

srd(nil, []).
srd(tree(Root, Left, Right), Result) :-
    srd(Left, ResultLeft),
    srd(Right, ResultRight),
    append(ResultLeft, [Root | ResultRight], Result).

?- def(myTree, T), srd(T, R).
R = [4, 7, 2, 1, 5, 3, 6]

Pre-ordine (rsd)

rsd(nil, []).
rsd(tree(Root, Left, Right), Result) :-
    rsd(Left, ResultLeft),
    rsd(Right, ResultRight),
    append([Root | ResultLeft], ResultRight, Result).

Post-ordine (sdr)

sdr(nil, []).
sdr(tree(Root, Left, Right), Result) :-
    sdr(Left, ResultLeft),
    sdr(Right, ResultRight),
    append(ResultLeft, ResultRight, ResultWithoutRoot),
    append(ResultWithoutRoot, [Root], Result).

Pattern-ul comun

Toate trei au aceeași structură:

1. caz de bază: nil → lista vidă
2. caz recursiv: parcurge stânga, parcurge dreapta, combină cele două liste cu [Root] în poziția potrivită pentru ordinea dorită

Prioritate în parțial

Arborii binari nu apar în parțial (Labs 1-5 + model + șablon). Concept util pentru înțelegerea recursivității, dar prioritate scăzută față de findall, liste, calcul propozițional.