% Binary tree drawing in LaTeX using the PiCTeX macros.
%
% Edward M. Reingold (reingold@cs.uiuc.edu)
% Nachum Dershowitz (nachum@cs.uiuc.edu)
%
\typeout{Binary Tree Macros.  Released 18 Jan 1991; modified 2 Apr 1992.}
%
% These macros are in the public domain.  You may use them and copy them at
% will, provided you retain the authorship information.
%
%
% USAGE: \tree[optional root symbol]{left subtree}{right subtree}
%
% For example,
%
%     \tree[X]
%        {\setdots\tree[Z]
%           {\setsolid\tree[Y]{a}{}}
%           {\setsolid\tree{c}{d}}}
%        {\tree
%           {\tree{}{f}}
%           {\tree{g}{h}}}
%
% The root symbol and leaves can be anything you can construct in LaTeX
% or PiCTeX.  The trees constructed can be used in any context in LaTeX
% or PiCTeX.  That is, you can have, say, tables of trees of equations.
%
%
% WARNING: Do not use the tilde (~) as the first character in any subtree!
%
%
% PARAMETERS: Feel free to change the following tree drawing parameters;
%             these parameters can be reset even in the middle of a tree.
%
\newdimen\subtreesep \subtreesep=10pt   % Distance between nonempty subtrees
\newdimen\levelsep   \levelsep=30pt     % Distance between successive levels
\def\nodesymbol{$\bullet$}              % Default symbol for an internal node
%                          Tree edges connecting to the default node symbol
%                          will go to it's center.  Other tree edges will be
%                          chopped off at a node's bounding box.
%
%
% Here's an example that changes the parameters in the middle of the tree:
%
%     \subtreesep=15pt\levelsep=40pt
%     \tree[\fbox{\subtreesep=5pt\levelsep=13pt\tree[o]{a}{a}}]
%        {b}{b}
%
%
% You can get triangular subtrees by using \triangle which has the format 
%
%      \triangle[optional apex label]{width}{height}
%
% For example,
%
%      \tree{\triangle[A]{2\subtreesep}{2\levelsep}}
%           {\tree{\triangle{\subtreesep}{\levelsep}}
%                 {\tree{\fbox{}}
%                       {\fbox{}}}}
%
%
% Don't fiddle with the stuff that follows; it's fairly delicate.
%
% Working variables
%
\catcode`@=11%
\newdimen\halfsubtreesep % half the subtree separation
%
\newdimen\leftwd         % width of left subtree
\newdimen\rightwd        % width of right subtree
%
\newcount\rootbullet     % flag indicating if root is the default bullet
\newdimen\rootwd         % width of root
\newdimen\rootht         % height of root
\newdimen\rootdp         % depth of root
%
\newcount\leftrootbullet % flag indicating if left root is the default bullet
\newdimen\leftrootht     % height of left subtree's root
\newdimen\leftrootwd     % width of left subtree's root
\newcount\rightrootbullet% flag indicating if right root is the default bullet
\newdimen\rightrootht    % height of right subtree's root
\newdimen\rightrootwd    % width of right subtree's root
%
\newdimen\@@root           % distance of root midpointfrom left edge of tree
\newdimen\leftroot       % distance of root midpoint of left subtree
                         % from left edge of tree
\newdimen\rightroot      % distance of root midpoint of right subtree
                         % from left edge of tree
%
\newcount\leafnode       % flag indicating if subtree just placed is a leaf
%
\newdimen\rootxpos       % x-cooordinate of the root midpoint
\newdimen\leftrootpos    % position of the root of the left subtree
\newdimen\rightrootpos   % position of the root of the right subtree
\newdimen\leftpos        % position of the NE corner of the left subtree
\newdimen\rightpos       % position of the NW corner of the right subtree
%
\newbox\rootnode         % the root node, as placed
\newbox\leftsubtree      % the left subtree, as placed
\newbox\rightsubtree     % the right subtree, as placed
%
\newdimen\xa             % (\xa,\ya) = coordinates of the point on the root
\newdimen\ya             % node at which to connect the line to a child
\newdimen\xb             % (\xb,\yb) = coordinates of the point on the child
\newdimen\yb             % at which to connect the line to the parent
%
\let\ifnextchar=\@ifnextchar%
\def\tree{\ignorespaces%
\def\tree{\ifnextchar[{\treey}{\treex}}%
%
\setdimensionmode%
\setlinear%
%
\@ifnextchar[{\treey}{\treex}%
}%
%
\long\def\treex#1#2{\itree{#1}{#2}{\nodesymbol}}  % use default node symbol
\long\def\treey[#1]#2#3{\itree{#2}{#3}{#1}}       % use specified node symbol
%
\long\def\itree#1#2#3{\ignorespaces  % #1=left, #2=right, #3=root
%
\halfsubtreesep=\subtreesep     % Do this calculation for each node so its...
\divide\halfsubtreesep by 2     % ...value can vary throughout the tree
%
\ignorespaces%
%
% Recursively draw nonempty left subtree
%
\ifx ~#1~\ignorespaces%
 \else%
   \leafnode=1  % Assume left subtree is a leaf
   \setbox\leftsubtree=\hbox{#1}\ignorespaces
   \leftwd=\wd\leftsubtree%
   \leftroot=\@@root%
   \leftrootbullet=\rootbullet%
   \leftrootht=\rootht%
   \leftrootwd=\rootwd%
   \ifnum \leafnode=1%
      \leftroot=\leftwd%
      \divide\leftroot by 2%
      \leftrootbullet=0%
      \leftrootht=\ht\leftsubtree%
      \advance\leftrootht by \dp\leftsubtree%
      \leftrootwd=\leftwd%
   \fi%
\fi%
%
% Recursively draw nonempty right subtree
%
\ifx ~#2~\ignorespaces%
 \else%
   \leafnode=1  % Assume right subtree is a leaf
   \setbox\rightsubtree=\hbox{#2}\ignorespaces%
   \rightwd=\wd\rightsubtree%
   \rightroot=\@@root%
   \rightrootbullet=\rootbullet%
   \rightrootht=\rootht%
   \rightrootwd=\rootwd%
   \ifnum \leafnode=1%
      \rightroot=\rightwd%
      \divide\rightroot by 2%
      \rightrootbullet=0%
      \rightrootht=\ht\rightsubtree%
      \advance\rightrootht by \dp\rightsubtree%
      \rightrootwd=\rightwd%
   \fi%
\fi%
%
% In the case of empty subtrees, give artificial values for those empty
% trees so that the later calculations are done properly.
%
\ifx ~#1#2~\ignorespaces        %  Both subtrees empty
   \rightroot=0pt%
   \leftroot=-\halfsubtreesep%
   \leftwd=-\halfsubtreesep%
\else\ifx ~#1~\ignorespaces     %  Left subtree empty, right subtree not empty
   \leftroot=\rightroot%
   \advance\leftroot by -\subtreesep%
   \leftwd=-\subtreesep%
\else\ifx ~#2~\ignorespaces     %  Right subtree empty, left subtree not empty
   \rightroot=\leftroot%
   \advance\rightroot by -\leftwd%
\fi\fi\fi%
%
% With the subtrees done, now do the root node
%
\setbox\rootnode=\hbox{\setcoordinatemode #3}\ignorespaces%
\global\rootwd=\wd\rootnode%
\global\rootht=\ht\rootnode%
\global\advance\rootht by \dp\rootnode%
\ifx \nodesymbol#3\ignorespaces%
    \global\rootbullet=1%
  \else\ignorespaces%
    \global\rootbullet=0%
\fi%
%
% Find distance of the root midpoint from left edge of the tree
%
\global\@@root=\leftroot%
\global\advance\@@root by \rightroot%
\global\advance\@@root by \leftwd%
\global\advance\@@root by \subtreesep%
\ifdim \@@root<\rootwd \global\@@root=\rootwd \fi%
\global\divide\@@root by 2%
%
% Indicate this root and all its ancestors are not a leaves
%
\global\leafnode=0%
%
% Find positions of the root and those of the roots of the subtrees
%
\leftrootpos=\leftroot%
\advance\leftrootpos by -\leftwd%
\advance\leftrootpos by -\halfsubtreesep%
%
\rightrootpos=\rightroot%
\advance\rightrootpos by \halfsubtreesep%
%
\rootxpos=\leftrootpos%
\advance\rootxpos by \rightrootpos%
\divide\rootxpos by 2%
%
\leftpos=0pt%
\advance\leftpos by \leftrootht%
\divide\leftpos by 2%
%
\rightpos=0pt%
\advance\rightpos by \rightrootht%
\divide\rightpos by 2%
%
% Now the root is a box of width \rootwd and total height \rootht, centered
% at (\rootxpos,\levelsep); the root of the left subtree is a box of
% width \leftrootwd and total height \leftrootht, centered at
% (\leftrootpos,0); the root of the right subtree is a box of width
% \rightrootwd and total height \rightrootht, centered at (\rightrootpos,0).
%
%
\beginpicture
%
\put {\box\rootnode} at {\rootxpos} {\levelsep}     % Draw the root
%
\ifx ~#1~\else                                      % Draw the left subtree
   \put {\box\leftsubtree} [rt] at {-\halfsubtreesep} {\leftpos}
   \xa=\rootxpos%
   \ya=\levelsep%
   \ifnum\rootbullet=0%
      \chop{\rootxpos}{\levelsep}{-\rootwd}{\rootht}{\leftrootpos}{0}%
           {\xa}{\ya}%
   \fi%
   \xb=\leftrootpos%
   \yb=0pt%
   \ifnum\leftrootbullet=0%
      \chop{\leftrootpos}{0}{\leftrootwd}{-\leftrootht}{\rootxpos}{\levelsep}%
           {\xb}{\yb}%
   \fi%
   \plot {\xa} {\ya}  {\xb} {\yb} /%
\fi%
%
\ifx ~#2~\else                                      % Draw the right subtree
   \put {\box\rightsubtree} [lt] at {\halfsubtreesep} {\rightpos}
   \xa=\rootxpos%
   \ya=\levelsep%
   \ifnum\rootbullet=0%
      \chop{\rootxpos}{\levelsep}{\rootwd}{\rootht}{\rightrootpos}{0}%
           {\xa}{\ya}%
   \fi%
   \xb=\rightrootpos%
   \yb=0pt%
   \ifnum\rightrootbullet=0%
      \chop{\rightrootpos}{0}{-\rightrootwd}{-\rightrootht}{\rootxpos}%
           {\levelsep}{\xb}{\yb}%
   \fi
   \plot {\xa} {\ya}  {\xb} {\yb} /%
\fi%
%
% Draw the bottom of the triangle, when appropriate.
%
\ifx#1. \ifx#2. \plot {\leftrootpos} {0pt} {\rightrootpos} {0pt} / \fi\fi%
%
\endpicture%
}%
%
\long\def\triangle{\ifnextchar[{\triangley}{\trianglex}}%
\long\def\trianglex#1#2{\itriangle{#1}{#2}{}}       % use empty apex symbol
\long\def\triangley[#1]#2#3{\itriangle{#2}{#3}{#1}} % use specified apex symbol
\long\def\itriangle#1#2#3{%  A triangle #1 wide and #2 high, #3 at apex
   \subtreesep=#1%
   \levelsep=#2%
   \tree[#3]{.}{.}%
}%
%
\newcount\@@x%  Scratch counters used in the computations of \chop
\newcount\@@y%  to find the location on the border of a node's bounding
\newcount\@@a%  box at which to attach a line aimed at a target point
\newcount\@@b%  from the center of the box.
\newcount\@@c%
\newcount\@@d%  It would be better to do all these calculation in dimen's
\newcount\@@e%  instead of counters, but so many dimen's are used above
\newcount\@@f%  that to do so would make running out of dimen's very probable.
\newcount\@@g%  
\newcount\@@h%  Forgive us for not explaining the following computations;
\newcount\@@l%  they're based on elementary analytical geometry.
%
\def\chop#1#2#3#4#5#6#7#8{\ignorespaces%
                          % (#1,#2) = coordinates of center of bounding box
                          % #3 x #4 = width x height of bounding box
                          % (#5,#6) = coordinates of target point
                          % (#7,#8) = coordinates of computed intersection
                          %           point
%
\@@a=#1\divide \@@a by 10000%  Scale down to prevent arithmetic overflow.
\@@b=#2\divide \@@b by 10000%
\@@c=#3\divide \@@c by 10000%
\@@d=#4\divide \@@d by 10000%
\@@e=#5\divide \@@e by 10000%
\@@f=#6\divide \@@f by 10000%
%
\@@l=-\@@f\advance\@@l by \@@b%
%%
\@@y=-\@@d%
\divide \@@y by 2%
\advance\@@y by \@@b%
%%
\@@g=\@@c%
\divide \@@g by 2%
\advance\@@g by \@@a%
%%
\@@x=-\@@a%
\advance\@@x by \@@e%
\multiply\@@x by \@@d%
\divide\@@x by \@@l%
\divide\@@x by 2%
\advance \@@x by \@@a%
%%
\count255=-\@@a%
\advance\count255 by \@@e%
\multiply\count255 by 2%
\@@h=-\@@c%
\multiply \@@h by \@@l%
\divide \@@h by \count255%
\advance \@@h by \@@b%
%
\ifnum #5>#1%
   \ifnum\@@x>\@@g\else\@@g=\@@x\@@h=\@@y\fi%
\else%
   \ifnum\@@x<\@@g\else\@@g=\@@x\@@h=\@@y\fi%
\fi%
\multiply\@@g by 10000%  Scale back up
\multiply\@@h by 10000%
\global#7=\@@g sp%
\global#8=\@@h sp%
}%
\catcode`@=12%