Ninety-Nine Picat Problems
|
Check whether a given term represents a binary tree
Write a predicate istree/1 which succeeds if and only if its
argument is a term representing a binary tree.
Example:
Picat> istree($t(a,t(b,nil,nil),nil)).
yes
Picat> istree($t(a,t(b,nil,nil))).
no
istree(nil) => true.
istree(t(_,L,R)) => istree(L), istree(R).
Construct completely balanced binary trees
In a completely balanced binary tree, the following property
holds for every node: The number of nodes in its left subtree
and the number of nodes in its right subtree are almost equal,
which means their difference is not greater than one.
Write a predicate cbal_tree/2 to construct completely balanced
binary trees for a given number of nodes. The predicate should
generate all solutions via backtracking. Put the letter 'x' as
information into all nodes of the tree.
Example:
Picat> cbal_tree(4,T).
T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;
T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;
etc......No
cbal_tree(0,T) => T = nil.
cbal_tree(N,T), N > 0 =>
T = $t(x,L,R),
N0 = N - 1,
N1 = N0 div 2, N2 = N0 - N1,
distrib(N1,N2,NL,NR),
cbal_tree(NL,L),
cbal_tree(NR,R).
distrib(N,N,NL,NR) => NL = N, NR = N.
distrib(N1,N2,NL,NR) ?=> NL = N1, NR = N2.
distrib(N1,N2,NL,NR) => NL = N2, NR = N1.
Symmetric binary trees
Let us call a binary tree symmetric if you can draw a
vertical line through the root node and then the right
subtree is the mirror image of the left subtree. Write a
predicate symmetric/1 to check whether a given binary tree
is symmetric.
Hint: Write a predicate mirror/2 first to check whether
one tree is the mirror image of another. We are only
interested in the structure, not in the contents of the nodes.
symmetric(nil) => true.
symmetric(t(_,L,R)) => mirror(L,R).
mirror(nil,nil) => true.
mirror(t(_,L1,R1),t(_,L2,R2)) => mirror(L1,R2), mirror(R1,L2).
Binary search trees (dictionaries)
Use the predicate add/3 to write a predicate to construct a
binary search tree from a list of integer numbers.
Example:
Picat> construct([3,2,5,7,1],T).
T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))
Then use this predicate to test the solution of the problem P56.
Example:
Picat> test_symmetric([5,3,18,1,4,12,21]).
yes
Picat> test_symmetric([3,2,5,7,4]).
no
add(X,nil,T) => T = $t(X,nil,nil).
add(X,t(Root,L,R),T), X @< Root => T = $t(Root,L1,R), add(X,L,L1).
add(X,t(Root,L,R),T), X @> Root => T = $t(Root,L,R1), add(X,R,R1).
construct(L,T) => construct(L,T,nil).
construct([],T,T0) => T = T0.
construct([N|Ns],T,T0) => add(N,T0,T1), construct(Ns,T,T1).
test_symmetric(L) => construct(L,T), symmetric(T).
Generate-and-test paradigm
Apply the generate-and-test paradigm to construct all
symmetric, completely balanced binary trees with a given
number of nodes. Example:
Picat> sym_cbal_trees(5,Ts).
Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, ...)]
How many such trees are there with 57 nodes? Investigate
about how many solutions there are for a given number of
nodes? What if the number is even? Write an appropriate
predicate.
sym_cbal_tree(N,T) => cbal_tree(N,T), symmetric(T).
sym_cbal_trees(N,Ts) => Ts = find_all(T,sym_cbal_tree(N,T)).sort_remove_dups().
investigate(A,B) ?=>
between(A,B,N),
sym_cbal_trees(N,Ts),
L = length(Ts),
writef("%w %w\n",N,L),
fail.
investigate(_,_) => true.
Construct height-balanced binary trees
In a height-balanced binary tree, the following property
holds for every node: The height of its left subtree and the
height of its right subtree are almost equal, which means
their difference is not greater than one.
Write a predicate hbal_tree/2 to construct height-balanced
binary trees for a given height. The predicate should
generate all solutions via backtracking. Put the letter 'x'
as information into all nodes of the tree.
Example:
Picat> hbal_tree(3,T).
T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil))) ;
T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil)) ;
...
no
hbal_tree(0,T) => T = nil.
hbal_tree(1,T) => T = $t(x,nil,nil).
hbal_tree(D,T), D > 1 =>
T = $t(x,L,R),
distrib(D-1,D-2,DL,DR),
hbal_tree(DL,L),
hbal_tree(DR,R).
Consider a height-balanced binary tree of height H. What is
the maximum number of nodes it can contain? Clearly,
MaxN = 2**H - 1. However, what is the minimum number MinN?
This question is more difficult. Try to find a recursive
statement and turn it into a predicate minNodes/2 defined
as follwos:
% minNodes(H,N): N is the minimum number of nodes in a
height-balanced binary tree of height H.
On the other hand, we might ask: what is the maximum height
H a height-balanced binary tree with N nodes can have?
% maxHeight(N,H): H is the maximum height of a height-balanced
binary tree with N nodes
Now, we can attack the main problem: construct all the
height-balanced binary trees with a given nuber of nodes.
% hbal_tree_nodes(N,T): T is a height-balanced binary tree
with N nodes.
Find out how many height-balanced trees exist for N = 15.
table
minNodes(0,N) => N = 0.
minNodes(1,N) => N = 1.
minNodes(H,N), H > 1 =>
minNodes(H-1,N1),
minNodes(H-2,N2),
N = 1 + N1 + N2.
maxNodes(H,N) => N is 2**H - 1.
minHeight(0,H) => H = 0.
minHeight(N,H), N > 0 =>
N1 is N // 2,
minHeight(N1,H1),
H is H1 + 1.
maxHeight(N,H) => maxHeight(N,H,1,1).
maxHeight(N,H,H1,N1), N1 > N => H = H1 - 1.
maxHeight(N,H,H1,_N1) =>
H2 = H1 + 1,
minNodes(H2,N2),
maxHeight(N,H,H2,N2).
hbal_tree_nodes(N,T) =>
minHeight(N,Hmin),
maxHeight(N,Hmax),
between(Hmin,Hmax,H),
hbal_tree(H,T),
nodes(T,N).
% nodes(T,N): the binary tree T has N nodes
nodes(nil,N) => N = 0.
nodes(t(_,Left,Right),N) =>
nodes(Left,NLeft),
nodes(Right,NRight),
N = NLeft + NRight + 1.
% count_hbal_trees(N,C): there are C different height-balanced binary
% trees with N nodes.
count_hbal_trees(N,C) =>
C = len(find_all(T,hbal_tree_nodes(N,T))).
Count the leaves of a binary tree
A leaf is a node with no successors. Write a predicate
count_leaves/2 to count them.
count_leaves(nil,N) => N = 0.
count_leaves(t(_,nil,nil),N) => N = 1.
count_leaves(t(_,L,R),N) =>
count_leaves(L,NL),
count_leaves(R,NR),
N = NL+NR.
Collect the leaves of a binary tree in a list
A leaf is a node with no successors. Write a predicate
leaves/2 to collect them in a list.
leaves(nil,S) => S = [].
leaves(t(X,nil,nil),S) => S = [X].
leaves(t(_,L,R),S) =>
leaves(L,SL),
leaves(R,SR),
S = SL ++ SR.
Collect the internal nodes of a binary tree in a list
An internal node of a binary tree has either one or two
non-empty successors. Write a predicate internals/2 to
collect them in a list.
internals(nil,S) => S = [].
internals(t(_,nil,nil),S) => S = [].
internals(t(X,L,R),S) =>
internals(L,SL),
internals(R,SR),
S = [X|SL] ++ SR.
Collect the nodes at a given level in a list
A node of a binary tree is at level N if the path from the
root to the node has length N-1. The root node is at level 1.
Write a predicate atlevel/3 to collect all nodes at a given
level in a list.
Using atlevel/3 it is easy to construct a predicate
levelorder/2 which creates the level-order sequence of the
nodes. However, there are more efficient ways to do that.
atlevel(nil,_,S) => S = [].
atlevel(t(X,_,_),1,S) => S = [X].
atlevel(t(_,L,R),D,S), D > 1 =>
D1 is D-1,
atlevel(L,D1,SL),
atlevel(R,D1,SR),
S = SL ++ SR.
% The following is a quick-and-dirty solution for the
% level-order sequence
levelorder(T,S) => levelorder(T,S,1).
levelorder(T,S,D), atlevel(T,D,[]) => S = [].
levelorder(T,S,D) =>
atlevel(T,D,SD),
D1 = D+1,
levelorder(T,S1,D1),
S = SD ++ S1.
Construct a complete binary tree
A complete binary tree with height H is defined as follows:
The levels 1,2,3,...,H-1 contain the maximum number of nodes
(i.e 2**(i-1) at the level i, note that we start counting
the levels from 1 at the root). In level H, which may
contain less than the maximum possible number of nodes,
all the nodes are "left-adjusted". This means that in a
levelorder tree traversal all internal nodes come first,
the leaves come second, and empty successors (the nil's
which are not really nodes!) come last.
Particularly, complete binary trees are used as data
structures (or addressing schemes) for heaps.
We can assign an address number to each node in a complete
binary tree by enumerating the nodes in levelorder, starting
at the root with number 1. In doing so, we realize that for
every node X with address A the following property holds: The
address of X's left and right successors are 2*A and 2*A+1,
respectively, supposed the successors do exist. This fact can
be used to elegantly construct a complete binary tree structure.
Write a predicate complete_binary_tree/2 with the following
specification:
% complete_binary_tree(N,T): T is a complete binary tree with N nodes.
Test your predicate in an appropriate way.
complete_binary_tree(N,T) => complete_binary_tree(N,T,1).
complete_binary_tree(N,T,A), A > N => T = nil.
complete_binary_tree(N,T,A) =>
T = $t(_,L,R),
AL = 2 * A,
AR = AL + 1,
complete_binary_tree(N,L,AL),
complete_binary_tree(N,R,AR).
Layout a binary tree (1)
Given a binary tree as the usual term t(X,L,R) (or nil). As
a preparation for drawing the tree, a layout algorithm is
required to determine the position of each node in a
rectangular grid. Several layout methods are conceivable,
one of them is as follows.
In this layout strategy, the position of a node v is obtained
by the following two rules:
x(v) is equal to the position of the node v in the inorder
y(v) is equal to the depth of the node v in the tree sequence
In order to store the position of the nodes, we extend the
term representing a node (and its successors) as follows:
% nil represents the empty tree (as usual)
% t(W,X,Y,L,R) represents a (non-empty) binary tree with root
W "positioned" at (X,Y), and subtrees L and R.
Write a predicate layout_binary_tree/2 with the following
specification:
% layout_binary_tree(T,PT): PT is the "positioned" binary
tree obtained from the binary tree T. (+,?)
Test your predicate in an appropriate way.
layout_binary_tree(T,PT) =>
layout_binary_tree(T,PT,1,_,1).
% layout_binary_tree(T,PT,In,Out,D): T and PT as in layout_binary_tree/2;
% In is the position in the inorder sequence where the tree T (or PT)
% begins, Out is the position after the last node of T (or PT) in the
% inorder sequence. D is the depth of the root of T (or PT).
% (+,?,+,?,+)
layout_binary_tree(nil,PT,I,Iout,_) => PT = nil, Iout = I.
layout_binary_tree(t(W,L,R),PT,Iin,Iout,Y) =>
PT = $t(W,X,Y,PL,PR),
Y1 = Y + 1,
layout_binary_tree(L,PL,Iin,X,Y1),
X1 = X + 1,
layout_binary_tree(R,PR,X1,Iout,Y1).
Layout a binary tree (2)
An alternative layout method is to position a node v by
using the following rules:
(1) y(v) is equal to the depth of the node v in the tree
(2) if D denotes the depth of the tree (i.e. the number of
populated levels) then the horizontal distance between
nodes at level i (counted from the root, beginning with
1) is equal to 2**(D-i+1). The leftmost node of the
tree is at position 1.
% layout_binary_tree2(T,PT): PT is the "positionned" binary
% tree obtained from the binary tree T. (+,?)
layout_binary_tree2(nil,PT) => PT = nil.
layout_binary_tree2(T,PT) =>
hor_dist(T,D4),
D is D4//4,
x_pos(T,X,D),
layout_binary_tree2(T,PT,X,1,D).
% hor_dist(T,D4): D4 is four times the horizontal distance
% between the root node of T and its successor(s) (if any).
% (+,-)
hor_dist(nil,D4) => D4 = 1.
hor_dist(t(_,L,R),D4) =>
hor_dist(L,D4L),
hor_dist(R,D4R),
D4 = 2 * max(D4L,D4R).
% x_pos(T,X,D): X is the horizontal position of the root node of T
% with respect to the picture co-ordinate system. D is the horizontal
% distance between the root node of T and its successor(s) (if any).
% (+,-,+)
x_pos(t(_,nil,_),X,_) => X = 1.
x_pos(t(_,L,_),X,D) =>
D2 is D//2,
x_pos(L,XL,D2),
X is XL+D.
% layout_binary_tree2(T,PT,X,Y,D): T and PT as in layout_binary_tree/2;
% D is the the horizontal distance between the root node of T and
% its successor(s) (if any). X, Y are the co-ordinates of the root node.
% (+,-,+,+,+)
layout_binary_tree2(nil,PT,_,_,_) => PT = nil.
layout_binary_tree2(t(W,L,R),PT,X,Y,D) =>
PT = $t(W,X,Y,PL,PR),
Y1 = Y + 1,
Xleft = X - D,
D2 = D // 2,
layout_binary_tree2(L,PL,Xleft,Y1,D2),
Xright is X + D,
layout_binary_tree2(R,PR,Xright,Y1,D2).
Layout a binary tree (3)
The position of a node v is obtained by the following rules:
(1) y(v) is equal to the depth of the node v in the tree
(2) in order to determine the horizontal positions of the
nodes we construct "contours" for each subtree and shift
them together horizontally as close as possible. However,
we maintain the symmetry in each node; i.e. the horizontal
distance between a node and the root of its left subtree
is the same as between it and the root of its right subtree.
The "contour" of a tree is a list of terms c(Xleft,Xright) which
give the horizontal position of the outermost nodes of the tree
on each level, relative to the root position. In the example
given in the problem description, the "contour" of the tree with
root k would be [c(-1,1),c(-2,0),c(-1,1)]. Note that the first
element in the "contour" list is derived from the position of
the nodes c and m.
% layout_binary_tree3(T,PT): PT is the "positionned" binary
% tree obtained from the binary tree T. (+,?)
layout_binary_tree3(nil,PT) => PT = nil.
layout_binary_tree3(T,PT) =>
contour_tree(T,CT), % construct the "contour" tree CT
CT = $t(_,_,_,Contour),
mincont(Contour,MC,0), % find the position of the leftmost node
Xroot = 1-MC,
layout_binary_tree3(CT,PT,Xroot,1).
contour_tree(nil,CT) => CT = nil.
contour_tree(t(X,L,R),CT) =>
CT = $t(X,CL,CR,Contour),
contour_tree(L,CL),
contour_tree(R,CR),
combine(CL,CR,Contour).
combine(nil,nil,Cont) => Cont = [].
combine(t(_,_,_,CL),nil,Cont) =>
Cont = [$c(-1,-1)|Cs],
shift(CL,-1,Cs).
combine(nil,t(_,_,_,CR),Cont) =>
Cont = [$c(1,1)|Cs],
shift(CR,1,Cs).
combine(t(_,_,_,CL),t(_,_,_,CR),Cont) =>
Cont = [$c(DL,DR)|Cs],
maxdiff(CL,CR,MD,0),
DR = (MD+2)//2, DL = -DR,
merge(CL,CR,DL,DR,Cs).
shift([],_,CS) => CS = [].
shift([c(L,R)|Cs],S,CS) =>
CS = [$c(LS,RS)|CsS],
LS is L+S, RS is R+S,
shift(Cs,S,CsS).
maxdiff([],_,MD,MD0) => MD = MD0.
maxdiff(_,[],MD,MD0) => MD = MD0.
maxdiff([c(_,R1)|Cs1],[c(L2,_)|Cs2],MD,A) =>
A1 is max(A,R1-L2),
maxdiff(Cs1,Cs2,MD,A1).
merge([],CR,_,DR,Cs) => shift(CR,DR,Cs).
merge(CL,[],DL,_,Cs) => shift(CL,DL,Cs).
merge([c(L1,_)|Cs1],[c(_,R2)|Cs2],DL,DR,CS) =>
CS = [$c(L,R)|CsR],
L is L1+DL, R is R2+DR,
merge(Cs1,Cs2,DL,DR,CsR).
mincont([],MC,MC0) => MC = MC0.
mincont([c(L,_)|Cs],MC,A) =>
A1 = min(A,L),
mincont(Cs,MC,A1).
layout_binary_tree3(nil,PT,_,_) => PT = nil.
layout_binary_tree3(t(W,nil,nil,_),PT,X,Y) => PT = $t(W,X,Y,nil,nil).
layout_binary_tree3(t(W,L,R,[c(DL,DR)|_]),PT,X,Y) =>
PT = $t(W,X,Y,PL,PR),
Y1 = Y + 1,
Xleft = X + DL,
layout_binary_tree3(L,PL,Xleft,Y1),
Xright = X + DR,
layout_binary_tree3(R,PR,Xright,Y1).
4.16a (**) A string representation of binary trees
The string representation has the following syntax:
<tree> ::= | <letter><subtrees>
<subtrees> ::= | '(' <tree> ',' <tree> ')'
tree_string(T,S), nonvar(T) => tree_to_string(T,S).
tree_string(T,S), nonvar(S) => string_to_tree(S,T).
tree_to_string(T,S) => tree_to_list(T,S).
tree_to_list(nil,S) => S = [].
tree_to_list(t(X,nil,nil),S) => S = [X].
tree_to_list(t(X,L,R),S) =>
S = [X,'('|List],
tree_to_list(L,LsL),
tree_to_list(R,LsR),
List = LsL ++ [','|LsR] ++ [')'].
string_to_tree([],T) => T = nil.
string_to_tree([X],T) => T = $t(X,nil,nil).
string_to_tree([X,'('|List],T) =>
T = $t(X,Left,Right),
append(List1,[')'],List), % not so good (n.f.)
append(LeftList,[','|RightList],List1),
string_to_tree(LeftList,Left),
string_to_tree(RightList,Right).
Preorder and inorder sequences of binary trees
preorder(nil,S) => S = [].
preorder(t(X,Left,Right),S) =>
S = [X|List],
preorder(Left,ListLeft),
preorder(Right,ListRight),
List = ListLeft ++ ListRight.
inorder(nil,S) => S = [].
inorder(t(X,Left,Right),List) =>
inorder(Left,ListLeft),
inorder(Right,ListRight),
List = ListLeft ++ [X|ListRight].
Dotstring representation of binary trees
We consider again binary trees with nodes that are
identified by single lower-case letters, as in the example
of problem 4.16. Such a tree can be represented by the
preorder sequence of its nodes in which dots (.) are inserted
where an empty subtree (nil) is encountered during the tree
traversal.
The syntax of the dotstring representation is super simple:
<tree> ::= . | <letter> <tree> <tree>
tree_dotstring(T,S) => tree_dots_dl(T,S,[]).
tree_dots_dl(nil,L1,L2) => L1 = ['.'|L2].
tree_dots_dl(t(X,Left,Right),L1,L4) =>
L1 = [X|L2],
tree_dots_dl(Left,L2,L3),
tree_dots_dl(Right,L3,L4).