Prolog - stromy
V Prologu lze pracovat i se složitějšími datovými strukturami. Např. s binárními stromy se pracuje tak, že si vytvoříme term t(LevySyn, Uzel, PravySyn), který reprezentuje uzel a jeho dva syny. Prázdný uzel můžeme reprezentovat jako nil (nil není žádné zvláštní klíčové slovo Prologu, je to jen nulární term, kdybychom použili třeba nic bude to fungovat úplně stejně).
Strom, který má kořen 1, a dva syny 2 a 3 se tedy dá zapsat jako t(t(nil,2,nil),1,t(nil,3,nil)). Když levého syna (2) nahradíme podstromem t(t(nil, 4, nil),2, t(nil,5, nil)) zapíšeme výsledek jako t(t(t(nil,4,nil),2,t(nil,5,nil)),1,t(nil,3,nil)).
Zkusme si v Prologu práci s binárními stromy. Nejjednodušší jsou asi průchody stromem. Začneme tedy s převedením stromu na seznam v inorder pořadí.
% inorderList(+T,-S) :- prevadi strom T na seznam S v inorder poradi
inorderList(nil,[]).
inorderList(t(X,Y,Z), S):-inorderList(X,S1),inorderList(Z,S2),append(S1,[Y|S2],S).
% preorder(+T,-S) :- prevadi strom T na seznam S v preorder poradi
preorderList(nil,[]).
preorderList(t(X,Y,Z), [Y|S]):-preorderList(X,S1),preorderList(Z,S2),append(S1,S2,S).
% postorder(+T,-S) :- prevadi strom T na seznam S v postorder poradi
postorderList(nil,[]).
postorderList(t(X,Y,Z), S):-postorderList(X,S1),postorderList(Z,S2),append(S1,S2,S3),append(S3,[Y],S).
Občas se místo seznamu prvků ze stromu hodí další prvek vracet při stisknuti ; (nebo při selhání výpočtu a hledání dalšího ohodnocení).
inorder(t(L,_,_),X):-inorder(L,X).
inorder(t(_,X,_),X).
inorder(t(_,_,R),X):-inorder(R,X).
preorder(t(_,X,_),X).
preorder(t(L,_,_),X):-preorder(L,X).
preorder(t(_,_,R),X):-preorder(R,X).
postorder(t(L,_,_),X):-postorder(L,X).
postorder(t(_,_,R),X):-postorder(R,X).
postorder(t(_,X,_),X).
Samozřejmě je možné vytvořit i binární vyhledávací stromy. Pro to potřebujeme proceduru pro přidání do BST.
% pridejBST(+T,+X,+S) :- prida prvek X do stromu T a vrati strom S
pridejBST(nil, X, t(nil,X,nil)).
%pridejBST(t(L,X,P),X,t(L,X,P)). % odkomentovani tehle radky zpusobi, ze se prvky nemohou opakovat
pridejBST(t(L,U,P),X,t(T,U,P)):-X=<U,pridejBST(L,X,T). % tohle je pak treba zmenit na X<U
pridejBST(t(L,U,P),X,t(L,U,T)):-X>U,pridejBST(P,X,T).
Když už umíme přidávat do BST, tak samozřejmě umíme i postavit BST ze seznamu (níže jsou dvě možné varianty).
% seznamNaBST(+S,-T) :- vytvori BST T ze seznamu S
seznamNaBST(S,T):-seznamNaBST(S,nil,T).
seznamNaBST([],T,T).
seznamNaBST([H|Hs],T1,T):-pridejBST(T1,H,T2),seznamNaBST(Hs,T2,T).
sB([], nil).
sB([X], t(nil,X,nil)).
sB([H|T], V):-sB(T,V1),pridejBST(H,V,V1).
Pomocí převedení na seznam a inorder průchodu lze samozřejmě seznam i setřídit:
% bstSort(+Seznam,-SetridenySeznam) :- tridi Seznam pomoci prevodu na BST a vraci
% SetridenySeznam
bstSort(S,T):-seznamNaBST(S,T1),inorderList(T1,T).
Úkol: Pokuste se nyní napsat převod stromu na seznam tak, že v něm budou prvky uloženy po patrech. Tj. vlastně udělat průchod stromem do šířky. Jak byste takový program napsali? Hodí se vám na to rozdílové seznamy z minulého cvičení.
Stromy se ale dají používat i jinak, než jen pro BST. Můžeme jimi například reprezentovat výrazy. V uzlech jsou potom operátory v listech (uzlech, které obsahují dva nil) jsou potom hodnoty. Zkusme si napsat vyhodnocení takového stromu:
%vyhodnot(Strom, Hodnota):-vyhodnooti vyraz zadany jako Strom a vysledek vrati jako Hodnota
vyhodnot(t(nil, H, nil), H).
vyhodnot(t(LP, *, PP), H):-vyhodnot(LP, H1), vyhodnot(PP, H2), H is H1*H2.
vyhodnot(t(LP, +, PP), H):-vyhodnot(LP, H1), vyhodnot(PP, H2), H is H1+H2.
vyhodnot(t(LP, -, PP), H):-vyhodnot(LP, H1), vyhodnot(PP, H2), H is H1-H2.
vyhodnot(t(LP, /, PP), H):-vyhodnot(LP, H1), vyhodnot(PP, H2), H2 =\= 0, H is H1/H2.
Úkol: Uměli byste z výrazu v postfixu takový strom vyrobit? A co kdybyste dostali seznam a úkol mezi prvky seznamu přidat operátory a závorky tak, aby výsledný výraz měl zadanou hodnotu?