% P65 (**) Layout a binary tree (2) % % See problem P64 for the conventions. % % 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) 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. (+,?) :- ensure_loaded(p57). % for test layout_binary_tree2(nil,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,1). hor_dist(t(_,L,R),D4) :- hor_dist(L,D4L), hor_dist(R,D4R), D4 is 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,_),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,nil,_,_,_). layout_binary_tree2(t(W,L,R),t(W,X,Y,PL,PR),X,Y,D) :- Y1 is Y + 1, Xleft is X - D, D2 is D//2, layout_binary_tree2(L,PL,Xleft,Y1,D2), Xright is X + D, layout_binary_tree2(R,PR,Xright,Y1,D2). % Test (see example given in the problem description): % ?- construct([n,k,m,c,a,e,d,g,u,p,q],T),layout_binary_tree2(T,PT).