% P64 (**) Layout a binary tree (1) % % Given a binary tree as the usual Prolog 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 % the following: % % 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 sequence % y(v) is equal to the depth of the node v in the tree % % In order to store the position of the nodes, we extend the Prolog % 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 positionned at (X,Y), and subtrees L and R % % Write a predicate layout_binary_tree/2: % layout_binary_tree(T,PT) :- PT is the "positionned" binary % tree obtained from the binary tree T. (+,?) or (?,+) :- ensure_loaded(p57). % for test 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). % (+,?,+,?,+) or (?,+,+,?,+) layout_binary_tree(nil,nil,I,I,_). layout_binary_tree(t(W,L,R),t(W,X,Y,PL,PR),Iin,Iout,Y) :- Y1 is Y + 1, layout_binary_tree(L,PL,Iin,X,Y1), X1 is X + 1, layout_binary_tree(R,PR,X1,Iout,Y1). % Test (see example given in the problem description): % ?- construct([n,k,m,c,a,h,g,e,u,p,s,q],T),layout_binary_tree(T,PT).