Zdroj



% Transformujte binární strom s číselnými klíči
%  (nemusí být vyhledávací, ale tvar zase podle strom/1)
%  tak, že tvar zůstane stejný, ale hodnota klíče vrcholu
%  bude průměrem hodnot původních klíčů v podstromu vrcholu.
% Bodování: 1.6 bodu za lineání řešení,
%  za pomalejší (pro libovolný tvar stromu) maximálně 0.8.

% oznac(+Strom, -Strom)

oznac(S1, S2) :- oznac(S1, S2, _, _).
%oznac(+Strom, -Strom, -PočetVrcholů, -Součet)
oznac(list, list, 0, 0).
oznac(uzel(L1, H, P1), uzel(L2, Prumer, P2), Pocet, Soucet) :-
	oznac(L1, L2, PocetL, SoucetL),
	oznac(P1, P2, PocetP, SoucetP),
	Pocet is PocetL+PocetP+1,
	Soucet is SoucetL+SoucetP+H,
	Prumer is Soucet/Pocet.


strom(list).
strom(uzel(L, K, P)) :- number(K), strom(L), strom(P).

Dotazy


?- S =
  uzel(
    uzel(uzel(list,3,list), 5, uzel(list,2,uzel(list,4,list))),
    7,
    uzel(uzel(list,1,list), 6, list)
  ),
  oznac(S, SO).
SO =
  uzel(
    uzel(uzel(list,3,list), 3.5, uzel(list,3,uzel(list,4,list))),
    4,
    uzel(uzel(list,1,list), 3.5, list)
  ).

?- S = uzel(uzel(uzel(list, 3, list), 4,
  uzel(list, 2, uzel(list, 4, list))), 1,
  uzel(uzel(list, 3, uzel(uzel(list, 7, list), 5, list)),
  7, list)),
  oznac(SI, SO).
SO = uzel(uzel(uzel(list, 3, list), 3.25,
  uzel(list, 3, uzel(list, 4, list))), 4,
  uzel(uzel(list, 5, uzel(uzel(list, 7, list), 6, list)),
  5.5, list)).