Select Git revision
2019-11-11-nary-trees.pl
-
jfschaefer authoredjfschaefer authored
2019-11-11-nary-trees.pl 1.29 KiB
% The tree definition from the homework assignment.
istree(tree(Value,Children)) :-
string(Value),subtrees(Children).
subtrees([]).
subtrees([(Cost,T)|Rest]) :-
number(Cost),istree(T), subtrees(Rest).
% An example tree.
% If you want to call e.g. addweights with this tree, you can do it with the following trick:
% tree1(X), addweights(X, Sum).
tree1(tree("A", [(2, tree("B", [(1, tree("E", [])), (2, tree("F", []))])),
(5, tree("C", [(2, tree("G", []))])),
(2, tree("D", [(1, tree("X", [(1, tree("Y", []))]))]))])).
% Add up all the weights of the edges in the tree.
% (we called it cw in the tutorial)
addweights(tree(_, []), 0).
addweights(tree(_, [(X, T)|Rest]), S) :-
addweights(T, S1),
addweights(tree("asdf", Rest), S2),
S is X + S1 + S2.
% Also adds up all the weights, but in a different way:
% In the previous attempt, we always expected a tree as argument and constructed trees on demand.
% In this approach we'll take a list of (Cost, Tree) pairs instead.
% This is not as pretty, but a useful approach for some tree search algorithms.
addweights2([], 0).
addweights2([(X, tree(_, Children))|Rest], S) :-
addweights2(Rest, S1),
addweights2(Children, S2),
S is S1 + S2 + X.
addweights2(T, S) :-
istree(T),
addweights2([(0, T)], S).