% 4.13 (**) 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(p4_04). % 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).
 

JSA0LjEzICgqKikgTGF5b3V0IGEgYmluYXJ5IHRyZWUgKDEpCiUKJSBHaXZlbiBhIGJpbmFyeSB0cmVlIGFzIHRoZSB1c3VhbCBQcm9sb2cgdGVybSB0KFgsTCxSKSAob3IgbmlsKS4KJSBBcyBhIHByZXBhcmF0aW9uIGZvciBkcmF3aW5nIHRoZSB0cmVlLCBhIGxheW91dCBhbGdvcml0aG0gaXMKJSByZXF1aXJlZCB0byBkZXRlcm1pbmUgdGhlIHBvc2l0aW9uIG9mIGVhY2ggbm9kZSBpbiBhIHJlY3Rhbmd1bGFyCiUgZ3JpZC4gU2V2ZXJhbCBsYXlvdXQgbWV0aG9kcyBhcmUgY29uY2VpdmFibGUsIG9uZSBvZiB0aGVtIGlzCiUgdGhlIGZvbGxvd2luZzoKJQolIFRoZSBwb3NpdGlvbiBvZiBhIG5vZGUgdiBpcyBvYnRhaW5lZCBieSB0aGUgZm9sbG93aW5nIHR3byBydWxlczoKJSAgIHgodikgaXMgZXF1YWwgdG8gdGhlIHBvc2l0aW9uIG9mIHRoZSBub2RlIHYgaW4gdGhlIGlub3JkZXIgc2VxdWVuY2UKJSAgIHkodikgaXMgZXF1YWwgdG8gdGhlIGRlcHRoIG9mIHRoZSBub2RlIHYgaW4gdGhlIHRyZWUKJQolIEluIG9yZGVyIHRvIHN0b3JlIHRoZSBwb3NpdGlvbiBvZiB0aGUgbm9kZXMsIHdlIGV4dGVuZCB0aGUgUHJvbG9nIAolIHRlcm0gcmVwcmVzZW50aW5nIGEgbm9kZSAoYW5kIGl0cyBzdWNjZXNzb3JzKSBhcyBmb2xsb3dzOgolICAgIG5pbCByZXByZXNlbnRzIHRoZSBlbXB0eSB0cmVlIChhcyB1c3VhbCkKJSAgICB0KFcsWCxZLEwsUikgcmVwcmVzZW50cyBhIChub24tZW1wdHkpIGJpbmFyeSB0cmVlIHdpdGggcm9vdAolICAgICAgICBXIHBvc2l0aW9ubmVkIGF0IChYLFkpLCBhbmQgc3VidHJlZXMgTCBhbmQgUgolCiUgV3JpdGUgYSBwcmVkaWNhdGUgbGF5b3V0X2JpbmFyeV90cmVlLzI6CgolIGxheW91dF9iaW5hcnlfdHJlZShULFBUKSA6LSBQVCBpcyB0aGUgInBvc2l0aW9ubmVkIiBiaW5hcnkKJSAgICB0cmVlIG9idGFpbmVkIGZyb20gdGhlIGJpbmFyeSB0cmVlIFQuICgrLD8pIG9yICg/LCspCgo6LSBlbnN1cmVfbG9hZGVkKHA0XzA0KS4gJSBmb3IgdGVzdAoKbGF5b3V0X2JpbmFyeV90cmVlKFQsUFQpIDotIGxheW91dF9iaW5hcnlfdHJlZShULFBULDEsXywxKS4KCiUgbGF5b3V0X2JpbmFyeV90cmVlKFQsUFQsSW4sT3V0LEQpIDotIFQgYW5kIFBUIGFzIGluIGxheW91dF9iaW5hcnlfdHJlZS8yOwolICAgIEluIGlzIHRoZSBwb3NpdGlvbiBpbiB0aGUgaW5vcmRlciBzZXF1ZW5jZSB3aGVyZSB0aGUgdHJlZSBUIChvciBQVCkKJSAgICBiZWdpbnMsIE91dCBpcyB0aGUgcG9zaXRpb24gYWZ0ZXIgdGhlIGxhc3Qgbm9kZSBvZiBUIChvciBQVCkgaW4gdGhlIAolICAgIGlub3JkZXIgc2VxdWVuY2UuIEQgaXMgdGhlIGRlcHRoIG9mIHRoZSByb290IG9mIFQgKG9yIFBUKS4gCiUgICAgKCssPywrLD8sKykgb3IgKD8sKywrLD8sKykKIApsYXlvdXRfYmluYXJ5X3RyZWUobmlsLG5pbCxJLEksXykuCmxheW91dF9iaW5hcnlfdHJlZSh0KFcsTCxSKSx0KFcsWCxZLFBMLFBSKSxJaW4sSW91dCxZKSA6LSAKICAgWTEgaXMgWSArIDEsCiAgIGxheW91dF9iaW5hcnlfdHJlZShMLFBMLElpbixYLFkxKSwgCiAgIFgxIGlzIFggKyAxLAogICBsYXlvdXRfYmluYXJ5X3RyZWUoUixQUixYMSxJb3V0LFkxKS4KCiUgVGVzdCAoc2VlIGV4YW1wbGUgZ2l2ZW4gaW4gdGhlIHByb2JsZW0gZGVzY3JpcHRpb24pOgolID8tICBjb25zdHJ1Y3QoW24sayxtLGMsYSxoLGcsZSx1LHAscyxxXSxUKSxsYXlvdXRfYmluYXJ5X3RyZWUoVCxQVCkuCg==

Y29uc3RydWN0KFtuLGssbSxjLGEsaCxnLGUsdSxwLHMscV0sVCksbGF5b3V0X2JpbmFyeV90cmVlKFQsUFQpLg==

construct([n,k,m,c,a,h,g,e,u,p,s,q],T),layout_binary_tree(T,PT).