Initial commit

8 files changed, 4874 insertions, 0 deletions

diff --git a/macros/plain/contrib/treetex/classes.tex b/macros/plain/contrib/treetex/classes.tex
new file mode 100644
index 0000000000..f9dbc98bb9
--- /dev/null
+++ b/macros/plain/contrib/treetex/classes.tex
@@ -0,0 +1,105 @@
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+%%% Complete binary trees                                                  %%%  
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+                                                                                
+% The macro \b@nary{<number>} expands to the description of a complete          
+% binary tree with <number> many internal nodes, where each level is filled with
+% the maximal number of internal nodes, and the last level of internal nodes    
+% is filled from left to right.                                                 
+                                                                                
+\newcount\b@nno % number of nodes                                               
+\newcount\b@nlv % number of complete levels                                     
+\newcount\b@ndl % number of nodes on incomplete level                           
+                                                                                
+\def\ld(#1,#2,#3){% #1, #2, and #3 must be counter registers.                   
+                  % #1 is the input, #1 must be >= 1.                           
+                  % \ld makes the following assignments:                        
+                  % #2:=|_log_2(#1)_|, #3:=2^#2.                                
+                  % The contents of #1 is destroyed during the computation.     
+     #2=0 #3=1                                                                  
+       \loop\ifnum #1>\@ne\relax                                                
+            \divide #1 by\tw@ % this is integer division                        
+            \advance #2 by\@ne                                                  
+            \multiply #3 by\tw@                                                 
+     \repeat}                                                                   
+                                                                                
+\def\b@nary#1{% draws a complete binary tree with #1 internal nodes,            
+           % a complete binary tree with N internal nodes has                   
+           % lv:=|_log_2(N+1)_| many                                            
+           % complete level of binary nodes and dl:=N-2^{lv}+1 many internal    
+           % nodes on an incomplete level.                                      
+     \b@nno=#1\relax\advance\b@nno by \@ne                                      
+     \ld(\b@nno,\b@nlv,\b@ndl)%                                                 
+     \b@ndl=-\b@ndl\advance\b@ndl by #1\advance\b@ndl by\@ne                    
+     \b@n}                                                                      
+                                                                                
+\def\b@n{%                                                                      
+     \ifnum\b@nlv>\@ne                                                          
+           \advance\b@nlv by-\@ne                                               
+           \b@n                                                                 
+           \b@n                                                                 
+           \advance\b@nlv by\@ne                                                
+           \node{}                                                              
+      \else\ifnum\b@ndl>\@ne                                                    
+                 \advance\b@ndl by-\tw@                                         
+                 \node{\le@f\external}\node{\le@f\external}\node{}%             
+                 \node{\le@f\external}\node{\le@f\external}\node{}%             
+                 \node{}%                                                       
+            \else\ifnum\b@ndl=\@ne                                              
+                       \advance\b@ndl by-\@ne                                   
+                       \node{\le@f\external}\node{\le@f\external}\node{}%       
+                       \node{\le@f\external}%                                   
+                       \node{}%                                                 
+                  \else\node{\le@f\external}\node{\le@f\external}\node{}%       
+                    \fi                                                         
+              \fi                                                               
+        \fi}                                                                    
+                                                                                
+\def\circleleaves{\def\le@f{\type{circle}}}                                     
+\def\squareleaves{\def\le@f{\type{square}}}                                     
+                                                                                
+\newcount\no@                                                                   
+\def\no#1{\no@=#1\relax}                                                        
+                                                                                
+\def\binary#1{%                                                                 
+     \no{1}\circleleaves                                                        
+     #1%                                                                        
+     \b@nary{\no@}}                                                             
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+%%% Fibonacci trees                                                        %%%  
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+                                                                                
+% \f@b expands to the description of a Fibonacci tree                           
+% of height \f@bht.                                                             
+                                                                                
+\newcount\f@bht                                                                 
+                                                                                
+\def\f@b{% draws a Fibonacci tree of depth #1                                   
+     \ifnum\f@bht>1                                                             
+           \advance\f@bht by-\@ne\f@b\advance\f@bht by\@ne                      
+           \advance\f@bht by-\tw@\f@b\advance\f@bht by\tw@                      
+           \ifunn@des\node{\unary}                                              
+                  \fi                                                           
+           \node{\lefttop}                                                      
+      \else\ifnum\f@bht=1                                                       
+                 \node{\external\le@f}                                          
+                 \node{\external\le@f}                                          
+                 \node{}                                                        
+            \else\node{\external\le@f}                                          
+              \fi                                                               
+        \fi}                                                                    
+                                                                                
+\newif\ifunn@des                                                                
+                                                                                
+\let\unarynodes\unn@destrue                                                     
+\def\hght#1{\f@bht=#1\relax}                                                    
+                                                                                
+\def\fibonacci#1{%                                                              
+     \hght{0}\unn@desfalse\circleleaves                                         
+     #1%                                                                        
+     \f@b}                                                                      
+                                                                                
+                                                                                
+%                                                                               
+
diff --git a/macros/plain/contrib/treetex/epodd.bbl b/macros/plain/contrib/treetex/epodd.bbl
new file mode 100644
index 0000000000..0d07cfe5fb
--- /dev/null
+++ b/macros/plain/contrib/treetex/epodd.bbl
@@ -0,0 +1,107 @@
+\begin{thebibliography}{10}
+
+\bibitem{BaezaTrees}
+R.~A. Baeza-Yates.
+\newblock On embedding a binary tree on a hypercube.
+\newblock Submitted for publication, November 1988.
+
+\bibitem{Tables}
+R.~J. Beach.
+\newblock {\em Setting Tables and Illustrations with Style}.
+\newblock PhD thesis, University of Waterloo, 1985.
+
+\bibitem{Karlsruhe}
+A.~Br{\"u}ggemann-Klein, P.~Dolland, and A.~Heinz.
+\newblock How to please authors and publishers: A versatile document
+  preparation system at {K}arlsruhe.
+\newblock In J.~D\'esarm\'enien, editor, {\em {\TeX{}} for Scientific
+  Documentation}, pages 8--31, Strasbourg, France, June 1986.
+\newblock Springer-Verlag Lecture Notes in Computer Science~236.
+
+\bibitem{Exeter}
+A.~Br{\"u}ggemann-Klein and D.~Wood.
+\newblock Drawing trees nicely with {\TeX}.
+\newblock In M.~Clark, editor, {\em Proceedings of the Third European
+  \TeX{}-Conference}, Exeter, England, July 1988.
+\newblock To appear.
+
+\bibitem{BinarySearchTrees}
+L.~Devroye.
+\newblock A note on the height of binary search trees.
+\newblock {\em Journal of the ACM}, 33(3):489--498, July 1986.
+
+\bibitem{BinaryTrees}
+Ph. Flajolet and A.~Odlyzko.
+\newblock The average height of binary trees and other simple trees.
+\newblock {\em Journal of Computer and System Sciences}, 25:171--213, 1982.
+
+\bibitem{DocumentFormatting}
+R.~Furuta, J.~Scofield, and A.~Shaw.
+\newblock Document formatting systems: Surveys, concepts, issues.
+\newblock {\em Computing Surveys}, 14(3):417--472, 1982.
+
+\bibitem{GML}
+Ch.~F. Goldfarb.
+\newblock A generalized approach to document markup.
+\newblock {\em SIGPLAN Notices of the ACM}, 16(6):68--73, June 1981.
+
+\bibitem{KWIFIP}
+R.~Klein and D.~Wood.
+\newblock On binary trees.
+\newblock In G.~Ritter, editor, {\em Proceedings of the 11th World Computer
+  Congress}, San Francisco, USA, 1989.
+\newblock To appear.
+
+\bibitem{ACP}
+D.~E. Knuth.
+\newblock {\em Fundamental Algorithms}, volume~1 of {\em The Art of Computer
+  Programming}.
+\newblock Addison-Wesley, Reading, Massachusetts, 1973.
+
+\bibitem{TeXbook}
+D.~E. Knuth.
+\newblock {\em The {\TeX{}}book}, volume~A of {\em Computers \& Typesetting}.
+\newblock Addison-Wesley, Reading, Massachusetts, 1986.
+
+\bibitem{LaTeX}
+L.~Lamport.
+\newblock {\em {\LaTeX}, User's Guide \& Reference Manual}.
+\newblock Addison-Wesley, Reading, Massachusetts, 1986.
+
+\bibitem{OAPD}
+Th. Ottmann and P.~Widmayer.
+\newblock {\em Algorithmen und Datenstrukturen}.
+\newblock Bibliographisches Institut, Mannheim, 1989.
+\newblock To appear.
+
+\bibitem{Grif}
+V.~Quint, I.~Vatton, and H.~Bedor.
+\newblock Grif: An interactive environment for {\TeX{}}.
+\newblock In J.~D\'esarm\'enien, editor, {\em {\TeX{}} for Scientific
+  Documentation}, pages 145--158, Strasbourg, France, June 1986.
+\newblock Springer-Verlag Lecture Notes in Computer Science~236.
+
+\bibitem{Scribe}
+B.~K. Reid.
+\newblock {\em Scribe: A Document Specification Language and its Compiler}.
+\newblock PhD thesis, Carnegie Mellon University, 1980.
+
+\bibitem{TidierTrees}
+E.~M. Reingold and J.~S. Tilford.
+\newblock Tidier drawings of tree.
+\newblock {\em IEEE Transactions on Software Engineering}, 7(2):223--228, March
+  1981.
+
+\bibitem{Complexity}
+K.~J. Supowit and E.~M. Reingold.
+\newblock The complexity of drawing trees nicely.
+\newblock {\em Acta Informatica}, 18(4):377--392, 1983.
+
+\bibitem{TidyTrees}
+Ch. Wetherell and A.~Shannon.
+\newblock Tidy drawings of trees.
+\newblock {\em IEEE Transactions on Software Engineering}, 5(5):514--520,
+  September 1979.
+
+\end{thebibliography}
+
diff --git a/macros/plain/contrib/treetex/epodd.tex b/macros/plain/contrib/treetex/epodd.tex
new file mode 100644
index 0000000000..d2f6b36f17
--- /dev/null
+++ b/macros/plain/contrib/treetex/epodd.tex
@@ -0,0 +1,1189 @@
+% This is epodd.tex, the description of the treetex macro package as it will
+% appear in EP-ODD in summer 89. It is in some aspects more general
+% than tree_doc.tex and corrects an error in the computation of
+% the number of registers used by treetex. The user interface of
+% treetex is explained in more detail in tree_doc.tex.
+
+\documentstyle[12pt,fullpage]{article}
+
+\clubpenalty=10000
+\widowpenalty=10000
+
+\def\addcontentsline#1#2#3{\relax}% Some captions are too long for some
+     % TeX installations (buffer size too small)
+
+\newenvironment{lemma}{\begingroup\samepage\begin{lemmma}\ }{\end{lemmma}%
+     \endgroup}
+\newtheorem{lemmma}{Lemma}[section]
+\newenvironment{proof}{\begin{prooof}\rm\ \nopagebreak}{\end{prooof}}
+\newcommand{\proofend}{\qquad\ifmmode\Box\else$\Box$\fi}
+\newtheorem{prooof}{Proof}
+\renewcommand{\theprooof}{}   % makes shure that prooof doesn't get numbers
+\newenvironment{Figure}{\begin{figure}\vspace{1\baselineskip}}%
+                       {\vspace{1\baselineskip}\end{figure}}
+\newlength{\figspace}         % space between figures in a single
+\setlength{\figspace}{30pt}   % Figure environment
+
+\newcommand{\var}[1]{{\it #1\/}}     % use it for names of variables
+\newcommand{\emph}[1]{{\em #1\/}}    % use it for emphazided text
+                                     % (This notion sticks to the
+                                     % applicative style of markup.)
+\renewcommand{\O}{{\rm O}}           % O-notation, also for math mode
+\newcommand{\T}{{\cal T}}            % the set T in math mode
+\newcommand{\TreeTeX}{Tree\TeX}
+\newcommand{\fig}[1]{Figure~\ref{#1}}
+\let\p\par
+
+\input treetex
+\Treestyle{\vdist{20pt}\minsep{16pt}}
+\dummyhalfcenterdim@n=2pt
+
+% \def\Tree#1\end#2{\end{Tree}}  % Trees are not processed
+% \let\endTree\relax                  %
+
+\def\Node(#1,#2){\put(#1,#2){\circle*{4}}}
+\def\Edge(#1,#2,#3,#4,#5){\put(#1,#2){\line(#3,#4){#5}}}
+
+\def\enode{\node{\external\type{dot}}}
+\def\inode{\node{\type{dot}}}
+
+\def\e{\node{\external\type{dot}}}
+\def\i{\node{\type{dot}}}
+\def\il{\node{\type{dot}\leftonly}}
+\def\ir{\node{\type{dot}\rightonly}}
+
+\newcommand{\stack}[3]{%
+     \vtop{\settowidth{\hsize}{#1}%
+     \setlength{\leftskip}{0pt plus 1fill}%
+     \setlength{\baselineskip}{#2}#3}}
+
+\let\multic\multicolumn
+
+\newlength{\hd} % hidden digit
+\setbox0\hbox{1}
+\settowidth{\hd}{\usebox{0}}
+\newcommand{\ds}{\hspace{\hd}} % digit space
+
+\newcommand{\ccol}[1]{\multicolumn{1}{c}{#1}}
+
+\hyphenation{post-or-der sym-bol Karls-ruhe bool-ean}
+
+\begin{document}
+
+\bibliographystyle{plain}
+
+\title{Drawing Trees Nicely with \TeX\thanks{This work was supported by
+     a Natural Sciences and Engineering Research Council of Canada
+     Grant~A-5692, a Deutsche Forschungsgemeinschaft Grant~Sto167/1-1,
+     and a grant from the Information Technology Research  Centre.
+     It was begun during the first author's stay with
+     the Data Structuring Group in Waterloo.}}
+\author{Anne Br\"uggemann-Klein\thanks{Institut f\"ur Informatik,
+     Universit\"at Freiburg, Rheinstr.~10--12, 7800~Freiburg,
+     West~Germany}\ \and Derick Wood\thanks{Data
+     Structuring Group, Department of Computer Science, University of
+     Waterloo, Waterloo, Ontario N2L~3G1, Canada}}
+\date{}
+\maketitle
+
+\begin{abstract}
+
+We present a new solution to the tree drawing problem that
+integrates an excellent tree drawing algorithm into one of the best text
+processing systems available. More precisely, we present a \TeX{} macro package
+called \TreeTeX{} that produces drawings of trees from a purely logical
+description. Our approach has three advantages: Labels
+for nodes can be handled in a reasonable way; porting
+\TreeTeX{} to any site running \TeX{} is a trivial operation; and
+modularity in the description of a tree and \TeX{}'s macro capabilities
+allow for libraries of subtrees and tree classes.
+
+In addition, \TreeTeX{} has an option that produces
+drawings that make the
+\emph{structure} of the trees more obvious to the human eye,
+even though they may not be as aesthetically pleasing.
+
+\end{abstract}
+
+\section{Introduction}
+
+The problem of successfully integrating pictures and text in a
+document processing environment is tantalizing and difficult.
+Although there are systems available that allow such integration, they
+fall short in many ways, usually in document quality. Furthermore,
+most authors using document  preparation systems are neither book 
+designers nor graphic artists.  Just as modern document preparation
+systems do not expect an author to be a book designer, so we would
+prefer that they do not expect an author to be a graphic artist. The
+second author, Wood, needed to draw many trees in a series of papers
+on trees and in a projected book on trees. This problem enabled us
+to tackle the integration issue for one subarea of graphics, namely,
+tree drawing. We had the decided advantage that there already existed good
+algorithms to draw trees {\em without any author intervention}.
+Previous experience of the integration of pictures and text had been
+uninspiring; the  systems expected the author to prepare each picture
+in total. For example, a tree could be built up from smaller
+subtrees but the relative placement of them was left to the author.
+This situation continues to hold today with the drawing facilities
+available on most personal computers, and, because of this, the
+resulting figures still appear to be ``hand-drawn.'' Additionally,
+they are of inferior quality when compared with the quality of
+the surrounding text.
+
+In this paper we present an entirely new solution that integrates
+a tree drawing algorithm into one of the best text processing
+systems available. More precisely, we  describe \TreeTeX{}, a
+\TeX{} macro package that produces an aesthetically pleasing
+drawing of a tree from a purely logical description.
+We made two fundamental design
+decisions that heavily influenced the method of implementation.
+First, we wanted to allow an author to label the nodes of a tree.
+This decision means that the tree drawing package must be able to
+typeset labels exactly as they would be typeset by the typesetting
+program. There are two reasons for this. Text should be typeset
+consistently, wherever it appears in a document, and the tree
+drawing program needs to know the dimensions of the typeset labels.
+Second, we wanted to ensure that the program could be ported
+easily to other installations and sites, so that other, putative
+users would be able to use it easily.
+Indeed, \TreeTeX{} has been used successfully to typeset trees in
+\cite{BaezaTrees}, \cite{KWIFIP}, and \cite{OAPD}.
+
+By basing our package on \TeX{}, which for more subjective
+reasons we preferred over other typesetting systems such as
+troff, we could ensure wide interest
+in the package. By implementing it as a \TeX{} macro package
+instead of a preprocessor
+we made porting trivial and, furthermore, this also ensured
+consistency of typeset text within a document.
+The down side of this decision is that we had  to program with
+\TeX{} macros, not an experience to be recommended, and we had to live
+with the inherent register limitations of \TeX{}.
+
+This paper consists of a further nine  sections. In Sections~2, 3 and~4,
+we discuss the aesthetics of tree drawing and the algorithm of
+Reingold and Tilford~\cite{TidierTrees}. In Sections~5, 6, and~7, we
+describe our method of incorporating tree drawing into \TeX{}. Then,
+in the last three short sections, we consider the expected number of
+registers \TeX{} needs to draw a tree, the user interface (and three
+\TreeTeX{} examples), and discussion of, among other things, the
+performance  of \TreeTeX{}.
+
+\section{Aesthetical criteria for drawing trees}
+
+In this paper, we are dealing with ordered
+trees in the sense of~\cite{ACP}, specifically binary and unary-binary
+trees. A {\em binary tree\/} is a finite set of nodes that either
+is empty, or consists of a root and two disjoint binary trees called
+the left and right subtrees of the root. A {\em unary-binary tree\/} is
+a finite set of nodes that either is empty, or consists of a root and
+two disjoint unary-binary trees, or consists of a root and one
+nonempty unary-binary tree. An {\em extended binary tree\/} is a binary tree
+in which each node has either two nonempty subtrees or two
+empty subtrees.
+
+There are some basic agreements on how such trees should be drawn, reflecting
+the top-down and left-right ordering of nodes in a tree.
+In \cite{TidierTrees} and \cite{TidyTrees} these basic agreements were
+formalized as the following axioms.
+
+\begin{enumerate}
+\item[1.] Trees impose a distance on the nodes; no node
+          should be closer to the root than any of its
+          ancestors.
+\item[2.] Nodes on the same level should lie on a straight
+          line, and the straight lines defining the levels should be
+          parallel.
+\item[3.] The relative order of nodes on any level should be the same
+          as in the level order traversal of the tree.
+\end{enumerate}
+
+These axioms guarantee that trees are drawn as planar graphs: edges do
+not intersect except at nodes. Two further axioms improve the aesthetical
+appearance of trees.
+
+\begin{enumerate}
+\item[4.] In a unary-binary tree, each left child should be positioned
+          to the left of its parent, each
+          right child to the right of its parent, and each unary child
+          should be positioned below its parent.
+\item[5.] A parent should be centered over its children.
+\end{enumerate}
+
+An additional axiom deals with the problem of tree drawings becoming too wide
+and therefore exceeding the physical limit of the output medium:
+
+\begin{enumerate}
+\item[6.] Tree drawings should occupy as little width as possible without
+          violating the other axioms.
+\end{enumerate}
+
+In \cite{TidyTrees}, Wetherell and Shannon introduce two algorithms for
+tree drawings, the first of which fulfills axioms~1--5, and the second
+1--6. However, as Reingold and Tilford in \cite{TidierTrees}
+point out, there is a lack of symmetry in the algorithms of
+Wetherell and Shannon which may lead to unpleasant results;
+therefore, Reingold and Tilford introduce a new structured
+axiom.
+
+\begin{enumerate}
+\item[7.] A subtree of a given tree should be
+          drawn the same way regardless of where it occurs in the tree.
+\end{enumerate}
+
+Axiom~7 allows the same tree to be drawn differently only when it occurs as
+a subtree in different trees.
+Reingold and Tilford give an algorithm which fulfills axioms~1--5
+and~7. Although
+this algorithm doesn't fulfill axiom~6,
+the aesthetical improvements are well worth the additional space.
+\fig{algorithms} illustrates the benefits of axiom~7, and \fig{narrowtrees}
+shows that the algorithm of Reingold and Tilford violates axiom~6.
+
+\begin{Figure}
+\centering
+\leavevmode\noindent
+\begin{Tree}
+\enode
+\enode\enode\inode\enode\enode\inode\inode\inode
+\node{\external\type{dot}\rght{\unskip\hskip2\mins@p\hskip2\dotw@dth}}
+\enode\enode\inode\enode\enode\inode\inode\inode
+\inode
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\enode
+\enode\enode\inode\enode\enode\inode\inode\inode
+\enode
+\enode\enode\inode\enode\enode\inode\inode\inode
+\inode
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\
+\caption{The left tree is drawn by the algorithm of Wetherell and Shannon,
+and the tidier right one is drawn by the algorithm of Reingold and Tilford.}
+\label{algorithms}
+
+\vspace{\figspace}
+\centering
+\leavevmode\noindent
+\begin{Tree}
+\enode\enode\enode\enode\enode\enode\enode\enode\enode
+\enode\inode\inode\inode
+\enode\inode\inode\inode
+\enode\inode\inode\inode
+\enode\inode\inode\inode
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\enode\enode\enode\enode\enode\enode\enode\enode
+\node{\external\type{dot}\rght{\unskip\hskip\mins@p\hskip\dotw@dth}}
+\enode\inode\inode\node{\type{dot}\rght{\unskip\hskip\mins@p\hskip\dotw@dth}}
+\enode\inode\inode\node{\type{dot}\rght{\unskip\hskip\mins@p\hskip\dotw@dth}}
+\enode\inode\inode\node{\type{dot}\rght{\unskip\hskip\mins@p\hskip\dotw@dth}}
+\enode\inode\inode\inode
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\
+\caption{The left tree is drawn by the algorithm of Reingold and Tilford, but
+the right tree shows that narrower drawings fulfilling all aesthetic axioms
+are possible.}
+\label{narrowtrees}
+\end{Figure}
+
+
+\section{The algorithm of Reingold and Tilford}
+
+The algorithm of Reingold and Tilford (hereafter called ``the RT~algorithm'')
+takes a modular approach to the
+positioning of nodes. The relative positions of the nodes in a subtree
+are calculated independently of the rest of the tree. After the
+relative positions of two subtrees have been calculated, they can be
+joined as siblings in a larger tree by placing them as close
+together as possible and centering the parent node above them.
+Incidentally, this modular approach is the reason that the
+algorithm fails to fulfill axiom~6; see~\cite{Complexity}.
+Two sibling subtrees are placed as close together as possible,
+during a postorder traversal, as follows.
+Imagine that the two subtrees of a binary node
+have been drawn and cut out of paper along
+their contours. Then, starting with the two subtrees superimposed at their
+roots, move them apart until a minimal agreed upon distance
+between the trees is obtained at each level. This can be done gradually.
+Initially, their roots are separated by some agreed upon minimum
+distance; then, at the next level, they are pushed
+apart until the minimum separation is established there.
+This process is continued at successively lower levels until the
+last level of the shorter subtree is reached. At some levels no movement may be
+necessary, but at no level are the two subtrees moved closer
+together. When the process is complete, the position of the
+subtrees is fixed relative to their parent, which is centered over them.
+Assured that the subtrees will never be placed closer together,
+the postorder traversal is continued.
+
+A nontrivial implementation of
+this algorithm has been obtained by Reingold and Tilford in~\cite{TidierTrees} 
+that runs in time $\O(N)$, where $N$ is the number of
+nodes of the tree to be drawn.
+Their crucial idea is to keep track of the contour of the subtrees
+by special pointers, called threads, such that whenever
+two subtrees are joined, only the
+top part of the trees down to the lowest level of the
+smaller tree need to be taken into account.
+
+The nodes are positioned on a fixed grid and are
+considered to have zero width; labeling is not provided. 
+Although the algorithm only draws binary trees, it is easily 
+extended to multiway trees.
+
+\section{Improving human perception of trees}
+
+It is common understanding in book design that aesthetics and readability
+don't necessarily coincide, and---as Lamport (\cite{LaTeX}) puts it---%
+``documents are meant to be read, not hung in museums.'' 
+Therefore, readability is more important than aesthetics.
+
+When it comes to tree drawings, readability means that the structure of
+a tree must be easily recognizable. This criterion is not always met
+by the RT~algorithm. As an example, there are trees whose structure is 
+different even though they have the same number
+of nodes on each level. The RT~algorithm might assign identical positions to
+these nodes making it very hard to perceive the structural differences.
+Hence, we have modified the RT~algorithm such that additional white space
+is inserted between subtrees of
+\emph{significant} nodes. Here a binary node
+is called significant if the minimum distance
+between its two subtrees is achieved \emph{below} their root level.
+Setting the amount of additional white space to zero retains the original RT~%
+placement. The effect of having nonzero additional white space between
+the subtrees of significant
+nodes is illustrated in \fig{addspace}.
+
+Another feature we have added to the RT~algorithms is the possibility to draw
+an unextended binary tree with the same placement of nodes as its
+associated extended version;
+this makes the structure of a tree more prominent; see \fig{extended}.
+We define the \emph{associated extended version}
+of a binary tree to be the binary tree obtained by replacing each empty subtree
+having a nonempty sibling with a subtree consisting of one node. 
+
+\begin{Figure}
+\centering
+\leavevmode\noindent
+\begin{Tree}
+\e\il\e\e\i\i\il % the left subtree
+\e\ir\il % the right subtree
+\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\e\il\il\il % the left subtree
+\e\e\i\e\i\il % the right subtree
+\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\adds@p10pt
+\begin{Tree}
+\e\il\e\e\i\node{\type{dot}\lft{$\longrightarrow$}}\il % the left subtree
+\e\ir\il % the right subtree
+\node{\type{dot}\lft{$\longrightarrow$}}
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\e\il\il\il % the left subtree
+\e\e\i\e\i\il % the right subtree
+\node{\type{dot}\lft{$\longrightarrow$}}
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\
+\adds@p0pt
+
+\caption{The nodes of the first two trees are placed in the same positions
+by the RT~algorithm, although the structure of the two trees is different.
+The alternative drawings highlight the structural differences 
+of the trees by adding additional white space between the subtrees of
+($\longrightarrow$) significant nodes.}
+\label{addspace}
+\end{Figure}
+
+\begin{Figure}
+\centering
+\leavevmode\noindent
+\begin{Tree}
+\e\e\i\il\e\e\i\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\hbox{}\qquad
+\begin{Tree}
+\e\e\i\e\i\e\ir\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\hbox{}\\
+\extended
+\begin{Tree}
+\e\e\i\il\e\e\i\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\hbox{}\qquad
+\begin{Tree}
+\e\e\i\e\i\e\ir\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\hbox{}\\
+\noextended
+\begin{Tree}
+\e\e\i\e\i\e\e\i\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\
+\caption{As in the previous figure, the nodes of the first two trees
+are placed in the same position by the RT algorithm,
+although their structure is different. The modified
+RT~algorithms highlights the structural differences of the trees by 
+drawing them like their identical extended
+version (given in the third row), but suppressing the additional nodes.}
+\label{extended}
+\end{Figure}
+
+
+\section{Trees in a document preparation environment}
+
+Drawings of trees do not usually appear by themselves,
+but are included in some text
+that is itself typeset by a text processing system. Therefore, a typical
+scenario is a pipe of three stages. First, we have a tree drawing
+program that calculates the positioning of the nodes of the tree to
+be drawn and outputs a description of the tree drawing in
+some graphics language; this is followed by
+a graphics system that transforms this
+description into an intermediate language that can be interpreted by the output
+device; and, finally, we have the
+text processing system that integrates the output of the
+graphics system into the text.
+
+This scenario loses its linear structure once nodes have to be labeled, since
+the labeling influences the positioning of the nodes. Labels usually occur
+inside, to the left of, to the right of, or beneath nodes (the latter only for
+external nodes). Their widths should certainly be taken into account
+by the  tree drawing algorithm. But the labels have to be typeset first
+to determine their extensions,
+preferably by the typesetting program that
+is used for the regular text, because this ensures uniformity in the textual
+parts of the document and provides the author with the full power of a
+text processing system for composing the labels. Hence, a more complex
+communication scheme than a simple pipe is required.
+
+Although a system of two processes running simultaneously might be the most
+elegant solution, we wanted a system that is easily portable to
+widely different machines at our sites
+including personal computers with single process
+operating systems.
+Therefore, we decided to use a text processing system
+having programming facilities powerful enough to 
+program a tree drawing algorithm and graphics facilities powerful enough
+to draw a tree. One text processing system
+rendering outstanding typographic quality and satisfactory programming
+facilities is \TeX, developed by Knuth at Stanford University;
+see~\cite{TeXbook}.
+The \TeX{} system includes the following programming facilities.
+
+\begin{enumerate}
+\item[1.] Datatypes:\\
+     integers~(256), dimensions\footnote{The term \emph{dimension} is used
+     in \TeX\ to describe physical measurements of typographical objects;
+     for example, the length of a word.}~(512), 
+     boxes~(256), tokenlists~(256), and
+     boolean variables~(unrestricted).
+\item[2.] Elementary statements:\\
+     $a:=\rm const$, $a:=b$ (all types);\\
+     $a:=a+b$, $a:=a*b$, $a:=a/b$ (integers and dimensions); and\\
+     horizontal and vertical nesting of boxes.
+\item[3.] Control constructs:\\
+     if-then-else statements testing relations between integers,
+     dimensions, boxes, or boolean variables.
+\item[4.] Modularization constructs:\\
+     macros with up to 9~parameters (can be viewed as procedures without
+     the concept of local variables).
+\end{enumerate}
+
+Although the programming
+facilities of \TeX{} hardly exceed the abilities of a Turing machine,
+they are sufficient to
+handle small programs. How about the graphics facilities?
+Although \TeX{} has no built-in graphics facilities, it
+allows the placement of characters in arbitrary positions on
+the page. Therefore, complex pictures can be synthesized from elementary
+picture elements treated as characters. Lamport has included such
+a picture drawing environment in his macro package \LaTeX, using
+quarter circles of different sizes and line segments (with and without
+arrow heads) of different slopes as basic elements; see~\cite{LaTeX}.
+These elements are sufficient for drawing trees.
+
+This survey of \TeX's capabilities implies that \TeX{} may be a suitable
+text processing system to implement a tree drawing algorithm directly.
+We base our algorithm on the RT~algorithm, because this algorithm
+gives, aesthetically, the most pleasing results. In the first version
+presented here, we
+restrict ourselves to unary-binary trees, although our method is
+applicable to arbitrary multiway trees. But to take advantage
+of the text processing environment, we expand the algorithm to allow
+labeled nodes.
+
+In contrast to previous tree drawing programs, we feel no necessity to
+position the nodes of a tree on a fixed grid. While this may be
+reasonable for a plotter with a coarse resolution, it is certainly not
+necessary for \TeX, a system that is capable of handling
+arbitrary dimensions
+and producing device \emph{independent} output.
+
+
+\section{A representation method for \TeX{}trees}
+
+The first problem to be solved in implementing our tree drawing algorithm
+is how to choose a good internal representation
+for trees. A straightforward adaptation
+of the implementation by Reingold and Tilford requires, for each node,
+at least:
+%
+\begin{enumerate}
+\item two pointers to the children of the node,
+\item two dimensions for the offset to the left and the right child (these
+      may be different once there are labels of different widths to the
+      left and right of the nodes),
+\item two dimensions for the $x$- and $y$-coordinates of the final
+      position of the nodes,
+\item three or four labels, and
+\item one token to store the geometric shape (circle, square, framed text, etc.)
+      of the node.
+\end{enumerate}
+%
+Because these data are used frequently in calculations, they should be
+stored in registers (that's what variables are called in \TeX)
+rather than being recomputed, to obtain
+reasonably fast performance. This gives a total of $10N$ registers for
+a tree with $N$ nodes, which quickly exceeds
+\TeX's limited supply of registers. Therefore, we present a
+modified algorithm hand-tailored to the abilities of \TeX{}.
+We start with the following observation.
+Suppose a unary-binary tree is built bottom-up, using a postorder
+traversal. This can be done by repeating the following three steps in
+an order determined by the tree to be built.
+
+\begin{enumerate}
+\item Create a new subtree consisting of one external node.
+\item Create a new subtree by appending the two subtrees last created 
+      to a new binary node; see \fig{Construct}.
+\item Create a new subtree by appending the subtree created last as a left,
+      right, or unary subtree of a new node; see \fig{Construct}.
+\end{enumerate}
+
+(A pointer to) each subtree that has been
+created in steps 1--3 is pushed onto a stack, and
+steps 2 and 3 remove two trees or one tree, respectively,
+from the stack before the push
+operation is carried out. The tree to be built is
+the tree remaining on the stack.
+
+\begin{Figure}
+\centering
+\begin{Tree}
+\treesymbol{\lvls{2}}%
+\hspace{-\l@stlmoff}\usebox{\l@sttreebox}\hspace{\l@strmoff}
+$+$
+\treesymbol{\lvls{2}}%
+\hspace{-\l@stlmoff}\usebox{\l@sttreebox}\hspace{\l@strmoff}\quad
+$\Longrightarrow$\quad
+\treesymbol{\lvls{2}}%
+\treesymbol{\lvls{2}}%
+\node{\type{dot}}%
+\hspace{-\l@stlmoff}\raisebox{\vd@st}{\usebox\l@sttreebox}\hspace{\l@strmoff}%
+\end{Tree}
+
+\vskip\baselineskip
+
+\begin{Tree}
+\treesymbol{\lvls{2}}%
+\hspace{-\l@stlmoff}\usebox{\l@sttreebox}\hspace{\l@strmoff}\quad
+$\Longrightarrow$\quad
+\treesymbol{\lvls{2}}%
+\node{\leftonly\type{dot}}%
+\hspace{-\l@stlmoff}\raisebox{\vd@st}{\usebox\l@sttreebox}\hspace{\l@strmoff}%
+\quad or\quad
+\treesymbol{\lvls{2}}%
+\node{\unary\type{dot}}%
+\hspace{-\l@stlmoff}\raisebox{\vd@st}{\usebox\l@sttreebox}\hspace{\l@strmoff}%
+\quad or\quad
+\treesymbol{\lvls{2}}%
+\node{\rightonly\type{dot}}%
+\hspace{-\l@stlmoff}\raisebox{\vd@st}{\usebox\l@sttreebox}\hspace{\l@strmoff}%
+\end{Tree}
+
+\caption{Construction steps 2 and 3}
+\label{Construct}
+\end{Figure}
+
+This tree traversal is performed twice in the RT~algorithm.
+During the first pass,
+at each execution of steps 2 or~3, the relative positions of the
+subtree(s) and of the new node are computed.
+A closer examination of the RT~algorithm reveals that information about the
+subtree's coordinates is not needed during this pass; the contour information
+alone is sufficient. Complete information is only needed in the second
+traversal, when the tree is really drawn. This is where we can use
+a special feature of \TeX{} that allows us to save registers.
+Unlike Pascal, \TeX{} has the capability of
+storing a drawing in a single box register that can be positioned freely in
+later drawings. This means that in our implementation the two passes
+of the original RT~algorithm can be woven into a single pass,
+storing the contour and drawing of each subtree on the stack.
+Although the latter is a complex object, it takes only one of
+\TeX's precious registers.
+
+
+\section{The internal representation}
+
+Given a tree, the corresponding \TeX{}tree is a box containing
+the ``drawing'' of the tree, together with some additional
+information about the contour of the tree.
+The reference point of a \TeX{}tree-box is always in the root of the
+tree. The height, depth, and width of the box of a \TeX{}tree are
+of no importance in this context.
+
+The additional information about the contour of the tree is stored in some
+registers for numbers and dimensions and
+is needed in order to put subtrees together to form a larger tree.
+An array \var{loff} of dimensions contains for each
+level of the tree the horizontal offset between the
+left end of the leftmost node at the current level and the
+left end of the leftmost node at the next level.
+The horizontal offset between the root
+and the leftmost node of the whole tree is hold in \var{lmoff}, and 
+the horizontal offset between the root and the leftmost node at
+the bottom level of the tree is hold in \var{lboff}.
+Finally, \var{ltop} holds the distance between the reference point
+of the tree and the leftmost end of the root.
+We use
+\var{roff}, \var{rmoff}, \var{rboff}, and \var{rtop}
+as the corresponding variables for ``left'' replaced by ``right.'' Finally,
+\var{height} holds the height of the tree, and \var{type} holds the
+geometric shape of the root of the tree. \fig{TeXtree} shows an example 
+\TeX{}tree, that is a tree drawing and the corresponding additional information.
+
+\begin{Figure}
+\centering
+\begin{Tree}
+\e\ir\ir\e
+  \node{\type{dot}\rightonly\rght{\unskip\vrule height.8pt width5pt depth0pt}}%
+  \i % A
+\end{Tree}
+\leavevmode
+\stack{-10pt}{\vd@st}{%
+     -10pt\\10pt\\10pt\\\var{loff}}%
+\hspace{1em}%
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%
+\hspace{1em}%
+\stack{-10pt}{\vd@st}{%
+     15pt\\5pt\\-10pt\\\var{roff}}%
+
+\vskip\baselineskip\raggedright
+height:~3, type:~dot, ltop:~2pt, rtop:~2pt, lmoff:~-10pt, rmoff:~20pt, lboff:~10pt,
+rboff:~10pt.
+
+\caption{A \TeX{}tree consists of the drawing of the tree and the additional 
+information. The width of the dots is 4pt, the minimal separation between
+adjacent nodes is 16pt, making for a distance of 20pt center to center.
+The length of the small rule labeling 
+one of the nodes is 5pt. The column left (right)
+of the tree drawing is the array \var{loff} (\var{roff}),
+describing the left (right) contour of the tree. At each level,
+the dimension given is the horizontal
+offset between the border at the current and 
+at the next level. The offset between
+the left border of the root node and the leftmost node at level~1 is -10pt,
+the offset between the right border of the root node and the rightmost node at
+level~1 is 15pt, etc.}
+\label{TeXtree}
+\end{Figure}
+
+Given two \TeX{}trees \var{A} and \var{B},
+how can a new \TeX{}tree \var{C} be built that
+consists of a new root and has \var{A} and \var{B} as subtrees?
+An example is given in \fig{AddInfo}.
+First we determine which tree is higher; this is
+\var{B} in the example.
+Then we have to compute the minimal distance
+between the roots of \var{A} and \var{B}, such that at all levels
+of the trees there is free space of at least \var{minsep} between
+the trees when they are drawn side by side.
+For this purpose we keep track of two values, \var{totsep} and
+\var{currsep}. The variables \var{totsep} and \var{currsep}
+hold the total distance between the roots and the distance
+between the rightmost node of \var{A} and the leftmost node
+of \var{B} at the current level. To calculate
+\var{totsep} and \var{currsep}, we start at level 0 and
+visit each level of the trees until we reach the bottommost level
+of the smaller tree; this is \var{A} in our example.
+
+\begin{Figure}
+\centering
+\begin{Tree}
+\e\ir\ir\e
+  \node{\type{dot}\rightonly\rght{\unskip\vrule height.8pt width5pt depth0pt}}%
+  \i % A
+\end{Tree}
+\leavevmode
+A: \stack{-10pt}{\vd@st}{%
+     -10pt\\10pt\\10pt\\\ \\\var{loff}(\var{A})}%
+\hspace{1em}%
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%
+\hspace{1em}%
+\stack{-10pt}{\vd@st}{%
+     15pt\\5pt\\-10pt\\\ \\\var{roff}(\var{A})}%
+\qquad
+\begin{Tree}
+\e\il\e\i\il\il\ir % B
+\end{Tree}
+\leavevmode
+B: \stack{-10pt}{\vd@st}{%
+     10pt\\-10pt\\-10pt\\-10pt\\-10pt\\\ \\\var{loff}(\var{B})}%
+\hspace{1em}%
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%
+\hspace{1em}%
+\stack{-10pt}{\vd@st}{%
+     10pt\\-10pt\\-10pt\\10pt\\-30pt\\\ \\\var{roff}(\var{B})}%
+\\[\figspace]
+\begin{Tree}
+\e\ir\ir\e
+  \node{\type{dot}\rightonly\rght{\unskip\vrule height.8pt width5pt depth0pt}}%
+  \i % A
+\e\il\e\i\il\il\ir % B
+\i % C
+\end{Tree}
+\leavevmode
+C: \stack{-10pt}{\vd@st}{%
+     -20\\-10pt\\%
+     \makebox[0pt][r]{\var{loff}(\var{A})$\smash{\left\{\vrule height\vd@st
+          depth\vd@st width0pt\right.}$ }%
+     10pt\\10pt\\%
+     \makebox[0pt][r]{$\longrightarrow$ }%
+     10pt\\%
+     \makebox[0pt][r]{\raisebox{-.5\vd@st}{\var{loff}(\var{B})$\smash
+          {\left\{\vrule height.5\vd@st
+          depth.5\vd@st width0pt\right.}$ }}%
+     \makebox[0pt][r]{-}10pt\\\ \\\var{loff}(\var{C})}%
+\hspace{1em}%
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%
+\hspace{1em}%
+\stack{-10pt}{\vd@st}{%
+     20pt\\10pt\\-10pt\\-10pt%
+     \makebox[0pt][l]{\raisebox{-.5\vd@st}{
+          $\smash{\left\}\vrule height2.5\vd@st
+          depth2.5\vd@st width0pt\right.}$\var{roff}(\var{B})}}%
+     \\10pt\\-30pt\\\ \\\var{roff}(\var{C})}%
+
+\vspace{\figspace}
+\centering
+\begin{tabular}{|l|r|r|r|}
+\hline
+&\multic{1}{c|}{\var{A}}&\multic{1}{c|}{\var{B}}&\multic{1}{c|}{\var{C}}\\
+\hline
+height&\multic{1}{c|}{3}&  \multic{1}{c|}{5}&  \multic{1}{c|}{6}\\
+type&  \multic{1}{c|}{dot}&\multic{1}{c|}{dot}&\multic{1}{c|}{dot}\\
+ltop&  2pt&                2pt&                2pt\\
+rtop&  2pt&                2pt&                2pt\\
+lmoff& -10pt&              -30pt&              -30pt\\
+rmoff& 20pt&               10pt&               30pt\\
+lboff& 10pt&               -30pt&              -10pt\\
+rboff& 10pt&               -30pt&              -10pt\\
+\hline
+\end{tabular}\qquad
+\begin{tabular}{|c|r|r|}
+\hline
+\multic{1}{|c|}{level}&\multic{1}{c|}{\var{totsep}}&
+                      \multic{1}{c|}{\var{currsep}}\\
+\hline
+0&20pt&0/16pt\\
+1&25pt&11/16pt\\
+2&40pt&1/16pt\\
+3&40pt&16pt\\
+\hline
+\end{tabular}
+\caption{The \TeX{}trees \var{A} and~\var{B} are combined to form the
+larger \TeX{}\-tree~\var{C}. The first table gives the additional
+information of the three \TeX{}trees,
+and the second table gives the
+history of the computation for \var{totsep} and \var{currsep}.}
+\label{AddInfo}
+\end{Figure}
+
+At level 0, the distance between the roots of \var{A} and \var{B}
+should be at least \var{minsep}. Therefore, we set
+$\var{totsep}:=\var{minsep} + \var{rtop}(\var{A})
++ \var{ltop}(\var{B})$ and $\var{currsep}:=\var{minsep}$.
+Using $\var{roff}(\var{A})$ and $\var{loff}(\var{B})$, we can
+calculate \var{currsep} for the next level.
+If $\var{currsep} < \var{minsep}$, we have to increase \var{totsep} by
+the difference and update \var{currsep}. This process is
+repeated until we reach the lowest level of \var{A}
+at which point \var{totsep} holds the final distance between the
+nodes of \var{A} and \var{B}, as calculated by the RT~algorithm.
+If the root of \var{C} is a significant node, then the additional space,
+which is 0pt by default, is added to \var{totsep}.
+However, the approach of synthesizing
+drawings from simple graphics characters allows only a finite
+number of orientations for the tree edges; therefore, \var{totsep}
+must be increased slightly to fit the next orientation
+available.
+
+Now we are ready to build the box of \TeX{}tree~\var{C}.
+Simply put \var{A} and~\var{B} side by side, with the reference
+points \var{totsep}~units apart, insert a new node
+above them, and connect the parent and children by edges.
+Next, we compute the additional information
+for \var{C}. This can be done by using the additional information
+for \var{A} and~\var{B}.
+Note that most components of $\var{roff}(\var{C})$ and
+$\var{lroff}(\var{C})$ are the same as in the higher tree, which
+is \var{B} in our case.
+So, if we can avoid moving this information around, 
+the number of counters we have to access to update the additional information
+for \var{C} is within a small constant of the height of~\var{A}.
+Hence, we can apply the same argument as
+in~\cite{TidierTrees}, which gives
+us a running time of $\O(N)$ for drawing a tree with N nodes.
+
+We must design the allocation of storage registers for
+the additional information of \TeX{}trees carefully to fulfill the
+following requirement. If a new tree is built from
+two subtrees, the additional information of the new tree
+shares storage with its larger subtree.
+Organizational overhead, that is,
+pointers that keep track of the locations of different parts of additional
+information, must be avoided.
+This means that the additional information
+for one \TeX{}tree should be stored in a sequence
+of consecutive dimension registers
+such that only one pointer for access to the first element
+in this sequence is needed. On the other hand, each parent
+tree is higher and, therefore, needs more storage than its subtrees.
+So we must ensure that there is always enough space in the sequence
+for more information.
+
+The obvious way to fulfill these requirements is to use a stack and to
+allow only the topmost \TeX{}trees of this stack to be
+combined into a larger tree at any time.
+This leads to the following allocation of registers: A contiguous sequence of
+box registers contains the treeboxes of the subtrees in the stack. A
+contiguous sequence of token registers contains the type information for the
+nodes of the subtrees in the stack. For each subtree in the stack,
+a contiguous sequence of dimension registers contains the contour
+information of the subtree. The ordering of these groups of dimension
+registers reflects the ordering of the subtrees in the
+stack. Finally, a contiguous sequence of counter registers contains
+the height and the address of the first dimension register for
+each subtree in the stack. Four address counters store the addresses
+of the last treebox, type information, height, and address of contour
+information. A sketch of the register organization for a stack of \TeX{}trees
+is provided in \fig{Registers}.
+
+\begin{Figure}
+Dimension registers\\
+\var{lmoff}(1) \var{rmoff}(1) \var{lboff}(1) \var{rboff}(1) \var{ltop}(1)
+               \var{rtop}(1)\\
+\var{loff}($h_1$) \var{roff}($h_1$) \dots\ \var{loff}(1) \var{roff}(1)\\
+\dots\\
+\var{lmoff}($n$) \var{rmoff}($n$) \var{lboff}($n$) \var{rboff}($n$)
+                 \var{ltop}($n$) \var{rtop}($n$)\\
+\var{loff}($h_n$) \var{roff}($h_n$) \dots\ \var{loff}(1) \var{roff}(1)\\
+\mbox{}\\
+Counter registers\\
+\var{lasttreebox} \var{lasttreeheight} \var{lasttreeinfo} \var{lasttreetype}\\
+\var{treeheight}(1) \var{diminfo}(1) \dots\ \var{treeheight}($n$)
+                    \var{diminfo}($n$)\\
+\mbox{}\\
+Box registers\\
+\var{treebox}(1) \dots\ \var{treebox}($n$)\\
+\mbox{}\\
+Token registers\\
+\var{type}(1) \dots\ \var{type}($n$)
+
+\caption{\var{lasttreebox}, \var{lasttreeheight}, \var{lasttreeinfo},
+\var{lasttreetype} contain pointers to \var{treebox}($n$)
+\var{treeheight}($n$), \var{lmoff}($n$), \var{type}($n$),
+\var{diminfo}($i$) contains a pointer to
+\var{lmoff}($i$). Unused dimension registers are
+allowed between the dimension registers of subsequent trees. The counter
+registers \var{lasttreebox},\ldots,\var{diminfo}($n$) serve as a directory
+mechanism to access the \TeX{}trees on the stack.}
+\label{Registers}
+\end{Figure}
+
+
+When a new node is pushed onto the stack, the treebox, type information,
+height, address of contour information, and contour information are
+stored in the next free registers of the appropriate type, and the
+four address counters are updated accordingly.
+
+When a new tree is formed from the topmost subtrees on the stack,
+the treebox, type information, height, and address of contour information
+of the new tree are sorted in the registers formerly used by the bottommost
+subtree that has occurred in the construction step, 
+and the four address registers are
+updated accordingly. This means that this information for the subtrees
+is no longer accessible. The contour information of the new subtree
+is stored in the same registers as the contour information of the larger
+subtree used in the construction, apart from the left and right offset
+of the root to the left and right child, which are stored in the
+following dimension registers. This means that gaps can occur
+between the contour information of subtrees in the
+stack, namely when the right subtree, which is in a higher position in the
+stack, is higher than the left one. To avoid these
+gaps, the user can specify an option \verb.\lefttop. when entering a
+binary node, which makes the topmost tree in the stack the
+left subtree of the node.
+
+This stack concept also has consequences for the design of the user interface
+that is discussed in Section~\ref{Interface}.
+
+\section{Space cost analysis}
+
+Suppose we want to draw a unary-binary tree $T$ of height $h$ having
+$N$ nodes\footnote{The height $h$ and the number of nodes $N$ refer to the
+drawing of the tree. $N$ is the number of circles, squares,~etc., actually
+drawn, and $h$ is the number of levels in the drawing minus 1.}.
+According to our internal representation,
+for each subtree in the stack we need:
+
+\begin{enumerate}
+\item one box register to store the box of the \TeX{}tree;
+\item one token register to store the type of the root of the subtree;
+\item $2h^\prime+6$ dimension registers to store the additional
+      information, where $h^\prime$ is the height of the
+      subtree; and
+\item three counter registers to store the register numbers of the
+      box register, the token register, and the first dimension register above.
+\end{enumerate}
+
+\begin{lemma}
+Let $T$ be a unary-binary tree of height~$h$ and size~$N$; then:
+\begin{enumerate}
+\item at any time, there are at most $h+1$ subtrees of $T$ on the
+      stack; and
+\item for each set $\T$ of subtrees of $T$ that are on the stack
+      simultaneously we have
+      $$\sum_{T^\prime\in \T}({\rm ht}(T^\prime)+1) \le N$$
+\end{enumerate}
+\end{lemma}
+
+The lemma implies that our implementation 
+uses at most $9h+2N$~registers. 
+To compare this with the
+$10N$ registers used in the straightforward implementation,
+an estimation of the average height of a tree with $N$ nodes is
+needed. Several results, depending on the type of trees and of the
+randomization model, are cited in \fig{Stat}, which
+compares the number of registers used in a straightforward
+implementation with the average number of registers used in our
+implementation. This table shows clearly the advantage of our
+implementation.
+
+\begin{Figure}
+\centering
+
+\begin{tabular}{|c|c|c|c|c|}
+\hline
+&registers&\multicolumn{3}{c|}{average registers}\\
+\cline{3-5}
+nodes&(straight-&&unary-binary&binary\\
+&forward)&binary trees&trees&search trees\\
+$N$&&($2\sqrt{\pi N}$) \cite{BinaryTrees}&
+     ($\sqrt{3\pi N}$) ~\cite{BinaryTrees}&
+     ($4.311\log N$) \cite{BinarySearchTrees}\\
+\hline
+\ds10 & \ds100 & 120.89 & 107.37 & 109.34 \\
+\ds20 & \ds200 & 182.68 & 163.56 & 156.23 \\
+\ds30 & \ds300 & 234.75 & 211.33 & 191.96 \\
+\ds40 & \ds400 & 281.78 & 254.75 & 223.12 \\
+\ds50 & \ds500 & 325.60 & 295.37 & 251.78 \\
+\ds60 & \ds600 & 367.13 & 334.02 & 278.86 \\
+\ds70 & \ds700 & 406.93 & 371.17 & 304.84 \\
+\ds80 & \ds800 & 445.36 & 407.13 & 330.02 \\
+\ds90 & \ds900 & 482.67 & 442.12 & 354.59 \\
+100 & 1000 & 519.04 & 476.30 & 378.68 \\
+\hline
+\end{tabular}
+
+\caption{The numbers of registers used by a straightforward implementation
+(second column) and by our modified implementation (third to fifth column)
+of the RT~algorithm are
+given for different types of trees and randomization models.
+The formulas in parentheses indicate the average height of the respective 
+classes of trees.}
+\label{Stat}
+\end{Figure}
+
+
+\section{The user interface}\label{Interface}
+
+The user interface of \TreeTeX{} has been designed in the spirit of
+the thorough separation of the logical description of document components
+and their layout; see~\cite{DocumentFormatting,GML}. This concept
+ensures both uniformity and flexibility of document layout and frees
+authors from layout problems that have nothing to do with the
+substance of their work. For some powerful implementations and projects
+see \cite{Tables,Karlsruhe,LaTeX,Grif,Scribe}.
+
+The description of a tree consists of a description of its nodes
+in postorder. Each description of a node, in turn, has to specify
+the outdegree, the geometric shape and the labels of the node.
+Defaults are provided for all specifications,
+thereby allowing the user to omit many definitions
+if the defaults match what he or she wants.
+
+A separate style command defines layout parameters for tree drawings
+that are valid for all trees of a document.
+Layout parameters include the font to be used for labels, the diameter
+of circle nodes, the vertical distance between two subsequent levels
+of the tree, and the minimal horizontal distance between nodes.
+
+Standard versions of \TeX{} provide only a limited number of
+font and circle sizes. Hence, the user of the style command must make
+sure that the specified sizes can be realized. This is especially
+cumbersome when everything has to be magnified for later reproduction
+with reduction. But the style variables can be made parametric for
+installations that provide scalable fonts and replace \LaTeX{}'s
+circle- and line-drawing commands with routines that provide arbitrary
+diameters and slopes.
+
+Three examples of tree descriptions are given in 
+Figures~\ref{firstex}--\ref{lastex}.
+A more detailed description of the user interface is 
+given in~\cite{Exeter}.
+
+\section{Conclusions}
+
+We hope that, by now, we have convinced the reader of the main advantages
+of \TreeTeX{}: It integrates graphics and text; it is portable to all
+sites running \TeX{}; 
+and it is easy to use for the author, because it derives the drawing 
+of a tree from a purely structural description. But our decision to
+implement \TreeTeX{} as a \TeX{} macro package has also some
+drawbacks, both for the programmer and for the user of the system.
+
+>From the programmer's point of view, \TeX{}'s macro language is
+a low level programming language. Hence, maintaining and extending
+the package is a more tedious task than it would be if we had used
+a higher level language with better support for modularization.
+
+>From the author's point of view, \TreeTeX{}'s limitations lie in
+speed, size of trees, and graphical primitives.
+Typesetting all the trees in this article takes about two~minutes on
+a VAX~750, and typesetting a complete binary tree with 63~internal
+and 64~external nodes takes about one~minute on the same machine.
+The size of the trees is limited by three factors, namely,
+the number of registers, the complexity of the nested boxes that
+contain the drawing of a tree, and the limited number of slopes
+that are available for the edges, the latter being the most severe 
+problem at present. Hence, the main area of application for
+\TreeTeX{} is modest use such as in textbooks; displaying
+large amounts of statistical data, for example, is out of the question.
+
+Currently edges and circular nodes are drawn from \LaTeX{}'s set of 
+predefined graphical characters. Hence, \TreeTeX{} cannot draw
+arbitrarily wide trees or large circular nodes. We consider
+this restriction, however, to be a temporary one, since a committee inside
+the \TeX{} Users Group is  working on standard graphic 
+extensions to \TeX{} that will remove these limitations.
+
+As to further developments of \TreeTeX{}, it would be desirable to
+draw larger classes of trees, for example multiway trees, and to allow
+labels not only for nodes, but also for edges and whole subtrees.
+
+
+\Treestyle{\vdist{60pt}}
+\dummyhalfcenterdim@n=10pt
+
+\begin{Figure}
+\centering
+\begin{Tree}
+\node{\external\bnth{first}\cntr{1}\lft{Beeton}}
+\node{\external\cntr{3}\rght{Kellermann}}
+\node{\cntr{2}\lft{Carnes}}
+\node{\external\cntr{6}\lft{Plass}}
+\node{\external\bnth{last}\cntr{8}\rght{Tobin}}
+\node{\cntr{7}\rght{Spivak}}
+\node{\leftonly\cntr{5}\rght{Lamport}}
+\node{\cntr{4}\rght{Knuth}}
+\end{Tree}
+
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}\
+
+\begin{verbatim}
+\begin{Tree}
+\node{\external\bnth{first}\cntr{1}\lft{Beeton}}
+\node{\external\cntr{3}\rght{Kellermann}}
+\node{\cntr{2}\lft{Carnes}}
+\node{\external\cntr{6}\lft{Plass}}
+\node{\external\bnth{last}\cntr{8}\rght{Tobin}}
+\node{\cntr{7}\rght{Spivak}}
+\node{\leftonly\cntr{5}\rght{Lamport}}
+\node{\cntr{4}\rght{Knuth}}
+\end{Tree}
+
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}
+\end{verbatim}
+
+\caption{This is an example of a tree that includes labels.}
+\label{firstex}
+\end{Figure}
+
+\begin{Figure}
+\centering
+\begin{Tree}
+\node{\external\type{frame}\bnth{first}\cntr{Beeton}}
+\node{\external\type{frame}\cntr{Kellermann}}
+\node{\type{frame}\cntr{Carnes}}
+\node{\external\type{frame}\cntr{Plass}}
+\node{\external\type{frame}\bnth{last}\cntr{Tobin}}
+\node{\type{frame}\cntr{Spivak}}
+\node{\leftonly\type{frame}\cntr{Lamport}}
+\node{\type{frame}\cntr{Knuth}}
+\end{Tree}
+
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}\
+
+\begin{verbatim}
+\begin{Tree}
+\node{\external\type{frame}\bnth{first}\cntr{Beeton}}
+\node{\external\type{frame}\cntr{Kellermann}}
+\node{\type{frame}\cntr{Carnes}}
+\node{\external\type{frame}\cntr{Plass}}
+\node{\external\type{frame}\bnth{last}\cntr{Tobin}}
+\node{\type{frame}\cntr{Spivak}}
+\node{\leftonly\type{frame}\cntr{Lamport}}
+\node{\type{frame}\cntr{Knuth}}
+\end{Tree}
+
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}
+\end{verbatim}
+\caption{This is an example of a tree with framed center labels.}
+\end{Figure}
+
+\begin{Figure}
+\Treestyle{\treefonts{\small\it}\nodesize{16pt}\vdist{40pt}\minsep{16pt}}
+\centering
+\begin{Tree}
+\node{\external\bnth{first}\cntr{1}\lft{Beeton}}
+\node{\external\cntr{3}\rght{Kellermann}}
+\node{\cntr{2}\lft{Carnes}}
+\node{\external\cntr{6}\lft{Plass}}
+\node{\external\bnth{last}\cntr{8}\rght{Tobin}}
+\node{\cntr{7}\rght{Spivak}}
+\node{\leftonly\cntr{5}\rght{Lamport}}
+\node{\cntr{4}\rght{Knuth}}
+\end{Tree}
+
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}\
+
+\caption{This tree was produced from the same logical description as in
+Figure~\ref{firstex}, but with different style parameters}
+\label{lastex}
+\end{Figure}
+
+\clearpage
+\bibliography{trees}
+\end{document}
+
+
diff --git a/macros/plain/contrib/treetex/l_pic.tex b/macros/plain/contrib/treetex/l_pic.tex
new file mode 100644
index 0000000000..26e71e5475
--- /dev/null
+++ b/macros/plain/contrib/treetex/l_pic.tex
@@ -0,0 +1,839 @@
+% All this stuff comes from latex.tex, most of it from the                      
+% picture environment. No changes!!!                                            
+% It is needed if you want to use TreeTeX together with plain TeX.              
+                                                                                
+\catcode`\@=11                                                                  
+                                                                                
+\def\@height{height}                                                            
+\def\@depth{depth}                                                              
+\def\@width{width}                                                              
+                                                                                
+\font\tenln=line10                                                              
+\font\tencirc=circle10                                                          
+\font\tenlnw=linew10                                                            
+\font\tencircw=circlew10                                                        
+                                                                                
+\newcount\@tempcnta                                                             
+\newcount\@tempcntb                                                             
+\newdimen\@tempdima                                                             
+\newdimen\@tempdimb                                                             
+\newbox\@tempboxa                                                               
+                                                                                
+\def\@whilenoop#1{}                                                             
+                                                                                
+\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}             
+\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim                          
+        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}                     
+                                                                                
+\def\@ifnextchar#1#2#3{\let\@tempe #1\def\@tempa{#2}\def\@tempb{#3}\futurelet   
+    \@tempc\@ifnch}                                                             
+\def\@ifnch{\ifx \@tempc \@sptoken \let\@tempd\@xifnch                          
+      \else \ifx \@tempc \@tempe\let\@tempd\@tempa\else\let\@tempd\@tempb\fi    
+      \fi \@tempd}                                                              
+                                                                                
+% NOTE: the following hacking must precede the definition of \:                 
+%  as math medium space.                                                        
+                                                                                
+\def\:{\let\@sptoken= } \:  % this makes \@sptoken a space token                
+                                                                                
+\def\:{\@xifnch} \expandafter\def\: {\futurelet\@tempc\@ifnch}                  
+                                                                                
+\def\@ifstar#1#2{\@ifnextchar *{\def\@tempa*{#1}\@tempa}{#2}}                   
+                                                                                
+\let\:=\>                                                                       
+                                                                                
+%      ****************************************                                 
+%      *       THE PICTURE ENVIRONMENT        *                                 
+%      ****************************************                                 
+%                                                                               
+%  \unitlength     = value of dimension argument                                
+%  \@wholewidth    = current line width                                         
+%  \@halfwidth     = half of current line width                                 
+%  \@linefnt       = font for drawing lines                                     
+%  \@circlefnt     = font for drawing circles                                   
+%                                                                               
+% \linethickness{DIM} : Sets the width of horizontal and vertical lines         
+%     in a picture to DIM.  Does not change width of slanted lines              
+%     or circles.   Width of all lines reset by \thinlines and                  
+%     \thicklines                                                               
+%                                                                               
+% \picture(XSIZE,YSIZE)(XORG,YORG)                                              
+%   BEGIN                                                                       
+%     \@picht :=L YSIZE * \unitlength                                           
+%     box \@picbox :=                                                           
+%          \hbox to XSIZE * \unitlength                                         
+%            {\hskip -XORG * \unitlength                                        
+%             \lower YORG * \unitlength                                         
+%             \hbox{                                                            
+%   END                                                                         
+%                                                                               
+% \endpicture ==                                                                
+%   BEGIN                                                                       
+%                   } \hss }                                                    
+%                   heigth of \@picbox := \@picht                               
+%                   depth  of \@picbox := 0                                     
+%                   leavevmode                                                  
+%                   \box\@picbox                                                
+%   END                                                                         
+%                                                                               
+% \put(X, Y){OBJ} ==                                                            
+%   BEGIN                                                                       
+%     \@killglue                                                                
+%     \raise Y * \unitlength  \hbox to 0pt { \hskip X * \unitlength             
+%                                              OBJ \hss             }           
+%     \ignorespaces                                                             
+%   END                                                                         
+%                                                                               
+% \multiput(X,Y)(DELX,DELY){N}{OBJ} ==                                          
+%   BEGIN                                                                       
+%    \@killglue                                                                 
+%    \@multicnt := N                                                            
+%    \@xdim  := X * \unitlength                                                 
+%    \@ydim  := Y * \unitlength                                                 
+%    while \@multicnt > 0                                                       
+%      do \raise \@ydim \hbox to 0pt { \hskip \@xdim                            
+%                                             OBJ \hss   }                      
+%         \@multicnt := \@multicnt - 1                                          
+%         \@xdim     := \@xdim + DELX * \unitlength                             
+%         \@ydim     := \@ydim + DELY * \unitlength                             
+%      od                                                                       
+%    \ignorespaces                                                              
+%   END                                                                         
+%                                                                               
+%  \shortstack[POS]{TEXT} : Makes a \vbox containing TEXT stacked as            
+%      a one-column array, positioned l, r or c as indicated by POS.            
+                                                                                
+\newdimen\@wholewidth                                                           
+\newdimen\@halfwidth                                                            
+\newdimen\unitlength \unitlength =1pt                                           
+\newbox\@picbox                                                                 
+\newdimen\@picht                                                                
+                                                                                
+\def\picture(#1,#2){\@ifnextchar({\@picture(#1,#2)}{\@picture(#1,#2)(0,0)}}     
+                                                                                
+\def\@picture(#1,#2)(#3,#4){\@picht #2\unitlength                               
+\setbox\@picbox\hbox to #1\unitlength\bgroup                                    
+\hskip -#3\unitlength \lower #4\unitlength \hbox\bgroup}                        
+                                                                                
+\def\endpicture{\egroup\hss\egroup\ht\@picbox\@picht                            
+\dp\@picbox\z@\leavevmode\box\@picbox}                                          
+                                                                                
+\long\def\put(#1,#2)#3{\@killglue\raise#2\unitlength\hbox to \z@{\hskip         
+#1\unitlength #3\hss}\ignorespaces}                                             
+                                                                                
+\long\def\multiput(#1,#2)(#3,#4)#5#6{\@killglue\@multicnt=#5\relax              
+\@xdim=#1\unitlength                                                            
+\@ydim=#2\unitlength                                                            
+\@whilenum \@multicnt > 0\do                                                    
+{\raise\@ydim\hbox to \z@{\hskip                                                
+\@xdim #6\hss}\advance\@multicnt \m@ne\advance\@xdim                            
+#3\unitlength\advance\@ydim #4\unitlength}\ignorespaces}                        
+                                                                                
+\def\@killglue{\unskip\@whiledim \lastskip >\z@\do{\unskip}}                    
+                                                                                
+\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc                      
+  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}                     
+\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw                   
+  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}                    
+                                                                                
+\def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth}          
+                                                                                
+\def\shortstack{\@ifnextchar[{\@shortstack}{\@shortstack[c]}}                   
+                                                                                
+\def\@shortstack[#1]{\leavevmode                                                
+\vbox\bgroup\baselineskip-1pt\lineskip 3pt\let\mb@l\hss                         
+\let\mb@r\hss \expandafter\let\csname mb@#1\endcsname\relax                     
+\let\\\@stackcr\@ishortstack}                                                   
+                                                                                
+\def\@ishortstack#1{\halign{\mb@l ##\unskip\mb@r\cr #1\crcr}\egroup}            
+                                                                                
+                                                                                
+\def\@stackcr{\@ifstar{\@ixstackcr}{\@ixstackcr}}                               
+\def\@ixstackcr{\@ifnextchar[{\@istackcr}{\cr\ignorespaces}}                    
+                                                                                
+\def\@istackcr[#1]{\cr\noalign{\vskip #1}\ignorespaces}                         
+                                                                                
+                                                                                
+% \line(X,Y){LEN} ==                                                            
+% BEGIN                                                                         
+%  \@xarg    := X                                                               
+%  \@yarg    := Y                                                               
+%  \@linelen := LEN * \unitlength                                               
+%  if \@xarg = 0                                                                
+%     then \@vline                                                              
+%     else if \@yarg = 0                                                        
+%            then \@hline                                                       
+%            else \@sline                                                       
+%          if                                                                   
+%  if                                                                           
+% END                                                                           
+%                                                                               
+% \@sline ==                                                                    
+%  BEGIN                                                                        
+%    if \@xarg < 0                                                              
+%      then @negarg := T                                                        
+%           \@xarg  := -\@xarg                                                  
+%           \@yyarg := -\@yarg                                                  
+%      else @negarg := F                                                        
+%           \@yyarg := \@yarg                                                   
+%    fi                                                                         
+%    \@tempcnta := |\@yyarg|                                                    
+%    if \@tempcnta > 6                                                          
+%      then error: 'LATEX ERROR: Illegal \line or \vector argument.'            
+%           \@tempcnta := 0                                                     
+%    fi                                                                         
+%    \box\@linechar := \hbox{\@linefnt \@getlinechar(\@xarg,\@yyarg) }          
+%     if \@yarg > 0 then \@upordown = \raise                                    
+%                         \@clnht := 0                                          
+%                   else \@upordown = \lower                                    
+%                        \@clnht := height of \box\@linechar                    
+%     fi                                                                        
+%     \@clnwd  := width of \box\@linechar                                       
+%     if @negarg                                                                
+%       then \hskip - width of \box\@linechar                                   
+%            \@tempa == \hskip - 2* width of box \@linechar                     
+%       else \@tempa == \relax                                                  
+%     fi                                                                        
+%  %% Put out integral number of line segments                                  
+%     while \@clnwd <  \@linelen                                                
+%       do  \@upordown \@clnht \copy\@linechar                                  
+%           \@tempa                                                             
+%           \@clnht := \@clnht + ht of \box\@linechar                           
+%           \@clnwd := \@clnwd + width of \box\@linechar                        
+%       od                                                                      
+%                                                                               
+%  %% Put out last segment                                                      
+%     \@clnht := \@clnht - height of \box\@linechar                             
+%     \@clnwd := \@clnwd - width of \box\@linechar                              
+%     \@tempdima   := \@linelen - \@clnwd                                       
+%     \@tempdimb   := \@tempdima - width of \box\@linechar                      
+%     if @negarg  then \hskip -\@tempdimb                                       
+%                 else \hskip  \@tempdimb                                       
+%     fi                                                                        
+%     \@tempdima   := 1000 * \@tempdima                                         
+%     \@tempcnta   := \@tempdima / width of \box\@linechar                      
+%     \@tempdima   := (\@tempcnta * ht of \box\@linechar)/1000                  
+%     \@clnht := \@clnht + \@tempdima                                           
+%     if \@linelen < width of box\@linechar                                     
+%         then \hskip width of box\@linechar                                    
+%         else \hbox{\@upordown \@clnht \copy\@linechar}                        
+%     fi                                                                        
+% END                                                                           
+%                                                                               
+% \@hline ==                                                                    
+%   BEGIN                                                                       
+%     if \@xarg < 0 then  \hskip -\@linelen \fi                                 
+%     \vrule height \@halfwidth depth \@halfwidth width \@linelen               
+%     if \@xarg < 0 then  \hskip -\@linelen \fi                                 
+%  END                                                                          
+%                                                                               
+% \@vline == if \@yarg < 0 \@downline else \@upline  fi                         
+%                                                                               
+%                                                                               
+% \@getlinechar(X,Y) ==                                                         
+%   BEGIN                                                                       
+%     \@tempcnta := 8*X - 9                                                     
+%     if Y > 0                                                                  
+%       then \@tempcnta := \@tempcnta + Y                                       
+%       else \@tempcnta := \@tempcnta - Y + 64                                  
+%     fi                                                                        
+%     \char\@tempcnta                                                           
+%   END                                                                         
+%                                                                               
+% \vector(X,Y){LEN} ==                                                          
+% BEGIN                                                                         
+%  \@xarg    := X                                                               
+%  \@yarg    := Y                                                               
+%  \@linelen := LEN * \unitlength                                               
+%  if \@xarg = 0                                                                
+%     then \@vvector                                                            
+%     else if \@yarg = 0                                                        
+%            then \@hvector                                                     
+%            else \@svector                                                     
+%          if                                                                   
+%  if                                                                           
+% END                                                                           
+%                                                                               
+% \@hvector ==                                                                  
+%   BEGIN                                                                       
+%     \@hline                                                                   
+%     {\@linefnt if \@xarg < 0 then  \@getlarrow(1,0)                           
+%                              else  \@getrarrow(1,0)                           
+%                 fi}                                                           
+%   END                                                                         
+%                                                                               
+% \@vvector == if \@yarg < 0 \@downvector else \@upvector  fi                   
+%                                                                               
+% \@svector ==                                                                  
+%  BEGIN                                                                        
+%   \@sline                                                                     
+%   \@tempcnta := |\@yarg|                                                      
+%     if  \@tempcnta < 5                                                        
+%        then  \hskip - width of \box\@linechar                                 
+%              \@upordown \@clnht \hbox                                         
+%                       {\@linefnt                                              
+%                        if @negarg then \@getlarrow(\@xarg,\@yyarg)            
+%                                   else \@getrarrow(\@xarg,\@yyarg)            
+%                        fi }                                                   
+%        else  error: 'LATEX ERROR: Illegal \line or \vector argument.'         
+%     fi                                                                        
+%  END                                                                          
+%                                                                               
+% \@getlarrow(X,Y) ==                                                           
+%  BEGIN                                                                        
+%   if Y = 0                                                                    
+%     then \@tempcnta := '33                                                    
+%     else \@tempcnta := 16 * X  -  9                                           
+%          \@tempcntb := 2 * Y                                                  
+%          if \@tempcntb > 0                                                    
+%            then  \@tempcnta := \@tempcnta  +  \@tempcntb                      
+%            else  \@tempcnta := \@tempcnta  -  \@tempcntb +  64                
+%          fi                                                                   
+%   fi                                                                          
+%   \char\@tempcnta                                                             
+%  END                                                                          
+%                                                                               
+% \@getrarrow(X,Y) ==                                                           
+%  BEGIN                                                                        
+%   \@tempcntb := |Y|                                                           
+%   case of \@tempcntb                                                          
+%     0 : \@tempcnta := '55                                                     
+%     1 : if X < 3                                                              
+%           then \@tempcnta :=  24*X - 6                                        
+%           else if X = 3                                                       
+%                  then \@tempcnta := 49                                        
+%                  else \@tempcnta := 58  fi                                    
+%         fi                                                                    
+%     2 : if X < 3                                                              
+%           then \@tempcnta :=  24*X - 3                                        
+%           else \@tempcnta := 51     % X must = 3                              
+%         fi                                                                    
+%     3 : \@tempcnta := 16*X - 2                                                
+%     4 : \@tempcnta := 16*X + 7                                                
+%   endcase                                                                     
+%   if Y < 0                                                                    
+%     then \@tempcnta := \@tempcnta + 64                                        
+%   fi                                                                          
+%   \char\@tempcnta                                                             
+%  END                                                                          
+                                                                                
+\newif\if@negarg                                                                
+                                                                                
+\def\line(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax                              
+\@linelen=#3\unitlength                                                         
+\ifnum\@xarg =0 \@vline                                                         
+  \else \ifnum\@yarg =0 \@hline \else \@sline\fi                                
+\fi}                                                                            
+                                                                                
+\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg         
+  \else \@negargfalse \@yyarg \@yarg \fi                                        
+\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi               
+\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi                                  
+\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%                 
+\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@                                
+   \else\let\@upordown\lower \@clnht \ht\@linechar\fi                           
+\@clnwd=\wd\@linechar                                                           
+\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else       
+     \let\@tempa\relax \fi                                                      
+\@whiledim \@clnwd <\@linelen \do                                               
+  {\@upordown\@clnht\copy\@linechar                                             
+   \@tempa                                                                      
+   \advance\@clnht \ht\@linechar                                                
+   \advance\@clnwd \wd\@linechar}%                                              
+\advance\@clnht -\ht\@linechar                                                  
+\advance\@clnwd -\wd\@linechar                                                  
+\@tempdima\@linelen\advance\@tempdima -\@clnwd                                  
+\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar                           
+\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi                       
+\multiply\@tempdima \@m                                                         
+\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima     
+\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta                         
+\divide\@tempdima \@m                                                           
+\advance\@clnht \@tempdima                                                      
+\ifdim \@linelen <\wd\@linechar                                                 
+   \hskip \wd\@linechar                                                         
+  \else\@upordown\@clnht\copy\@linechar\fi}                                     
+                                                                                
+\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi                              
+\vrule \@height \@halfwidth \@depth \@halfwidth \@width \@linelen               
+\ifnum \@xarg <0 \hskip -\@linelen \fi}                                         
+                                                                                
+\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8                
+\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else              
+\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi                           
+\char\@tempcnta}                                                                
+                                                                                
+\def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax                            
+\@linelen=#3\unitlength                                                         
+\ifnum\@xarg =0 \@vvector                                                       
+  \else \ifnum\@yarg =0 \@hvector \else \@svector\fi                            
+\fi}                                                                            
+                                                                                
+\def\@hvector{\@hline\hbox to 0pt{\@linefnt                                     
+\ifnum \@xarg <0 \@getlarrow(1,0)\hss\else                                      
+    \hss\@getrarrow(1,0)\fi}}                                                   
+                                                                                
+\def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi}               
+                                                                                
+\def\@svector{\@sline                                                           
+\@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi                  
+\ifnum\@tempcnta <5                                                             
+  \hskip -\wd\@linechar                                                         
+  \@upordown\@clnht \hbox{\@linefnt  \if@negarg                                 
+  \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}%           
+\else\@badlinearg\fi}                                                           
+                                                                                
+\def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else                       
+\@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta              
+-9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@                                  
+\ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax                        
+\else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64                        
+\fi\fi\char\@tempcnta}                                                          
+                                                                                
+\def\@getrarrow(#1,#2){\@tempcntb=#2\relax                                      
+\ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi                            
+\ifcase \@tempcntb\relax \@tempcnta='55 \or                                     
+\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta                              
+24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49                        
+\else\@tempcnta=58 \fi\fi\or                                                    
+\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta                              
+24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or                              
+\@tempcnta=#1\relax\multiply\@tempcnta                                          
+\sixt@@n \advance\@tempcnta -\tw@ \else                                         
+\@tempcnta=#1\relax\multiply\@tempcnta                                          
+\sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi          
+\char\@tempcnta}                                                                
+                                                                                
+                                                                                
+                                                                                
+\def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi}                      
+                                                                                
+\def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule \@width \@wholewidth       
+   \@height \@linelen \@depth \z@\hss}}                                         
+                                                                                
+\def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule \@width \@wholewidth     
+   \@height \z@ \@depth \@linelen \hss}}                                        
+                                                                                
+\def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise          
+     \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}}             
+                                                                                
+\def\@downvector{\@downline\lower \@linelen                                     
+      \hbox to \z@{\@linefnt\char'77\hss}}                                      
+                                                                                
+% \dashbox{D}(X,Y) ==                                                           
+%  BEGIN                                                                        
+%  leave vertical mode                                                          
+%  \hbox to 0pt {                                                               
+%       \baselineskip := 0pt                                                    
+%       \lineskip     := 0pt                                                    
+%  %% HORIZONTAL DASHES                                                         
+%       \@dashdim := X * \unitlength                                            
+%       \@dashcnt := \@dashdim + 200 % to prevent roundoff error                
+%       \@dashdim := D * \unitlength                                            
+%       \@dashcnt := \@dashcnt / \@dashdim                                      
+%       if \@dashcnt is odd                                                     
+%         then \@dashdim := 0pt                                                 
+%              \@dashcnt := (\@dashcnt + 1) / 2                                 
+%         else \@dashdim := \@dashdim / 2                                       
+%              \@dashcnt := \@dashcnt / 2 - 1                                   
+%              \box\@dashbox   := \hbox{\vrule height \@halfwidth               
+%                                    depth \@halfwidth width \@dashdim}         
+%              \put(0,0){\copy\@dashbox}                                        
+%              \put(0,Y){\copy\@dashbox}                                        
+%              \put(X,0){\hskip -\@dashdim\copy\@dashbox}                       
+%              \put(X,Y){\hskip -\@dashdim\box\@dashbox}                        
+%              \@dashdim := 3 * \@dashdim                                       
+%       fi                                                                      
+%       \box\@dashbox := \hbox{\vrule height \@halfwidth                        
+%                                 depth \@halfwidth width D * \unitlength       
+%                              \hskip D * \unitlength}                          
+%       \@tempcnta := 0                                                         
+%       \put(0,0){\hskip \@dashdim                                              
+%                while \@tempcnta < \@dascnt                                    
+%                  do \copy\@dashbox                                            
+%                     \@tempcnta := \@tempcnta + 1                              
+%                  od                                                           
+%               }                                                               
+%       \@tempcnta := 0                                                         
+%       put(0,Y){\hskip \@dashdim                                               
+%                while \@tempcnta < \@dascnt                                    
+%                  do \copy\@dashbox                                            
+%                     \@tempcnta := \@tempcnta + 1                              
+%                  od                                                           
+%               }                                                               
+%                                                                               
+% %% vertical dashes                                                            
+%       \@dashdim := Y * \unitlength                                            
+%       \@dashcnt := \@dashdim + 200 % to prevent roundoff error                
+%       \@dashdim := D * \unitlength                                            
+%       \@dashcnt := \@dashcnt / \@dashdim                                      
+%       if \@dashcnt is odd                                                     
+%         then \@dashdim := 0pt                                                 
+%              \@dashcnt := (\@dashcnt + 1) / 2                                 
+%         else \@dashdim := \@dashdim / 2                                       
+%              \@dashcnt := \@dashcnt / 2 - 1                                   
+%              \box\@dashbox   := \hbox{\hskip -\@halfwidth                     
+%                                       \vrule width \@wholewidth               
+%                                                height \@dashdim  }            
+%              \put(0,0){\copy\@dashbox}                                        
+%              \put(X,0){\copy\@dashbox}                                        
+%              \put(0,Y){\lower\@dashdim\copy\@dashbox}                         
+%              \put(X,Y){\lower\@dashdim\copy\@dashbox}                         
+%              \@dashdim := 3 * \@dashdim                                       
+%       fi                                                                      
+%       \box\@dashbox := \hbox{\vrule width \@wholewidth                        
+%                                 height D * \unitlength       }                
+%       \@tempcnta := 0                                                         
+%       put(0,0){\hskip -\halfwidth                                             
+%                \vbox{while \@tempcnta < \@dashcnt                             
+%                       do \vskip D*\unitlength                                 
+%                          \copy\@dashbox                                       
+%                          \@tempcnta := \@tempcnta + 1                         
+%                       od                                                      
+%                      \vskip \@dashdim                                         
+%                     } }                                                       
+%       \@tempcnta := 0                                                         
+%       put(X,0){\hskip -\halfwidth                                             
+%                \vbox{while \@tempcnta < \@dashcnt                             
+%                       do \vskip D*\unitlength                                 
+%                          \copy\@dashbox                                       
+%                          \@tempcnta := \@tempcnta + 1                         
+%                       od                                                      
+%                      \vskip \@dashdim                                         
+%                     }                                                         
+%               }                                                               
+%    }     % END DASHES                                                         
+%                                                                               
+%  \@imakepicbox(X,Y)                                                           
+% END                                                                           
+                                                                                
+\def\dashbox#1(#2,#3){\leavevmode\hbox to \z@{\baselineskip \z@%                
+\lineskip \z@%                                                                  
+\@dashdim=#2\unitlength%                                                        
+\@dashcnt=\@dashdim \advance\@dashcnt 200                                       
+\@dashdim=#1\unitlength\divide\@dashcnt \@dashdim                               
+\ifodd\@dashcnt\@dashdim=\z@%                                                   
+\advance\@dashcnt \@ne \divide\@dashcnt \tw@                                    
+\else \divide\@dashdim \tw@ \divide\@dashcnt \tw@                               
+\advance\@dashcnt \m@ne                                                         
+\setbox\@dashbox=\hbox{\vrule \@height \@halfwidth \@depth \@halfwidth          
+\@width \@dashdim}\put(0,0){\copy\@dashbox}%                                    
+\put(0,#3){\copy\@dashbox}%                                                     
+\put(#2,0){\hskip-\@dashdim\copy\@dashbox}%                                     
+\put(#2,#3){\hskip-\@dashdim\box\@dashbox}%                                     
+\multiply\@dashdim 3                                                            
+\fi                                                                             
+\setbox\@dashbox=\hbox{\vrule \@height \@halfwidth \@depth \@halfwidth          
+\@width #1\unitlength\hskip #1\unitlength}\@tempcnta=0                          
+\put(0,0){\hskip\@dashdim \@whilenum \@tempcnta <\@dashcnt                      
+\do{\copy\@dashbox\advance\@tempcnta \@ne }}\@tempcnta=0                        
+\put(0,#3){\hskip\@dashdim \@whilenum \@tempcnta <\@dashcnt                     
+\do{\copy\@dashbox\advance\@tempcnta \@ne }}%                                   
+\@dashdim=#3\unitlength%                                                        
+\@dashcnt=\@dashdim \advance\@dashcnt 200                                       
+\@dashdim=#1\unitlength\divide\@dashcnt \@dashdim                               
+\ifodd\@dashcnt \@dashdim=\z@%                                                  
+\advance\@dashcnt \@ne \divide\@dashcnt \tw@                                    
+\else                                                                           
+\divide\@dashdim \tw@ \divide\@dashcnt \tw@                                     
+\advance\@dashcnt \m@ne                                                         
+\setbox\@dashbox\hbox{\hskip -\@halfwidth                                       
+\vrule \@width \@wholewidth                                                     
+\@height \@dashdim}\put(0,0){\copy\@dashbox}%                                   
+\put(#2,0){\copy\@dashbox}%                                                     
+\put(0,#3){\lower\@dashdim\copy\@dashbox}%                                      
+\put(#2,#3){\lower\@dashdim\copy\@dashbox}%                                     
+\multiply\@dashdim 3                                                            
+\fi                                                                             
+\setbox\@dashbox\hbox{\vrule \@width \@wholewidth                               
+\@height #1\unitlength}\@tempcnta0                                              
+\put(0,0){\hskip -\@halfwidth \vbox{\@whilenum \@tempcnta < \@dashcnt           
+\do{\vskip #1\unitlength\copy\@dashbox\advance\@tempcnta \@ne }%                
+\vskip\@dashdim}}\@tempcnta0                                                    
+\put(#2,0){\hskip -\@halfwidth \vbox{\@whilenum \@tempcnta< \@dashcnt           
+\relax\do{\vskip #1\unitlength\copy\@dashbox\advance\@tempcnta \@ne }%          
+\vskip\@dashdim}}}\@makepicbox(#2,#3)}                                          
+                                                                                
+% CIRCLES AND OVALS                                                             
+%                                                                               
+%  USER COMMANDS:                                                               
+%                                                                               
+%  \circle{D} : Produces the circle with the diameter as close as               
+%               possible to D * \unitlength.  \put(X,Y){\circle{D}}             
+%               puts the circle with its center at (X,Y).                       
+%                                                                               
+%  \oval(X,Y) : Makes an oval as round as possible that fits in the             
+%               rectangle of width X * \unitlength and height                   
+%               Y * \unitlength. The reference point is the center.             
+%                                                                               
+% \oval(X,Y)[POS] : Save as \oval(X,Y) except it draws only the                 
+%                   half or quadrant of the oval indicated by POS.              
+%                   E.G., \oval(X,Y)[t] draws just the top half                 
+%                   and \oval(X,Y)[br] draws just the bottom right              
+%                   quadrant.  In all cases, the reference point is             
+%                   the same as the unqualified \oval(X,Y) command.             
+%                                                                               
+% \@ovvert {DELTA1} {DELTA2} : Makes a vbox containing either the left side     
+%        or the right side of the oval being constructed.  The baseline         
+%        will coincide with the outside bottom edge of the oval; the left       
+%        side of the box will coincide with the left edge of the vertical       
+%        rule.  The width of the box will be \@tempdima.                        
+%        DELTA1 and DELTA2 are added to the character number in \@tempcnta      
+%        to get the characters for the top and bottom quarter circle pieces.    
+%                                                                               
+% \@ovhorz : Makes an hbox containing the straight rule for either the          
+%         top or the bottom of the oval being constructed.  The baseline        
+%         will coincide with bottom edge of the rule; the left side of          
+%         the box will coincide with the left side of the oval.                 
+%         The width of the box will be \@ovxx.                                  
+%                                                                               
+% \@getcirc {DIAM} : Sets \@tempcnta to the character number                    
+%                   of the top-right quarter circle with the largest            
+%                   diameter less than or equal to DIAM.                        
+%                   Sets \@tempboxa to an hbox containing that character.       
+%                   Sets \@tempdima to \wd \@tempboxa, which is the distance    
+%                   from the circle's left outside edge to its right            
+%                   inside edge.                                                
+%                   (These characters are like those described in the           
+%                   TeXbook, pp. 389-90.)                                       
+%                                                                               
+% \@getcirc {DIAM} ==                                                           
+%   BEGIN                                                                       
+%     \@tempcnta       := integer coercion of DIAM                              
+%     \@tempcnta       := \@tempcnta / integer coercion of 4pt                  
+%     if \@tempcnta > 10                                                        
+%       then \@tempcnta := 10 fi                                                
+%     if \@tempcnta > 0                                                         
+%       then \@tempcnta := \@tempcnta-1                                         
+%       else LaTeX Warning: Oval too small.                                     
+%     fi                                                                        
+%     \@tempcnta       := 4 * \@tempcnta                                        
+%     \@tempboxa       := \hbox{\@circlefnt \char \@tempcnta}                   
+%     \@tempdima       := \wd \@tempboxa                                        
+%   END                                                                         
+%                                                                               
+% \@put{X}{Y}{OBJ} ==                                                           
+%   BEGIN                                                                       
+%     \raise Y \hbox to 0pt{\hskip X OBJ \hss}                                  
+%   END                                                                         
+%                                                                               
+% \@oval(X,Y)[POS] ==                                                           
+%   BEGIN                                                                       
+%     \begingroup                                                               
+%	\boxmaxdepth := \maxdimen                                                     
+%       @ovt := @ovb := @ovl := @ovr := true                                    
+%       for all E in POS                                                        
+%         do  @ovE := false od                                                  
+%       \@ovxx      := X * \unitlength                                          
+%       \@ovyy      := Y * \unitlength                                          
+%       \@tempdimb := min(\@ovxx,\@ovyy)                                        
+%       \@getcirc{\@tempdimb}                                                   
+%       \@ovro     := \ht \@tempboxa                                            
+%       \@ovri     := \dp \@tempboxa                                            
+%       \@ovdx     := \@ovxx - \@tempdima                                       
+%       \@ovdx     := \@ovdx/2                                                  
+%       \@ovdy     := \@ovyy - \@tempdima                                       
+%       \@ovdy     := \@ovyy/2                                                  
+%       \@circlefnt                                                             
+%       \@tempboxa :=                                                           
+%           \hbox{                                                              
+%                 if @ovr                                                       
+%                   then \@ovvert{3}{2} \kern -\@tempdima                       
+%                 fi                                                            
+%                 if @ovl                                                       
+%                   then \kern \@ovxx \@ovvert{0}{1} \kern -\@tempdima          
+%                        \kern -\@ovxx                                          
+%                 fi                                                            
+%                 if @ovt                                                       
+%                   then \@ovhorz \kern -\@ovxx                                 
+%                 fi                                                            
+%                 if @ovb                                                       
+%                   then \raise \@ovyy \@ovhorz                                 
+%                 fi                                                            
+%                }                                                              
+%       \@ovdx    := \@ovdx + \@ovro                                            
+%       \@ovdy    := \@ovdy + \@ovro                                            
+%      \ht\@tempboxa := \dp\@tempboxa := 0                                      
+%       \@put{-\@ovdx}{-\@ovdy}{\box\@tempboxa}                                 
+%    \endgroup                                                                  
+%   END                                                                         
+%                                                                               
+% \@ovvert {DELTA1} {DELTA2} ==                                                 
+%   BEGIN                                                                       
+%      \vbox to \@ovyy {                                                        
+%                      if @ovb                                                  
+%                        then \@tempcntb := \@tempcnta + DELTA1                 
+%                             \kern -\@ovro                                     
+%                             \hbox { \char \@tempcntb }                        
+%                             \nointerlineskip                                  
+%                        else \kern \@ovri \kern \@ovdy                         
+%                      fi                                                       
+%                      \leaders \vrule width \@wholewidth \vfil                 
+%                      \nointerlineskip                                         
+%                      if @ovt                                                  
+%                        then \@tempcntb := \@tempcnta + DELTA2                 
+%                             \hbox { \char \@tempcntb }                        
+%                        else \kern \@ovdy \kern \@ovro                         
+%                      fi                                                       
+%                     }                                                         
+%   END                                                                         
+%                                                                               
+% \@ovhorz ==                                                                   
+%   BEGIN                                                                       
+%    \hbox to \@ovxx{                                                           
+%                   \kern \@ovro                                                
+%                   if @ovr                                                     
+%                     then                                                      
+%                     else \kern \@ovdx                                         
+%                   fi                                                          
+%                   \leaders \hrule height \@wholewidth \hfil                   
+%                   if @ovl                                                     
+%                     then                                                      
+%                     else \kern \@ovdx                                         
+%                   fi                                                          
+%                   \kern \@ovri                                                
+%                  }                                                            
+%   END                                                                         
+%                                                                               
+% \circle{DIAM} ==                                                              
+%   BEGIN                                                                       
+%    \begingroup                                                                
+%    \boxmaxdepth := maxdimen                                                   
+%    \@tempdimb := DIAM *\unitlength                                            
+%    if \@tempdimb > 15.5pt                                                     
+%      then \@getcirc{\@tempdimb}                                               
+%           \@ovro := \ht \@tempboxa                                            
+%           \@tempboxa := \hbox{                                                
+%                   \@circlefnt                                                 
+%                   \@tempcnta := \@tempcnta + 2                                
+%                   \char \@tempcnta                                            
+%                   \@tempcnta := \@tempcnta - 1                                
+%                   \char \@tempcnta                                            
+%                   \kern -2\@tempdima                                          
+%                   \@tempcnta := \@tempcnta + 2                                
+%                   \raise \@tempdima \hbox { \char \@tempcnta }                
+%                   \raise \@tempdima \box\@tempboxa                            
+%                  }                                                            
+%           \ht\@tempboxa := \dp\@tempboxa := 0                                 
+%           \@put{-\@ovro}{-\@ovro}{\@tempboxa}                                 
+%      else                                                                     
+%           \@circ{\@tempdimb}{96}                                              
+%    fi                                                                         
+%   \endgroup                                                                   
+%   END                                                                         
+%                                                                               
+% \circle*{DIAM}  ==  \@dot{DIAM} == \@circ{DIAM*\unitlength}{112}              
+%                                                                               
+% \@circ{DIAM}{CHAR} ==                                                         
+%  BEGIN                                                                        
+%   \@tempcnta := integer coercion of (DIAM + .5pt)/1pt.                        
+%   if \@tempcnta > 15 then \@tempcnta := 15 fi                                 
+%   if \@tempcnta > 1  then \@tempcnta := \@tempcnta - 1 fi                     
+%   \@tempcnta := \@tempcnta + CHAR                                             
+%   \@circlefnt                                                                 
+%   \char \@tempcnta                                                            
+%  END                                                                          
+%                                                                               
+                                                                                
+\newif\if@ovt                                                                   
+\newif\if@ovb                                                                   
+\newif\if@ovl                                                                   
+\newif\if@ovr                                                                   
+\newdimen\@ovxx                                                                 
+\newdimen\@ovyy                                                                 
+\newdimen\@ovdx                                                                 
+\newdimen\@ovdy                                                                 
+\newdimen\@ovro                                                                 
+\newdimen\@ovri                                                                 
+                                                                                
+\def\@getcirc#1{\@tempdima #1\relax \@tempcnta\@tempdima                        
+  \@tempdima 4pt\relax \divide\@tempcnta\@tempdima                              
+  \ifnum \@tempcnta > 10\relax \@tempcnta 10\relax\fi                           
+  \ifnum \@tempcnta >\z@ \advance\@tempcnta\m@ne                                
+    \else \@warning{Oval too small}\fi                                          
+  \multiply\@tempcnta 4\relax                                                   
+  \setbox \@tempboxa \hbox{\@circlefnt                                          
+  \char \@tempcnta}\@tempdima \wd \@tempboxa}                                   
+                                                                                
+\def\@put#1#2#3{\raise #2\hbox to \z@{\hskip #1#3\hss}}                         
+                                                                                
+\def\oval(#1,#2){\@ifnextchar[{\@oval(#1,#2)}{\@oval(#1,#2)[]}}                 
+                                                                                
+\def\@oval(#1,#2)[#3]{\begingroup\boxmaxdepth \maxdimen                         
+  \@ovttrue \@ovbtrue \@ovltrue \@ovrtrue                                       
+  \@tfor\@tempa :=#3\do{\csname @ov\@tempa false\endcsname}\@ovxx               
+  #1\unitlength \@ovyy #2\unitlength                                            
+  \@tempdimb \ifdim \@ovyy >\@ovxx \@ovxx\else \@ovyy \fi                       
+  \@getcirc \@tempdimb                                                          
+  \@ovro \ht\@tempboxa \@ovri \dp\@tempboxa                                     
+  \@ovdx\@ovxx \advance\@ovdx -\@tempdima \divide\@ovdx \tw@                    
+  \@ovdy\@ovyy \advance\@ovdy -\@tempdima \divide\@ovdy \tw@                    
+  \@circlefnt \setbox\@tempboxa                                                 
+  \hbox{\if@ovr \@ovvert32\kern -\@tempdima \fi                                 
+  \if@ovl \kern \@ovxx \@ovvert01\kern -\@tempdima \kern -\@ovxx \fi            
+  \if@ovt \@ovhorz \kern -\@ovxx \fi                                            
+  \if@ovb \raise \@ovyy \@ovhorz \fi}\advance\@ovdx\@ovro                       
+  \advance\@ovdy\@ovro \ht\@tempboxa\z@ \dp\@tempboxa\z@                        
+  \@put{-\@ovdx}{-\@ovdy}{\box\@tempboxa}%                                      
+  \endgroup}                                                                    
+                                                                                
+\def\@ovvert#1#2{\vbox to \@ovyy{%                                              
+    \if@ovb \@tempcntb \@tempcnta \advance \@tempcntb by #1\relax               
+	\kern -\@ovro \hbox{\char \@tempcntb}\nointerlineskip                          
+    \else \kern \@ovri \kern \@ovdy \fi                                         
+    \leaders\vrule width \@wholewidth\vfil \nointerlineskip                     
+    \if@ovt \@tempcntb \@tempcnta \advance \@tempcntb by #2\relax               
+	\hbox{\char \@tempcntb}%                                                       
+    \else \kern \@ovdy \kern \@ovro \fi}}                                       
+                                                                                
+\def\@ovhorz{\hbox to \@ovxx{\kern \@ovro                                       
+    \if@ovr \else \kern \@ovdx \fi                                              
+    \leaders \hrule height \@wholewidth \hfil                                   
+    \if@ovl \else \kern \@ovdx \fi                                              
+    \kern \@ovri}}                                                              
+                                                                                
+\def\circle{\@ifstar{\@dot}{\@circle}}                                          
+\def\@circle#1{\begingroup \boxmaxdepth \maxdimen \@tempdimb #1\unitlength      
+   \ifdim \@tempdimb >15.5pt\relax \@getcirc\@tempdimb                          
+      \@ovro\ht\@tempboxa                                                       
+     \setbox\@tempboxa\hbox{\@circlefnt                                         
+      \advance\@tempcnta\tw@ \char \@tempcnta                                   
+      \advance\@tempcnta\m@ne \char \@tempcnta \kern -2\@tempdima               
+      \advance\@tempcnta\tw@                                                    
+      \raise \@tempdima \hbox{\char\@tempcnta}\raise \@tempdima                 
+        \box\@tempboxa}\ht\@tempboxa\z@ \dp\@tempboxa\z@                        
+      \@put{-\@ovro}{-\@ovro}{\box\@tempboxa}%                                  
+   \else  \@circ\@tempdimb{96}\fi\endgroup}                                     
+                                                                                
+\def\@dot#1{\@tempdimb #1\unitlength \@circ\@tempdimb{112}}                     
+                                                                                
+\def\@circ#1#2{\@tempdima #1\relax \advance\@tempdima .5pt\relax                
+   \@tempcnta\@tempdima \@tempdima 1pt\relax                                    
+   \divide\@tempcnta\@tempdima                                                  
+   \ifnum\@tempcnta > 15\relax \@tempcnta 15\relax \fi                          
+   \ifnum \@tempcnta >\z@ \advance\@tempcnta\m@ne\fi                            
+   \advance\@tempcnta #2\relax                                                  
+   \@circlefnt \char\@tempcnta}                                                 
+                                                                                
+                                                                                
+%INITIALIZATION                                                                 
+\thinlines                                                                      
+                                                                                
+\newcount\@xarg                                                                 
+\newcount\@yarg                                                                 
+\newcount\@yyarg                                                                
+\newcount\@multicnt                                                             
+\newdimen\@xdim                                                                 
+\newdimen\@ydim                                                                 
+\newbox\@linechar                                                               
+\newdimen\@linelen                                                              
+\newdimen\@clnwd                                                                
+\newdimen\@clnht                                                                
+\newdimen\@dashdim                                                              
+\newbox\@dashbox                                                                
+\newcount\@dashcnt                                                              
+                                                                                
+                                                                                
+                                                                                
+%                                                                               
+
diff --git a/macros/plain/contrib/treetex/readme b/macros/plain/contrib/treetex/readme
new file mode 100644
index 0000000000..575afc2fe0
--- /dev/null
+++ b/macros/plain/contrib/treetex/readme
@@ -0,0 +1,19 @@
+TreeTeX is a public domain macro package for drawing
+trees with TeX. It may be freely distributed, provided
+that the following files are kept together:
+
+  README epodd.bbl epodd.tex tree_doc.bbl tree_doc.tex
+  classes.tex l_pic.tex treetex.tex
+
+Copyright is with Anne Brueggemann-Klein and Derick Wood.
+
+All remarks, bug reports etc. should be directed to
+
+  Dr. Anne Brueggemann-Klein
+  Institut fuer Informatik
+  Rheinstr. 10--12
+  7800 Freiburg, West Germany
+
+  email: abk@sun1.ruf.uni-freiburg.dbp.de
+
+
diff --git a/macros/plain/contrib/treetex/tree_doc.bbl b/macros/plain/contrib/treetex/tree_doc.bbl
new file mode 100644
index 0000000000..88c540ee0b
--- /dev/null
+++ b/macros/plain/contrib/treetex/tree_doc.bbl
@@ -0,0 +1,97 @@
+\begin{thebibliography}{10}                                                     
+                                                                                
+\bibitem{Tables}                                                                
+R.~J. Beach.                                                                    
+\newblock {\it Setting Tables and Illustrations with Style}.                    
+\newblock PhD thesis, University of Waterloo, 1985.                             
+                                                                                
+\bibitem{Karlsruhe}                                                             
+A. Br{\"u}ggemann-Klein, P. Dolland, and A. Heinz.                              
+\newblock How to please authors and publishers: a versatile document            
+  preparation system at {K}arlsruhe.                                            
+\newblock In J. D\'esarm\'enien, editor, {\it {\TeX{}} for Scientific           
+  Documentation}, Strasbourg, France, June 1986.                                
+\newblock LNCS~236.                                                             
+                                                                                
+\bibitem{TreeTeX}                                                               
+A. Br{\"u}ggemann-Klein and D. Wood.                                            
+\newblock {\it Tree{\TeX}: Documentation and User Handbook}.                    
+\newblock Technical Report, University of Waterloo, 1987.                       
+                                                                                
+\bibitem{AverageHeight}                                                         
+N.G. de~Bruijn, D. Knuth, and S.O. Rice.                                        
+\newblock The average height of planted plane trees.                            
+\newblock In R.C. Read, editor, {\it Graph Theory and Computing}, 1972.         
+                                                                                
+\bibitem{BinarySearchTrees}                                                     
+L. Devroye.                                                                     
+\newblock A note on the height of binary search trees.                          
+\newblock {\it Journal of the ACM}, 33(3), July 1986.                           
+                                                                                
+\bibitem{BinaryTrees}                                                           
+Ph. Flajolet and A. Odlyzko.                                                    
+\newblock The average height of binary trees and other simple trees.            
+\newblock {\it Journal of Computer and System Sciences}, 25, 1982.              
+                                                                                
+\bibitem{DocumentFormatting}                                                    
+R. Furuta, J. Scofield, and A. Shaw.                                            
+\newblock Document formatting systems: surveys, concepts, issues.               
+\newblock {\it Computing Surveys}, 14(3), 1982.                                 
+                                                                                
+\bibitem{GML}                                                                   
+Ch.~F. Goldfarb.                                                                
+\newblock A generalized approach to document markup.                            
+\newblock {\it SIGPLAN Notices of the ACM}, June 1981.                          
+                                                                                
+\bibitem{ACP}                                                                   
+D.~E. Knuth.                                                                    
+\newblock {\it Fundamental Algorithms}.                                         
+\newblock Volume~1 of {\it The Art of Computer Programming}, Addison-Wesley,    
+  Reading, Massachusetts, 1973.                                                 
+                                                                                
+\bibitem{TeXbook}                                                               
+D.~E. Knuth.                                                                    
+\newblock {\it The {\TeX{}}book}.                                               
+\newblock Volume~A of {\it Computers \& Typesetting}, Addison-Wesley, Reading,  
+  Massachusetts, 1986.                                                          
+                                                                                
+\bibitem{LaTeX}                                                                 
+L. Lamport.                                                                     
+\newblock {\it {\LaTeX}, User's Guide \& Reference Manual}.                     
+\newblock Addison-Wesley, Reading, Massachusetts, 1986.
+ 
+\bibitem{Brother}
+Th. Ottmann, H.-W. Six.
+\newblock Eine neue Klasse ausgeglichener Bin\"arb\"aume.
+\newblock {\it Angewandte Informatik}, 9, 1976.                         
+                                                                                
+\bibitem{Grif}                                                                  
+V. Quint, I. Vatton, and H. Bedor.                                              
+\newblock Grif: an interactive environment for {\TeX{}}.                        
+\newblock In J. D\'esarm\'enien, editor, {\it {\TeX{}} for Scientific           
+  Documentation}, Strasbourg, France, June 1986.                                
+\newblock LNCS~236.                                                             
+                                                                                
+\bibitem{Scribe}                                                                
+B.~K. Reid.                                                                     
+\newblock {\it Scribe: A Document Specification Language and its Compiler}.     
+\newblock PhD thesis, Carnegie Mellon University, 1980.                         
+                                                                                
+\bibitem{TidierTrees}                                                           
+E.~M. Reingold and J.~S. Tilford.                                               
+\newblock Tidier drawings of tree.                                              
+\newblock {\it IEEE Transactions on Software Engineering}, 7(2), March 1981.    
+                                                                                
+\bibitem{Complexity}                                                            
+K.~J. Supowit and E.~M. Reingold.                                               
+\newblock The complexity of drawing trees nicely.                               
+\newblock {\it Acta Informatica}, 18, 1983.                                     
+                                                                                
+\bibitem{TidyTrees}                                                             
+Ch. Wetherell and A. Shannon.                                                   
+\newblock Tidy drawings of trees.                                               
+\newblock {\it IEEE Transactions on Software Engineering}, 5(5), September      
+  1979.                                                                         
+                                                                                
+\end{thebibliography}                                                           
+                                                                                
diff --git a/macros/plain/contrib/treetex/tree_doc.tex b/macros/plain/contrib/treetex/tree_doc.tex
new file mode 100644
index 0000000000..8746ff12f5
--- /dev/null
+++ b/macros/plain/contrib/treetex/tree_doc.tex
@@ -0,0 +1,1331 @@
+% This is tree_doc.tex, the documentation for the treetex macro package
+% as it will appear in the conference proceedings of the third European
+% TeX meeting in Exeter, England, 1988.
+
+\documentstyle[12pt,DIN-A4]{article} 
+
+\advance\voffset by -2cm                                           
+                                                                                
+\clubpenalty=10000                                                              
+\widowpenalty=10000                                                             
+\def\addcontentsline#1#2#3{\relax}% Some captions are too long for some
+     % TeX installations (buffer size too small)
+
+                                                                                
+\newenvironment{lemma}{\begingroup\samepage\begin{lemmma}\ }{\end{lemmma}%      
+     \endgroup}                                                                 
+\newtheorem{lemmma}{Lemma}[section]                                             
+\newenvironment{proof}{\begin{prooof}\rm\ \nopagebreak}{\end{prooof}}           
+\newcommand{\proofend}{\qquad\ifmmode\Box\else$\Box$\fi}                        
+\newtheorem{prooof}{Proof}                                                      
+\renewcommand{\theprooof}{}   % makes shure that prooof doesn't get numbers       
+\newenvironment{Figure}{\begin{figure}\vspace{1\baselineskip}}%                 
+                       {\vspace{1\baselineskip}\end{figure}}                    
+\newlength{\figspace}         % space between figures in a single               
+\setlength{\figspace}{30pt}   % Figure environment                              
+                                                                                
+\newcommand{\var}[1]{{\it #1\/}}     % use it for names of variables            
+\newcommand{\emph}[1]{{\em #1\/}}    % use it for emphazided text               
+                                     % (This notion sticks to the               
+                                     % applicative style of markup.)            
+\renewcommand{\O}{{\rm O}}           % O-notation, also for math mode           
+\newcommand{\T}{{\cal T}}            % the set T in math mode                   
+\newcommand{\TreeTeX}{Tree\TeX}                                                 
+\newcommand{\fig}[1]{Figure~\ref{#1}}                                           
+\let\p\par                                                                      
+                                                                                
+\input TreeTeX                                    
+\Treestyle{\vdist{20pt}\minsep{16pt}}                                                        
+\dummyhalfcenterdim@n=2pt                                                       
+                                                                                
+\def\Node(#1,#2){\put(#1,#2){\circle*{4}}}                                      
+\def\Edge(#1,#2,#3,#4,#5){\put(#1,#2){\line(#3,#4){#5}}}                        
+                                                                                
+\def\enode{\node{\external\type{dot}}}                                          
+\def\inode{\node{\type{dot}}}                                                   
+                                                                                
+\def\e{\node{\external\type{dot}}}                                              
+\def\i{\node{\type{dot}}}                                                       
+\def\il{\node{\type{dot}\leftonly}}                                             
+\def\ir{\node{\type{dot}\rightonly}}                                            
+                                                                                
+\newcommand{\stack}[3]{%                                                        
+     \vtop{\settowidth{\hsize}{#1}%                                             
+     \setlength{\leftskip}{0pt plus 1fill}%                                     
+     \setlength{\baselineskip}{#2}#3}}                                          
+                                                                                
+\let\multic\multicolumn                                                         
+                                                                                
+\newlength{\hd} % hidden digit                                                  
+\setbox0\hbox{1}                                                                
+\settowidth{\hd}{\usebox{0}}                                                    
+\newcommand{\ds}{\hspace{\hd}} % digit space                                    
+                                                                                
+\newcommand{\ccol}[1]{\multicolumn{1}{c}{#1}}                                   
+                                                                                
+\hyphenation{post-or-der sym-bol Karls-ruhe bool-ean}                                    
+                                                                                
+\begin{document}                                                                
+                                                                                
+\bibliographystyle{plain}                                                       
+                                                                                
+\title{Drawing Trees Nicely with \TeX\thanks{This work was supported by         
+     a Natural Sciences and Engineering Research Council of Canada              
+     Grant~A-5692 and a Deutsche Forschungsgemeinschaft Grant~Sto167/1-1.
+     It was started during the first author's stay with              
+     the Data Structuring Group in Waterloo.}}                        
+\author{Anne Br\"uggemann-Klein\thanks{Institut f\"ur Informatik,     
+     Universit\"at Freiburg, Rheinstr.~10--12, 7800~Freiburg,
+     West~Germany}\ \and Derick Wood\thanks{Data          
+     Structuring Group, Department of Computer Science, University of           
+     Waterloo, Waterloo, Ontario, N2L~3G1, Canada}}                             
+\maketitle                                                                      
+                                                                                
+\begin{abstract}                                                                
+                                                                                
+Various algorithms have been proposed for the difficult problem of              
+producing aesthetically pleasing drawings of trees, see~%                       
+\cite{TidierTrees,TidyTrees} but                                                
+implementations only exist as ``special purpose software'',                     
+designed for special environments. Therefore,                                   
+many users resort to the                                                        
+drawing facilities available on most personal computers, but the                
+figures obtained in this way still look ``hand-drawn''; their quality is        
+inferior to the quality of the surrounding text that can be realized by         
+today's high quality text processing systems.                                   
+                                                                                
+In this paper we present an entirely new solution that                          
+integrates a tree drawing algorithm into one of the best text                   
+processing systems available. More precisely, we present a \TeX{} macro package 
+\TreeTeX{} that produces a drawing of a tree from a purely logical              
+description. Our approach has three advantages. First, labels           
+for nodes can be handled in a reasonable way. On the one hand, the tree         
+drawing algorithm can compute the widths of the labels and take                 
+them into account for the positioning of the nodes; on the other hand,          
+all the textual parts of the document can be treated uniformly. Second,         
+\TreeTeX{} can be trivially ported to any site running \TeX{}. Finally,         
+modularity in the description of a tree and \TeX{}'s macro capabilities         
+allow for libraries of subtrees and tree classes.                               
+                                                                                
+In addition, we have implemented an option that produces                        
+drawings which make the                                                         
+\emph{structure} of the trees more obvious to the human eye,                    
+even though they may not be as aesthetically pleasing.                          
+                                                                                
+\end{abstract}                                                                  
+                                                                                
+\section{Aesthetical criteria for drawing trees}                                
+                                                                                
+One of the most commonly used data structures in computer science is the tree.  
+As many people are using trees in their research or just as illustration        
+tools, they are usually struggling with the problem of                          
+\emph{drawing} trees. We are concerned primarily with ordered                   
+trees in the sense of~\cite{ACP}, especially binary and unary-binary            
+trees. A binary tree is a finite set of nodes which either                      
+is empty, or consists of a root and two disjoint binary trees called            
+the left and right subtrees of the root. A unary-binary tree is                 
+a finite set of nodes which either is empty, or consists of a root and          
+two disjoint unary-binary trees, or consists of a root and one                  
+nonempty unary-binary tree. An extended binary tree is a binary tree            
+in which each node has either two nonempty subtrees or two                      
+empty subtrees.                                                                 
+                                                                                
+For these trees there                                                           
+are some basic agreements on how they should be drawn, reflecting               
+the top-down and left-right ordering of nodes in a tree;                        
+see \cite{TidierTrees} and \cite{TidyTrees}.                                    
+                                                                                
+\begin{enumerate}                                                               
+\item[1.] Trees impose a distance on the nodes; no node                         
+          should be closer to the root than any of its                          
+          ancestors.                                                            
+\item[2.] Nodes of a tree at the same height should lie on a straight           
+          line, and the straight lines defining the levels should be            
+          parallel.                                                             
+\item[3.] The relative order of nodes on any level should be the same           
+          as in the level order traversal of the tree.                          
+\end{enumerate}                                                                 
+                                                                                
+These axioms guarantee that trees are drawn as planar graphs: edges do          
+not intersect except at nodes. Two further axioms improve the aesthetical       
+appearance of trees:                                                            
+                                                                                
+\begin{enumerate}                                                               
+\item[4.] In a unary-binary tree, each left child should be positioned          
+          to the left of its parent, each                                       
+          right child to the right of its parent, and each unary child          
+          should be positioned below its parent.                                
+\item[5.] A parent should be centered over its children.                        
+\end{enumerate}                                                                 
+                                                                                
+An additional axiom deals with the problem of tree drawings becoming too wide   
+and therefore exceeding the physical limit of the output medium:                
+                                                                                
+\begin{enumerate}                                                               
+\item[6.] Tree drawings should occupy as little width as possible without       
+          violating the other axioms.                                           
+\end{enumerate}                                                                 
+                                                                                
+In \cite{TidyTrees}, Wetherell and Shannon introduce two algorithms for         
+tree drawings, the first of which fulfills axioms~1--5, and the second          
+1--6. However, as Reingold and Tilford in \cite{TidierTrees}                    
+point out, there is a lack of symmetry in the algorithms of                     
+Wetherell and Shannon which may lead to unpleasant results.
+Therefore, Reingold and Tilford introduce a new structured        
+axiom:                                                                          
+                                                                                
+\begin{enumerate}                                                               
+\item[7.] A subtree of a given tree should be                                   
+          drawn the same way regardless of where it occurs in the given tree.   
+\end{enumerate}                                                                 
+                                                                                
+Axiom~7 allows the same tree to be drawn differently when it occurs as          
+a subtree in different trees.                                                   
+Reingold and Tilford give an algorithm which fulfills axioms~1--5               
+and~7. Although                                                                 
+this algorithm doesn't fulfill axiom~6,      
+the aesthetical improvements are well worth the additional space.
+\fig{algorithms} illustrates the benefits of axiom~7, and \fig{narrowtrees}
+shows that the algorithm of Reingold and Tilford violates axiom~6.
+
+\begin{Figure}                                                                  
+\centering
+\leavevmode\noindent                                                                      
+\begin{Tree}
+\enode
+\enode\enode\inode\enode\enode\inode\inode\inode
+\node{\external\type{dot}\rght{\unskip\hskip2\mins@p\hskip2\dotw@dth}}
+\enode\enode\inode\enode\enode\inode\inode\inode
+\inode                                                                    
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}                                                               
+\enode
+\enode\enode\inode\enode\enode\inode\inode\inode
+\enode
+\enode\enode\inode\enode\enode\inode\inode\inode
+\inode
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\                                                               
+\caption{The left tree is drawn by the algorithm of Wetherell and Shannon,
+and the tidier right one is drawn by the algorithm of Reingold and Tilford.}             
+\label{algorithms}                                                                  
+                                                                                
+\vspace{\figspace}                                                              
+\centering
+\leavevmode\noindent
+\begin{Tree}
+\enode\enode\enode\enode\enode\enode\enode\enode\enode
+\enode\inode\inode\inode                                                                      
+\enode\inode\inode\inode                                                                      
+\enode\inode\inode\inode                                                                      
+\enode\inode\inode\inode 
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\enode\enode\enode\enode\enode\enode\enode\enode
+\node{\external\type{dot}\rght{\unskip\hskip\mins@p\hskip\dotw@dth}}
+\enode\inode\inode\node{\type{dot}\rght{\unskip\hskip\mins@p\hskip\dotw@dth}}
+\enode\inode\inode\node{\type{dot}\rght{\unskip\hskip\mins@p\hskip\dotw@dth}}
+\enode\inode\inode\node{\type{dot}\rght{\unskip\hskip\mins@p\hskip\dotw@dth}}
+\enode\inode\inode\inode 
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\
+\caption{The left tree is drawn by the algorithm of Reingold and Tildford, but
+the right tree shows that narrower drawings fulfilling all aesthetic axioms
+are possible.}
+\label{narrowtrees}                                                                  
+\end{Figure}                                                                    
+                                                                                
+                                                                                
+\section{The algorithm of Reingold and Tilford}                                 
+                                                                                
+The algorithm of Reingold and Tilford (hereafter called ``the RT~algorithm'')   
+takes a modular approach to the                                                 
+positioning of nodes: The relative positions of the nodes in a subtree          
+are calculated independently from the rest of the tree. After the               
+relative positions of two subtrees have been calculated, they can be            
+joined as siblings in a larger tree by placing them as close                    
+together as possible and centering the parent node above them.                  
+Incidentally, the modularity principle is the reason that the                   
+algorithm fails to fulfill axiom~6; see~\cite{Complexity}.                      
+Two sibling subtrees are placed as close together as possible,                           
+during a postorder traversal, as follows. At each node \var{T},                 
+imagine that its two subtrees have been drawn and cut out of paper along        
+their contours. Then, starting with the two subtrees superimposed at their      
+roots, move them apart until a minimal agreed upon distance                     
+between the trees is obtained at each level. This can be done gradually:        
+Initially, their roots are separated by some agreed upon minimum                
+distance. Then, at the next lower level,                                        
+they are pushed                                                                 
+apart until the minimum separation is established there.                        
+This process is continued at successively lower levels until the                
+bottom of the shorter subtree is reached. At some levels no movement may be     
+necessary; but at no level are the two subtrees moved closer                    
+together. When the process is complete, the position of the                     
+subtrees is fixed relative to their parent, which is centered over them.        
+Assured that the subtrees will never be placed closer together,                 
+the postorder traversal is continued.                                           
+                                                                                
+A nontrivial implementation of                                                  
+this algorithm has been obtained by Reingold and Tilford that runs              
+in time $\O(N)$, where $N$ is the number of                                     
+nodes of the tree to be drawn.                                                  
+Their crucial idea is to keep track of the contour of the subtrees              
+by special pointers, called threads, such that whenever                         
+two subtrees are joined, only the                                               
+top part of the trees down to the lowest level of the                           
+smaller tree need to be taken into account.                              
+                                                                                
+The RT algorithm is given in \cite{TidierTrees}.
+The nodes are positioned on a fixed grid and are             
+considered to have zero width. No labelling is provided. The algorithm only     
+draws binary trees, but is easily extendable to multiway trees.                 
+                                                                                
+\section{Improving human perception of trees}                                   
+
+It is common understanding in book design that aesthetics and readability
+don't necessarily coincide, and---as Lamport (\cite{LaTeX}) puts it---%
+books are meant to be read, not to be hung on walls. Therefore, readability is
+more important than aesthetics.
+
+When it comes to tree drawings, readability means that the structure of
+a tree must be easily recognizable. This criterion is not always met
+by the RT~algorithm. As an example, there are trees whose structure is very
+different, the only common thing being the fact that they have the same number
+of nodes at each level. The RT~algorithm might assign identical positions to
+these nodes making it very hard to perceive the different structures.
+Hence, we have modified the RT~algorithm such that additional white space
+is inserted between subtrees of 
+\emph{significant} nodes. Here a binary node 
+is called significant if the minimum distance
+between its two subtrees is taken \emph{below} their root level.
+Setting the amount of additional white space to zero retains the original RT~%
+placement. The effect of having nonzero additional white space between 
+the subtrees of significant
+nodes is illustrated in \fig{addspace} .
+
+Another feature we have added to the RT~algorithms is the possibility to draw
+an unextended binary tree with the same placement of nodes as its
+associated extended version. We define the \emph{associated extended version}
+of a binary tree to be the binary tree obtained by replacing each empty subtree
+having a nonempty sibling with a subtree consisting of one node. This feature
+also makes the structure of a tree more prominent; see \fig{extended}.
+
+\begin{Figure}
+\centering
+\leavevmode\noindent                                                                      
+\begin{Tree} 
+\e\il\e\e\i\i\il % the left subtree
+\e\ir\il % the right subtree  
+\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\e\il\il\il % the left subtree
+\e\e\i\e\i\il % the right subtree
+\i
+\end{Tree}                                                               
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\adds@p10pt
+\begin{Tree}
+\e\il\e\e\i\node{\type{dot}\lft{$\longrightarrow$}}\il % the left subtree
+\e\ir\il % the right subtree  
+\node{\type{dot}\lft{$\longrightarrow$}}
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\e\il\il\il % the left subtree
+\e\e\i\e\i\il % the right subtree
+\node{\type{dot}\lft{$\longrightarrow$}}
+\end{Tree}                                                               
+\hskip\leftdist\box\TeXTree\hskip\rightdist\
+\adds@p0pt
+
+\caption{The first two trees get the same placement of their nodes
+by the RT~algorithm, although the structure of the two trees is very different.
+The alternative drawings highlight the structure of the trees by adding
+additional white space between the subtrees of 
+($\longrightarrow$) significant nodes.}
+\label{addspace}                                                                                
+\end{Figure} 
+
+\begin{Figure}
+\centering
+\leavevmode\noindent
+\begin{Tree}
+\e\e\i\il\e\e\i\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\e\e\i\e\i\e\ir\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\extended
+\begin{Tree}
+\e\e\i\il\e\e\i\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\qquad
+\begin{Tree}
+\e\e\i\e\i\e\ir\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\\
+\noextended
+\begin{Tree}
+\e\e\i\e\i\e\e\i\i
+\end{Tree}
+\hskip\leftdist\box\TeXTree\hskip\rightdist\  
+\caption{In the first two drawings, the RT~algorithm assigns the same placement 
+to the nodes of two trees although their structure is very different. The modified
+RT~algorithms highlights the structure of the trees by optionally
+drawing them like their extended
+counterpart, which is given in the second row.}
+\label{extended}
+\end{Figure}
+
+
+\section{Trees in a document preparation environment}                           
+                                                                                
+Drawings of trees usually don't come alone, but are included in some text       
+which is itself typeset by a text processing system. Therefore, a typical      
+scenario is a pipe of three stages. First comes the tree drawing             
+program which calculates the positioning of the nodes of the tree to            
+be drawn and outputs a description of the tree drawing in                       
+some graphics language; next comes a graphics system which transforms this      
+description into an intermediate language which can be interpreted by the output
+device; and finally comes the                                                   
+text processing system which integrates the output of the                       
+graphics system into the text.                                 
+                                                                                
+This scenario loses its linear structure once nodes have to be labelled, since
+the labelling influences the positioning of the nodes. Labels usually occur
+inside, to the left of, to the right of, or beneath nodes (the latter only for
+external nodes), and their extensions certainly should be taken into account
+by the  tree drawing algorithm. But the labels have to be typeset first
+in order to determine their extensions,
+preferably by the typesetting program that
+is used for the regular text, because this method makes for the uniformity in the textual
+parts of the document and provides the author with the full power of the
+text processing system for composing the labels. Hence, a more complex
+communication scheme than a simple pipe is required.
+
+Although a system of two processes running simultaneously might be the most
+elegant solution, we wanted a system that is easily portable to
+a large range of hardware at our sites 
+including personal computers with single process
+operating systems.                                                           
+Therefore, we thought of using a text processing system                              
+having programming facilities powerful enough to program a tree drawing algorithm                      
+and graphics facilities powerful enough                                                             
+to draw a tree. One text processing system                  
+rendering outstanding typographic quality and good enough programming           
+facilities is \TeX, developed by Knuth at Stanford University;                  
+see~\cite{TeXbook}.                                                             
+The \TeX{} system includes the following programming facilities:                
+                                                                                
+\begin{enumerate}                                                               
+\item[1.] datatypes:\\                                                          
+     integers~(256), dimensions\footnote{The term \emph{dimension} is used      
+     in \TeX\ to describe physical measurements of typographical objects,       
+     like the length of a word.}~(512), boxes~(256), tokenlists~(256), boolean  
+     variables~(unrestricted)                                                   
+\item[2.] elementary statements:\\                                              
+     $a:=\rm const$, $a:=b$ (all types);\\                                      
+     $a:=a+b$, $a:=a*b$, $a:=a/b$ (integers and dimensions);\\                  
+     horizontal and vertical nesting of boxes                                   
+\item[3.] control constructs:\\                                                 
+     if-then-else statements testing relations between integers,                
+     dimensions, boxes, or boolean variables                                    
+\item[4.] modularization constructs:\\                                          
+     macros with up to 9~parameters (can be viewed as procedures without        
+     the concept of local variables).                                               
+\end{enumerate}                                                                 
+                                                                                
+Although the programming                                                      
+facilities of \TeX{} hardly exceed the abilities of a Turing machine,
+they are sufficient to
+handle relatively small programs. How about the graphics facilities?   
+Although \TeX{} has no built-in graphics facilities, it                         
+allows the placement of characters in arbitrary positions on                    
+the page. Therefore, complex pictures can be synthesized from elementary        
+picture elements treated as characters. Lamport has included such               
+a picture drawing environment in his macro package \LaTeX, using                
+quarter circles of different sizes and line segments (with and without          
+arrow heads) of different slopes as basic elements; see~\cite{LaTeX}.           
+These elements are sufficient for drawing trees.                                
+                                                                                
+This survey of \TeX's capabilities implies that \TeX{} may be a suitable        
+text processing system to implement a tree drawing algorithm directly.          
+We are basing our algorithm on the RT~algorithm, because this algorithm               
+gives the aesthetically most pleasing results. In the first version
+presented here, we         
+restrict ourselves to unary-binary trees, although our method is                
+applicable to arbitrary multiway trees. But in order to take advantage          
+of the text processing environment, we expand the algorithm to allow            
+labelled nodes.                                                                 
+                                                                                
+In contrast to previous tree drawing programs, we feel no necessity to          
+position the nodes of a tree on a fixed grid. While this may be                 
+reasonable for a plotter with a coarse resolution, it is certainly not          
+necessary for \TeX, a system that is capable of handling                        
+arbitrary dimensions                                                            
+and produces device \emph{independent} output.                            
+
+                                                                                
+\section{A representation method for \TeX{}trees}                               
+                                                                                
+The first problem to be solved in implementing our tree drawing algorithm       
+is how to choose a good internal representation                                 
+for trees. A straightforward adaptation                                         
+of the implementation by Reingold and Tilford requires, for each node,          
+at least the following fields:                                                  
+                                                                                
+\begin{enumerate}                                                               
+\item two pointers to the children of the node                                  
+\item two dimensions for the offset to the left and the right child (these      
+      may be different once there are labels of different widths to the         
+      left and right of the nodes)                                              
+\item two dimensions for the $x$- and $y$-coordinates of the final              
+      position of the nodes                                                     
+\item three or four labels                                                      
+\item one token to store the geometric shape (circle, square, framed text etc.)
+      of the node.                       
+\end{enumerate}                                                                 
+                                                                                
+Because these data are used very frequently in calculations, they should be     
+stored in registers (that's what variables are called in \TeX),
+rather than being recomputed, in order to obtain           
+reasonably fast performance. This gives a total of $10N$ registers for          
+a tree with $N$ nodes, which would exceed                                                          
+\TeX's limited supply of registers. Therefore, we present a
+modified algorithm hand-tailored to the abilities of \TeX{}.
+We start with the following observation.                   
+Suppose a unary-binary tree is constructed bottom-up, in a postorder            
+traversal. This is done by iterating the following three steps in               
+an order determined by the tree to be constructed.                              
+                                                                                
+\begin{enumerate}                                                               
+\item Create a new subtree consisting of one external node.                     
+\item Create a new subtree by appending the two subtrees created last           
+      to a new binary node; see \fig{Construct}.                               
+\item Create a new subtree by appending the subtree created last as a left,     
+      right, or unary subtree of a new node; see \fig{Construct}.              
+\end{enumerate}                                                                 
+                                                                                
+(A pointer to) each subtree that has been                                       
+created in steps 1--3 is pushed onto a stack, and                               
+steps 2 and 3 remove two trees or one, respectively,                            
+from the stack before the push                                                  
+operation is carried out. Finally, the tree to be constructed will              
+be the remaining tree on the 
+stack.                                             
+                                                                                
+\begin{Figure}                                                                  
+\centering                                                                      
+\begin{Tree}                                                                    
+\treesymbol{\lvls{2}}%                                                          
+\hspace{-\l@stlmoff}\usebox{\l@sttreebox}\hspace{\l@strmoff}                    
+$+$                                                                             
+\treesymbol{\lvls{2}}%                                                          
+\hspace{-\l@stlmoff}\usebox{\l@sttreebox}\hspace{\l@strmoff}\quad               
+$\Longrightarrow$\quad                                                          
+\treesymbol{\lvls{2}}%                                                          
+\treesymbol{\lvls{2}}%                                                          
+\node{\type{dot}}%                                                              
+\hspace{-\l@stlmoff}\raisebox{\vd@st}{\usebox\l@sttreebox}\hspace{\l@strmoff}%  
+\end{Tree}
+
+\vskip\baselineskip                                                                      
+
+\begin{Tree}                                                                    
+\treesymbol{\lvls{2}}%                                                          
+\hspace{-\l@stlmoff}\usebox{\l@sttreebox}\hspace{\l@strmoff}\quad               
+$\Longrightarrow$\quad                                                          
+\treesymbol{\lvls{2}}%                                                          
+\node{\leftonly\type{dot}}%                                                     
+\hspace{-\l@stlmoff}\raisebox{\vd@st}{\usebox\l@sttreebox}\hspace{\l@strmoff}%  
+\quad or\quad                                                                   
+\treesymbol{\lvls{2}}%                                                          
+\node{\unary\type{dot}}%                                                        
+\hspace{-\l@stlmoff}\raisebox{\vd@st}{\usebox\l@sttreebox}\hspace{\l@strmoff}%  
+\quad or\quad                                                                   
+\treesymbol{\lvls{2}}%                                                          
+\node{\rightonly\type{dot}}%                                                    
+\hspace{-\l@stlmoff}\raisebox{\vd@st}{\usebox\l@sttreebox}\hspace{\l@strmoff}%  
+\end{Tree}                                                                      
+                                                                     
+\caption{Construction steps 2 and 3}                                                   
+\label{Construct}                                                              
+\end{Figure}                                                                    
+                                                                                
+This tree traversal is performed twice in the RT~algorithm.
+During the first pass,                            
+at each execution of step 2 or step 3, the relative positions of the         
+subtree(s) and of the new node are computed. 
+A closer examination of the RT~algorithm reveals that information about the
+subtree's coordinates is not needed during this pass; the contour information
+alone would be sufficient. Complete information is only needed in the second
+traversal, when the tree is actually drawn. Here a special feature of 
+\TeX{} comes in that allows us to save registers.
+Unlike Pascal, \TeX{} provides the capability of
+storing a drawing in a single box register that can be positioned freely in
+later drawings. This means that in our implementation the two passes
+of the original RT~algorithm can be intertwined into a single pass,
+storing for each subtree on the stack its contour and its drawing.
+Although the latter is a complex object, it takes only one of
+\TeX's precious registers.
+
+                                                                              
+\section{The internal representation}                                           
+                                                                                
+Given a tree, the corresponding \TeX{}tree is a box containing                  
+the ``drawing'' of the tree, together with some additional                      
+information about the contour of the tree.                                                              
+The reference point of a \TeX{}tree-box is always in the root of the            
+tree. The height, depth, and width of the box of a \TeX{}tree are               
+of no importance in this context.                                               
+                                                                                
+The additional information about the contour of the tree is stored in some      
+registers for numbers and dimensions and                                        
+is needed in order to put subtrees together to form a larger tree.              
+\var{loff} is an array of dimensions which contains for each                    
+level of the tree the horizontal offset between the                             
+left end of the                                                                 
+leftmost node at the current level and the                                      
+left end of the leftmost node at                                                
+the next level.                                                                 
+\var{lmoff} holds the horizontal offset between the root                        
+and the leftmost node of the whole tree. \var{lboff} holds the                  
+horizontal offset between the root and the leftmost node at                     
+the bottom level of the tree.                                                   
+Finally, \var{ltop} holds the distance between the reference point              
+of the tree and the leftmost end of the root.                                   
+The same is true for                                                            
+\var{roff}, \var{rmoff}, \var{rboff}, and \var{rtop}; just replace              
+``left'' by ``right''. Finally,                                                 
+\var{height} holds the height of the tree, and \var{type} holds the             
+geometric shape of the root of the tree. \fig{TeXtree} shows an example \TeX{}tree,
+i.e. a tree drawing and the corresponding additional information.
+
+\begin{Figure}
+\centering                                                                      
+\begin{Tree}                                                                    
+\e\ir\ir\e                                                                      
+  \node{\type{dot}\rightonly\rght{\unskip\vrule height.8pt width5pt depth0pt}}% 
+  \i % A                                                                        
+\end{Tree}                                                                      
+\leavevmode                                                                     
+\stack{-10pt}{\vd@st}{%                                                
+     -10pt\\10pt\\10pt\\\var{loff}}%                              
+\hspace{1em}%                                                                   
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%                         
+\hspace{1em}%                                                                   
+\stack{-10pt}{\vd@st}{%                                                         
+     15pt\\5pt\\-10pt\\\var{roff}}% 
+
+\vskip\baselineskip\raggedright
+height:~3, type:~dot, ltop:~2pt, rtop:~2pt, lmoff:~-10pt, rmoff:~20pt, lboff:~10pt,
+rboff:~10pt.
+
+\caption{A \TeX{}tree consists of the drawing of the tree and the
+additional information. The width of the dots is 4pt, the minimal separation between
+adjacent nodes is 16pt, making for a distance of 20pt center to center.
+The length of the small rule labelling one of the nodes is 5pt. The column left (right)
+of the tree drawing is the array \var{loff} (\var{roff}),
+describing the left (right) contour of the tree. At each level,
+the dimension given is the horizontal
+offset between the border at the current and at the next level. The offset between
+the left border of the root node and the leftmost node at level~1 is -10pt,
+the offset between the right border of the root node and the rightmost node at
+level~1 is 15pt, etc.}                               
+\label{TeXtree}
+\end{Figure}
+                                                                                
+Given two \TeX{}trees \var{A} and \var{B},                                      
+how can a new \TeX{}tree \var{C} be built that                                  
+consists of a new root and has \var{A} and \var{B} as subtrees?                 
+An example is given in \fig{AddInfo}.                        
+                                                                                
+\begin{Figure}                                                                  
+\centering                                                                      
+\begin{Tree}                                                                    
+\e\ir\ir\e                                                                      
+  \node{\type{dot}\rightonly\rght{\unskip\vrule height.8pt width5pt depth0pt}}% 
+  \i % A                                                                        
+\end{Tree}                                                                      
+\leavevmode                                                                     
+A: \stack{-10pt}{\vd@st}{%                                                      
+     -10pt\\10pt\\10pt\\\ \\\var{loff}(\var{A})}%                              
+\hspace{1em}%                                                                   
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%                         
+\hspace{1em}%                                                                   
+\stack{-10pt}{\vd@st}{%                                                         
+     15pt\\5pt\\-10pt\\\ \\\var{roff}(\var{A})}%                               
+\qquad                                                                          
+\begin{Tree}                                                                    
+\e\il\e\i\il\il\ir % B                                                          
+\end{Tree}                                                                      
+\leavevmode                                                                     
+B: \stack{-10pt}{\vd@st}{%                                                      
+     10pt\\-10pt\\-10pt\\-10pt\\-10pt\\\ \\\var{loff}(\var{B})}%               
+\hspace{1em}%                                                                   
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%                         
+\hspace{1em}%                                                                   
+\stack{-10pt}{\vd@st}{%                                                         
+     10pt\\-10pt\\-10pt\\10pt\\-30pt\\\ \\\var{roff}(\var{B})}%                
+\\[\figspace]                                                                        
+\begin{Tree}                                                                    
+\e\ir\ir\e                                                                      
+  \node{\type{dot}\rightonly\rght{\unskip\vrule height.8pt width5pt depth0pt}}% 
+  \i % A                                                                        
+\e\il\e\i\il\il\ir % B                                                          
+\i % C                                                                          
+\end{Tree}                                                                      
+\leavevmode                                                                     
+C: \stack{-10pt}{\vd@st}{%                                                      
+     -20\\-10pt\\%                                                              
+     \makebox[0pt][r]{\var{loff}(\var{A})$\smash{\left\{\vrule height\vd@st     
+          depth\vd@st width0pt\right.}$ }%                                      
+     10pt\\10pt\\%                                                              
+     \makebox[0pt][r]{$\longrightarrow$ }%                                      
+     10pt\\%                                                                    
+     \makebox[0pt][r]{\raisebox{-.5\vd@st}{\var{loff}(\var{B})$\smash           
+          {\left\{\vrule height.5\vd@st                                         
+          depth.5\vd@st width0pt\right.}$ }}%                                   
+     \makebox[0pt][r]{-}10pt\\\ \\\var{loff}(\var{C})}%                        
+\hspace{1em}%                                                                   
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%                         
+\hspace{1em}%                                                                   
+\stack{-10pt}{\vd@st}{%                                                         
+     20pt\\10pt\\-10pt\\-10pt%                                                  
+     \makebox[0pt][l]{\raisebox{-.5\vd@st}{                                     
+          $\smash{\left\}\vrule height2.5\vd@st                                 
+          depth2.5\vd@st width0pt\right.}$\var{roff}(\var{B})}}%                
+     \\10pt\\-30pt\\\ \\\var{roff}(\var{C})}%                                  
+                                                                                
+\vspace{\figspace}                                                              
+\centering                                                                      
+\begin{tabular}{|l|r|r|r|}                                                      
+\hline                                                                          
+&\multic{1}{c|}{\var{A}}&\multic{1}{c|}{\var{B}}&\multic{1}{c|}{\var{C}}\\      
+\hline                                                                          
+height&\multic{1}{c|}{3}&  \multic{1}{c|}{5}&  \multic{1}{c|}{6}\\              
+type&  \multic{1}{c|}{dot}&\multic{1}{c|}{dot}&\multic{1}{c|}{dot}\\            
+ltop&  2pt&                2pt&                2pt\\                            
+rtop&  2pt&                2pt&                2pt\\                            
+lmoff& -10pt&              -30pt&              -30pt\\                          
+rmoff& 20pt&               10pt&               30pt\\                           
+lboff& 10pt&               -30pt&              -10pt\\                          
+rboff& 10pt&               -30pt&              -10pt\\                          
+\hline                                                                          
+\end{tabular}\qquad                                                             
+\begin{tabular}{|c|r|r|}                                                        
+\hline                                                                          
+\multic{1}{|c|}{level}&\multic{1}{c|}{\var{totsep}}&                            
+                      \multic{1}{c|}{\var{currsep}}\\                           
+\hline                                                                          
+0&20pt&0/16pt\\                                                                 
+1&25pt&11/16\\                                                                
+2&40pt&1/16pt\\                                                                
+3&40pt&16pt\\                                                                
+\hline                                                                          
+\end{tabular}                                                                   
+\caption{The \TeX{}trees \var{A} and~\var{B} are combined to form the
+larger \TeX{}\-tree~\var{C}. The small table gives the 
+history of computation for \var{totsep} and \var{currsep}.}                  
+\label{AddInfo}                                                                 
+\end{Figure}                                                                    
+
+                                                                                
+First we determine which tree is higher; this is                                
+\var{B} in the example.                                                         
+Then we have to compute the minimal distance                                    
+between the roots of \var{A} and \var{B}, such that at all levels               
+of the trees there is free space of at least \var{minsep} between               
+the trees when they are drawn side by side.                                     
+For this purpose we keep track of two values, \var{totsep} and                  
+\var{currsep}. The variables \var{totsep} and \var{currsep}                     
+hold the total distance between the roots and the distance                      
+between the rightmost node of \var{A} and the leftmost node                     
+of \var{B} at the current level. In order to calculate                          
+\var{totsep} and \var{currsep}, we start at level 0 and                         
+visit each level of the trees until we reach the bottom level                   
+of the smaller tree; this is \var{A} in our example.                            
+                                                                                
+At level 0, the distance between the roots of \var{A} and \var{B}               
+should be at least \var{minsep}. Therefore, we set                              
+$\var{totsep}:=\var{minsep} + \var{rtop}(\var{A})                               
++ \var{ltop}(\var{B})$ and $\var{currsep}:=\var{minsep}$.                       
+Using $\var{roff}(\var{A})$ and $\var{loff}(\var{B})$, we can                   
+proceed to calculate \var{currsep} for the next level.                          
+If $\var{currsep} < \var{minsep}$, we have to increase \var{totsep} by          
+the difference and update \var{currsep}. This process is                        
+iterated until we reach the lowest level of \var{A}.                            
+Then \var{totsep} holds the final distance between the                          
+nodes of \var{A} and \var{B}, as calculated by the RT~algorithm. 
+If the root of \var{C} is a significant node, then the additional space ,
+which is 0pt by default, is added to \var{totsep}.               
+However, the approach of synthesizing                                           
+drawings from simple graphics characters allows only a finite                   
+number of orientations for the tree edges; therefore, \var{totsep}              
+must be increased slightly to fit the next orientation                          
+available.                                                                      
+                                                                                
+Now we are ready to construct the box of \TeX{}tree~\var{C}.                    
+Simply put \var{A} and~\var{B} side by side, with the reference                      
+points \var{totsep}~units apart, insert a new node                              
+above them, and connect the parent and children by edges.                       
+                                                                                
+Next, we update the additional information                                      
+for \var{C}. This can be done by using the additional information               
+for \var{A} and~\var{B}.                                                        
+Note that most components of $\var{roff}(\var{C})$ and                          
+$\var{lroff}(\var{C})$ are the same as in the higher tree, which                
+is \var{B} in our case.                                                         
+So, if we can avoid moving this information around, we only have                
+to access $\var{height}(\var{A}) + \var{const}$ many counters in                
+order to update the additional information for \var{C}.                         
+This implies that we can apply the same argument as                             
+in~\cite{TidierTrees}, which gives                                              
+us a running time of $\O(N)$ for drawing a tree with N nodes.                   
+                                                                                
+Therefore, we must carefully design the storage allocation for                  
+the additional information of \TeX{}trees in order to fulfill the               
+following requirements:                                                         
+If a new tree is built from                                                     
+two subtrees, the additional information of the new tree should                 
+share storage with its larger subtree.                                          
+Organizational overhead, that is,                                               
+pointers which keep track of the locations of different parts of additional     
+information, must be avoided.                                                   
+This means that all the additional information                                  
+for one \TeX{}tree should be stored in a row of consecutive dimension registers           
+such that only one pointer granting access to the first element                        
+in this row is needed.                                                          
+On the other hand, each parent                                                  
+tree is higher and therefore needs more storage than its subtrees.              
+So we must ensure that there is always enough space in the row                  
+for more information.                                                           
+                                                                                
+The obvious way to fulfill these requirements is to use a stack and to           
+allow only the topmost \TeX{}trees of this stack to be                          
+combined into a larger tree at any time.                   
+This leads to the following register allocation: A subsequent number of         
+box registers contains the treeboxes of the subtrees in the stack. A            
+subsequent number of token registers contains the type information for the      
+nodes of the subtrees in the stack. For each subtree in the stack,              
+a subsequent number of dimension registers contains the contour                 
+information of the subtree. The ordering of these groups of dimension           
+registers reflects the ordering of the subtrees in the                          
+stack. Finally, a subsequent number of counter registers contains               
+the height and the address of the first dimension register for                  
+each subtree in the stack. Four address counters store the addresses            
+of the last treebox, type information, height, and address of contour           
+information. A sketch of the register organization for a stack of \TeX{}trees
+is provided in \fig{Registers}.
+
+\begin{Figure}                                                                  
+Dimension registers\\                                                           
+\var{lmoff}(1) \var{rmoff}(1) \var{lboff}(1) \var{rboff}(1) \var{ltop}(1)       
+               \var{rtop}(1)\\                                                  
+\var{loff}($h_1$) \var{roff}($h_1$) \dots\ \var{loff}(1) \var{roff}(1)\\        
+\dots\\                                                                         
+\var{lmoff}($n$) \var{rmoff}($n$) \var{lboff}($n$) \var{rboff}($n$)             
+                 \var{ltop}($n$) \var{rtop}($n$)\\                              
+\var{loff}($h_n$) \var{roff}($h_n$) \dots\ \var{loff}(1) \var{roff}(1)\\        
+\ \\                                                                            
+Counter registers\\                                                             
+\var{lasttreebox} \var{lasttreeheight} \var{lasttreeinfo} \var{lasttreetype}\\  
+\var{treeheight}(1) \var{diminfo}(1) \dots\ \var{treeheight}($n$)               
+                    \var{diminfo}($n$)\\                                        
+\ \\                                                                            
+Box registers\\                                                                 
+\var{treebox}(1) \dots\ \var{treebox}($n$)\\                                    
+\ \\                                                                            
+Token registers\\                                                               
+\var{type}(1) \dots\ \var{type}($n$)
+
+\caption{\var{lasttreebox}, \var{lasttreeheight}, \var{lasttreeinfo},                    
+\var{lasttreetype} contain pointers to \var{treebox}($n$)                        
+\var{treeheight}($n$), \var{lmoff}($n$), \var{type}($n$),                       
+\var{diminfo}($i$) contains a pointer to                                        
+\var{lmoff}($i$). Unused dimension registers are                                
+allowed between the dimension registers of subsequent trees. The counter
+registers \var{lasttreebox},\ldots,\var{diminfo}($n$) serve as a directory
+mechanism to access the \TeX{}trees on the stack.}                   
+\label{Registers}                                                               
+\end{Figure}                                                                    
+                                                                   
+                                                                                
+When a new node is pushed onto the stack, the treebox, type information,        
+height, address of contour information, and contour information are             
+stored in the next free registers of the appropriate type, and the              
+four address counters are updated accordingly.                                  
+                                                                                
+When a new tree is formed from the topmost subtrees on the stack,               
+the treebox, type information, height, and address of contour information       
+of the new tree are sorted in the registers formerly used by the bottommost     
+subtree that has occured in the construction step, and the four address registers are       
+updated accordingly. This means that these informations for the subtrees        
+are no longer accessible. The contour information of the new subtree            
+is stored in the same registers as the contour information of the larger        
+subtree used in the construction, apart from the left and right offset          
+of the root to the left and right child, which are stored in the                
+following dimension registers. That means that gaps can occur                   
+between the contour information of subsequent subtrees in the                    
+stack, namely when the right subtree, which is on a higher position on the      
+stack, is higher than the left one. In order to avoid these                     
+gaps, the user can specify an option \verb.\lefttop. when entering a            
+binary node, which makes the topmost tree in the stack the                      
+left subtree of the node.                                                       
+                                                                                
+This stack concept also has consequences for the design of the user interface   
+that is discussed in Section~\ref{Interface}.                                   
+                                                                                
+\section{Space cost analysis}                                                   
+                                                                                
+Suppose we want to draw a unary-binary tree $T$ of height $h$ having            
+$N$ nodes\footnote{The height $h$ and the number of nodes $N$ refer to the
+drawing of the tree. $N$ is the number of circles, squares etc.~actually
+drawn, and $h$ is the number of levels in the drawing minus 1.}.
+According to our internal representation,                            
+for each subtree in the stack we need                                           
+                                                                                
+\begin{enumerate}                                                               
+\item one box register to store the box of the \TeX{}tree.                       
+\item one token register to store the type of the root of the subtree.           
+\item $2h^\prime+6$ dimension registers to store the additional 
+      information, where $h^\prime$ is the height of the                        
+      subtree.                                                                   
+\item three counter registers to store the register numbers of the             
+      box register, the token register, and the first dimension register above.         
+\end{enumerate}                                                                 
+                                                                                
+The following lemma relates to $h$ and $N$ the number
+of subtrees of $T$ which are on the      
+stack simultaneously and their heights.                          
+                                                                                
+\begin{lemma}                                                                   
+\begin{enumerate}                                                               
+\item At any time, there are at most $h+1$ subtrees of $T$ on the               
+      stack.                                                                    
+\item For each set $\T$ of subtrees of $T$ which are on the stack               
+      simultaneously we have                                                    
+      $$\sum_{T^\prime\in \T}({\rm ht}(T^\prime)+1)                             
+        \le\min(N,{(h+1)(h+2)\over2}).$$                                      
+\end{enumerate}                                                                 
+\end{lemma}                                                                     
+                                                                                
+\begin{proof}                                                                   
+\begin{enumerate}                                                               
+\item By induction on $h$.\label{stackdepth}                                           
+\item The trees in $\T$ are pairwise disjoint, and each tree of                 
+      height $h^\prime$ has at least $h^\prime+1$ nodes. This implies           
+      $$\sum_{T^\prime\in \T}({\rm ht}(T^\prime)+1)                             
+        \le N.$$                                                                
+      The second part is shown by induction on $h$.                           
+      The basis $h=0$ is clear.                                                 
+      Assume the assumption holds for all trees of height less than             
+      $h$. If $\T$                                                              
+      contains only subtrees of either the left or the right subtree            
+      of $T$, we have                                                           
+      $$\sum_{T^\prime\in \T}({\rm ht}(T^\prime)+1)\le                          
+      {h(h+1)\over2}\le{(h+1)(h+2)\over2}.$$                                    
+      Otherwise, $\T$ contains the left or the right subtree $T_s$ of           
+      $T$. Then all elements of $\T-\{T_s\}$ belong to the other                
+      subtree. This implies                                                     
+      \begin{eqnarray*}                                                         
+      \sum_{T^\prime\in \T}({\rm ht}(T^\prime)+1)&\le&                          
+      {\rm ht}(T_s)+1                                                           
+      +\sum_{T^\prime\in \T-\{T_s\}}({\rm ht}(T^\prime)+1)\\                    
+      &\le& h+{h(h+1)\over2}\le{(h+1)(h+2)\over2}.\proofend                       
+      \end{eqnarray*}                                                           
+\end{enumerate}                                                                 
+\end{proof}                                                                     
+                                                                                
+Therefore, our implementation uses at most $9h+2\min(N,(h+1)(h+2)/2)$          
+registers. In order to compare this with the                                    
+$10N$ registers used in the straightforward implementation,                     
+an estimation of the average height of a tree with $N$ nodes is                 
+needed. Several results, depending on the type of trees and of the                       
+randomization model, are cited in \fig{Stat}, which 
+compares the number of registers used in a straightforward           
+implementation with the average number of registers used in our                 
+implementation. This table shows clearly the advantage of our                  
+implementation. 
+
+\begin{Figure}
+\centering                                                                  
+\begin{tabular}{|c|c|c|c|c|}                                                    
+\hline                                                                          
+&registers&\multicolumn{3}{c|}{average registers}\\                             
+\cline{3-5}                                                                     
+nodes&(straight-&extended&unary-binary&binary\\                           
+&forward)&binary trees&trees&                                            
+     search trees\\
+&&($\sqrt{\pi n}$) \cite{AverageHeight}&
+  ($\sqrt{3\pi n}$) ~\cite{BinaryTrees}&
+  ($4.311\log n$) \cite{BinarySearchTrees}\\                                                             
+\hline                                                                          
+\ds8&    \ds80& \ds61.12& \ds94.15& \ds51.04\\                                  
+\ds9&    \ds90& \ds65.86&   100.89& \ds55.02\\                                  
+  10&      100& \ds70.44&   107.37& \ds58.80\\                                  
+  11&      110& \ds74.91&   113.64& \ds62.41\\                                  
+  12&      120& \ds79.26&   119.71& \ds65.87\\                                  
+  20&      200&   111.34&   163.56& \ds90.48\\                                  
+  30&      300&   147.37&   211.33&   117.31\\                                  
+  40&      400&   180.89&   254.75&   132.58\\                                  
+  50&      500&   212.80&   295.37&   143.54\\                                  
+\hline                                                                          
+\end{tabular}
+                                                                   
+\caption{The numbers of registers used by a straightforward implementation
+(second column) and by our modified implementation (third to fifth column)
+of the RT~algorithm are
+given for different types of trees and randomization models.
+The formula in parentheses indicates the average height of the respective class
+of trees, as depending on the number of nodes.}                                                        
+\label{Stat}                                                                    
+\end{Figure}                                                                    
+                                                                
+                                                                                
+\section{The user interface}\label{Interface}                                   
+                                                                                
+\subsection{General design considerations}                                      
+                                                                                
+The user interface of \TreeTeX{} has been designed in the spirit of             
+the thorough separation of the logical description of document components       
+and their layout; see~\cite{DocumentFormatting,GML}. This concept               
+ensures both uniformity and flexibility of document layout and frees            
+authors from layout problems which have nothing to do with the                  
+substance of their work. For some powerful implementations and projects         
+see \cite{Tables,Karlsruhe,LaTeX,Grif,Scribe}.                                  
+                                                                                
+In this context, the description of a tree is given in a purely                 
+logical form, and layout variations are defined by a separate style             
+command which is valid for all trees of a document.                             
+                                                                                
+A second design principle is to provide defaults for all specifications,        
+thereby allowing the user to omit many definitions                              
+if the defaults match what he or she wants.                                                        
+                                                                                
+The node descriptions of a tree must be entered in postorder.                   
+This fits the internal representation                                      
+of \TeX{}trees best. Although this is a natural method of describing a               
+tree, a user might prefer more flexible description methods.                     
+However, note that instances of well defined tree classes can be described      
+easily by \TeX{} macros. In section~\ref{ExampleClasses}. we give examples of macros                             
+for complete binary trees and Fibonacci trees.                                  
+                                                                                
+\TreeTeX{} uses the picture making macros of \LaTeX. If \TreeTeX{} is used with 
+any other macro package or format, the picture macros of                        
+\LaTeX{} are included automatically.                                            
+                                                                                
+\subsection{The description of a tree}                                          
+                                                                                
+The description of a tree is started by the command \verb.\beginTree.           
+and closed by \verb.\endTree. (or \verb.\begin{Tree}. and                       
+\verb.\end{Tree}. in \LaTeX). The description can be                  
+started in any mode; it defines a box and two dimensions. The                   
+box is stored in the box register \verb.\TeXTree. and contains the              
+drawing of the tree. The box has zero height and width, and its depth           
+is the height of the drawing. The reference point is in the                     
+center of the node of the tree. The dimensions are stored in the                
+registers \verb.\leftdist. and \verb.\rightdist. and describe                   
+the distance between the reference point and the left and                       
+right margin of the drawing. These data can be used to position the             
+drawing of the tree.                                                            
+                                                                                
+Note that the \TreeTeX{} macros don't contribute anything to the current        
+page but only store their results in the registers                              
+\verb.\TeXTree., \verb.\leftdist., and \verb.\rightdist.. It is the             
+user's job to put the drawing onto the page, using the                          
+commands \verb.\copy. or \verb.\box. (or \verb.\usebox. in \LaTeX).             
+                                                                                
+Each matching pair of \verb.\beginTree. and \verb.\endTree. must                
+contain the description for only \emph{one} tree.                               
+Descriptions of trees cannot be nested and                                      
+new registers cannot be allocated inside                                        
+a matching pair of \verb.\beginTree. and \verb.\endTree..                       
+                                                                                
+As already stated, each tree description defines the nodes of the tree in                        
+postorder, that is, a tree description is a particular sequence of node         
+descriptions.                                                                   
+                                                                                
+A node description, in turn, consists of the macro \verb.\node.,                
+followed by a list of node options, included in braces. The list                
+of node options may be empty. The node options describe the labels,             
+the geometric shape (type), and the outdegree of the node. Default values are   
+provided for all options which are not explicitly specified.                    
+The following node options are available:                                       
+                                                                                
+\begin{enumerate}                                                               
+\item[1.] \verb.\lft{<label>}., \verb.\rght{<label>}.,                          
+     \verb.\cntr{<label>}.,\\\verb.\bnth{<label>}.:\\                           
+     These options describe the labels which are put to the left of, to the     
+     right of, in the                                                           
+     center of, or beneath the node (the latter only makes sense for            
+     external nodes). The arguments of these macros are processed in            
+     internal horizontal mode (LR-mode in \LaTeX), but can consist of           
+     arbitrary nested boxes for more sophisticated labels. For each of          
+     these options, the default is an empty label.                              
+                                                                                
+\item[2.] \verb.\external., \verb.\unary.,                                      
+     \verb.\leftonly., \verb.\rightonly.:\\                                     
+     These options describe the outdegree                                       
+     of the node.                                   
+     The default is binary (no outdegree option is specified).                  
+                                                                                
+\item[3.] \verb.\type{<type>}.:\\                                               
+     This option describes the type or geometric shape of the node.             
+     \verb.<type>. can have the values \verb.square.,                         
+     \verb.dot., \verb.text., or \verb.frame.. 
+     The default value is \verb.circle. (no type is specified). A node of type
+     \verb.square. has a fixed width, while a node of type \verb.frame. has its
+     width determined by the center label. A node of type \verb.text. has no frame
+     around its center label. The center label can have arbitrary width.
+
+\item[3.] \verb.\leftthick., \verb.\rightthick.:
+     These options change the thickness of the left or right outgoing edge of
+     a binary node. Defaults are thin edges (neither option is specified).      
+                                                                                
+\item[4.] \verb.\lefttop.:\\                                                    
+     The node option \verb.\lefttop. in a binary node makes the                 
+     last entered subtree the left child of the node (the right child is the    
+     default). This option helps to cut down on the number of dimension registers  
+     used during the construction of a tree. As a rule of thumb,                
+     this option is recommended when the left subtree has a smaller             
+     height than the right subtree, that is,                                    
+     in this case the right subtree should                                      
+     be entered before the left one and their parent should be assigned the option 
+     \verb.\lefttop..                                                           
+\end{enumerate}                                                                 
+                                                                                
+\subsection{Macros for classes of trees}
+\label{ExampleClasses}                                        
+                                                                                
+Tree descriptions can be produced by macros. This is especially useful          
+for trees which belong to a larger class of trees and which can be specified    
+by some simple parameters. A small library of such                              
+macros is provided in the file \verb!TreeClasses.tex!.                          
+                                                                                
+\begin{enumerate}                                                               
+\item[1.] \verb.\treesymbol{<node options>}.:\\                                 
+     This macro produces a triangular tree symbol which can be included in      
+     a tree description instead of an external node. Labels for these           
+     tree symbols are described as for ordinary nodes. In addition, the         
+     options \verb.\lvls{<number>}. and \verb.\slnt{<number>}.                  
+     are provided. \verb.\lvls. defines the number of levels in the             
+     tree over which the triangle extends, and \verb.\slnt. gives               
+     the slant of the sides of the triangle, ranging from 1~(minimal)           
+     to 24~(maximal). On the other hand,                                        
+     \verb.\treesymbol. does not expand to a tree description, because          
+     a tree symbol cannot be built from subtrees, and, on the other hand,       
+     it is not a node, because it is allowed to extend over several tree        
+     levels and therefore has a longer contour than an ordinary node.           
+                                                                                
+\item[2.] \verb.\binary{<bin specification>}.:\\                                
+     This macro truly expands to a tree description. It produces                
+     a complete binary tree, that is, an extended binary tree,                  
+     where, for a given $h$, all external nodes appear at level $h$             
+     or $h-1$, and all external nodes at level $h$ lie left of those at         
+     level $h-1$. \verb.<bin specification>. consists of the                    
+     following options:                                                         
+     \verb.\no{<number>}. defines the number of internal nodes,                 
+     with \verb.<number>. greater than 0, and                                   
+     \verb.\squareleaves. produces leaves of type                               
+     \verb.square.. Defaults are \verb.\no{1}. and                              
+     leaves of type \verb.circle..                                              
+                                                                                
+\item[3.] \verb.fibonacci{<fib specification>}.:\\                              
+     This macro produces a Fibonacci tree.              
+     \verb.<fib specification>. allows for the three options                    
+     \verb.\hght{<number>}., \verb.\unarynodes.,                                 
+     and \verb.\squareleaves..                                                  
+     Normally, a Fibonacci tree of height $h+2$ is a binary tree                
+     with Fibonacci trees of height $h$ and $h+1$ as left and                   
+     right subtrees. The option \verb.\unarynodes. means that the               
+     Fibonacci tree is augmented by unary nodes such that each                  
+     two subtree siblings have the same height. These are examples
+     of what has been called brother-trees in the literature; 
+     see~\cite{Brother}. Defaults are                    
+     \verb.\hght{0}., the unaugmented version of a Fibonacci tree,              
+     and external nodes of type \verb.circle..                                  
+\end{enumerate}                                                                 
+                                                                                
+\subsection{Style options for trees}
+\sloppy                                            
+The \TreeTeX{} package includes a style command                           
+\verb.\Treestyle{<style option>}., where \verb.<style option>.                   
+contains all the parameter settings the user might want                         
+to change.                                                                      
+Normally, the command \verb.\Treestyle. appears only once at the beginning      
+of the document and the style options are valid for all trees of the            
+document.      
+
+\fussy                                                                                
+The changes in the style options are global. A \verb.\Treestyle. command        
+changes only the specified style options; non-specified options retain          
+the last specified value or the default value, respectively. The following            
+style options are available:                                                    
+                                                                                
+\begin{enumerate}                                                               
+\item[1.] \verb.\treefonts{<font options>}.:\\                                  
+     \sloppy                                                                    
+     \verb.\treefonts. is invoked by \verb.\beginTree., and it simply executes  
+     whatever is specified in \verb.<font options>.. Defaults are               
+     \verb.\treefonts{\tenrm}. (or \verb.\treefonts{\normalsize\rm}. in         
+     \LaTeX).                                                                   
+                                                                                
+\fussy                                                                          
+\item[2.] \verb.\nodesize{<size>}.:\\                                           
+     \verb.\nodesize. defines the size of the nodes. \verb.<size>. is a         
+     dimension and specifies the diameter of circle nodes. The                  
+     width of square nodes is adjusted accordingly to be slightly               
+     smaller than the diameter of circle nodes in order to                      
+     balance their appearance. Furthermore,                                     
+     \verb.\nodesize. adjusts the amount of space by which the                  
+     baseline of the labels is placed beneath the center of the node.           
+     The default value of \verb.\nodesize. suits the default of                 
+     \verb.\treefonts. (taking into account the size option                     
+     of \LaTeX's document style).                                               
+                                                                                
+\item[3.] \verb.\vdist{<dimen>}., \verb.\minsep{<dimen>}.,                      
+     \verb.\addsep{<dimen>}.:\\                                                 
+     \sloppy                                                                    
+     \verb.vdist. specifies the vertical distance between two                   
+     subsequent levels of the tree. Default is \verb.\vdist{60pt}..             
+     \verb.\minsep. specifies the minimal horizontal distance between two       
+     adjacent nodes. Default is \verb.\minsep{20pt}..                           
+     \verb.\addsep. specifies the additional amount of horizontal space         
+     by which two subtree siblings are pushed apart farther than                
+     calculated by the RT~algorithm,                                            
+     if the level at which they are closest is beneath                          
+     their root level. Default is \verb.\addsep{0pt}.                           
+                                                                                
+\fussy                                                                          
+\item[4.] \verb.\extended., \verb.\nonextended.:\\                              
+     With the option \verb.\extended. in effect, the nodes of a binary          
+     tree are placed in exactly the same way as they would be in the            
+     associated extended version of the tree (the missing nodes are             
+     assumed to have no labels). The default is \verb.\nonextended.,            
+     that is the usual layout.                                                  
+\end{enumerate}                                                                 
+                                                                                
+Some examples of tree descriptions                                              
+are given in the next figures.                
+A detailed description of the                                                   
+\TreeTeX{} macros is given in~\cite{TreeTeX}.
+                                   
+\Treestyle{\vdist{60pt}}                                                        
+\dummyhalfcenterdim@n=10pt                                                      
+                                                                                
+\begin{Figure}
+\centering
+\begin{Tree}
+\node{\external\bnth{first}\cntr{1}\lft{Beeton}}                         
+\node{\external\cntr{3}\rght{Kellermann}}                                       
+\node{\cntr{2}\lft{Carnes}}                                                     
+\node{\external\cntr{6}\lft{Plass}}                                             
+\node{\external\bnth{last}\cntr{8}\rght{Tobin}}                          
+\node{\cntr{7}\rght{Spivak}}                                                    
+\node{\leftonly\cntr{5}\rght{Lamport}}                                          
+\node{\cntr{4}\rght{Knuth}}                                                     
+\end{Tree}
+                                                                        
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}\                         
+
+\begin{verbatim}
+\begin{Tree}
+\node{\external\bnth{first}\cntr{1}\lft{Beeton}}                         
+\node{\external\cntr{3}\rght{Kellermann}}                                       
+\node{\cntr{2}\lft{Carnes}}                                                     
+\node{\external\cntr{6}\lft{Plass}}                                             
+\node{\external\bnth{last}\cntr{8}\rght{Tobin}}                          
+\node{\cntr{7}\rght{Spivak}}                                                    
+\node{\leftonly\cntr{5}\rght{Lamport}}                                          
+\node{\cntr{4}\rght{Knuth}}                                                     
+\end{Tree}
+                                                                        
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}
+\end{verbatim} 
+
+\caption{This is an example of a tree that includes labels.}                                         
+\end{Figure}
+
+\begin{Figure}
+\centering
+\begin{Tree}
+\node{\external\type{frame}\bnth{first}\cntr{Beeton}}                         
+\node{\external\type{frame}\cntr{Kellermann}}                                       
+\node{\type{frame}\cntr{Carnes}}                                                     
+\node{\external\type{frame}\cntr{Plass}}                                             
+\node{\external\type{frame}\bnth{last}\cntr{Tobin}}                          
+\node{\type{frame}\cntr{Spivak}}                                                    
+\node{\leftonly\type{frame}\cntr{Lamport}}                                          
+\node{\type{frame}\cntr{Knuth}}                                                     
+\end{Tree}
+                                                                        
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}\                         
+
+\begin{verbatim}
+\begin{Tree}
+\node{\external\type{frame}\bnth{first}\cntr{Beeton}}                         
+\node{\external\type{frame}\cntr{Kellermann}}                                       
+\node{\type{frame}\cntr{Carnes}}                                                     
+\node{\external\type{frame}\cntr{Plass}}                                             
+\node{\external\type{frame}\bnth{last}\cntr{Tobin}}                          
+\node{\type{frame}\cntr{Spivak}}                                                    
+\node{\leftonly\type{frame}\cntr{Lamport}}                                          
+\node{\type{frame}\cntr{Knuth}}                                                     
+\end{Tree}
+                                                                        
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}
+\end{verbatim}
+\caption{This is an example of a tree with framed center labels.} 
+\end{Figure}
+
+\begin{Figure}                                                                  
+\centering                                                                      
+\begin{Tree}                                                                    
+\binary{\no{6}\squareleaves}                                                    
+\end{Tree}
+                                                                      
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}\                         
+                                                                     
+\begin{verbatim}                                                                
+\begin{Tree}                                                                    
+\binary{\no{6}\squareleaves}                                                    
+\end{Tree}
+                                                                      
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}
+\end{verbatim}                                                                  
+\caption{This is an example of a complete binary tree.}                                     
+\end{Figure} 
+
+                                                                   
+\begin{Figure}                                                                  
+\centering                                                                      
+\begin{Tree}                                                                    
+\fibonacci{\hght{4}\unarynodes\squareleaves}                                    
+\end{Tree}
+
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}\                         
+                                                                      
+\begin{verbatim}                                                                
+\begin{Tree}                                                                    
+\fibonacci{\hght{4}\unarynodes\squareleaves}                                    
+\end{Tree}
+\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}
+\end{verbatim}
+                                                                  
+\caption{This is an example of a Fibonacci tree.}                                           
+\end{Figure}                                                                    
+ 
+                                                                                
+\clearpage                                                                      
+\bibliography{trees}                                                            
+\end{document}                                                                  
+                                                                                
+                                                                                
+
diff --git a/macros/plain/contrib/treetex/treetex.tex b/macros/plain/contrib/treetex/treetex.tex
new file mode 100644
index 0000000000..0a3ae04f26
--- /dev/null
+++ b/macros/plain/contrib/treetex/treetex.tex
@@ -0,0 +1,1187 @@
+% This is file treetex.tex of TreeTeX, Version 2.1 (May 23, 1989).
+% For changes search for "vs. 2.1".
+% 
+% TreeTeX is a public domain macro package for drawing
+% trees with TeX. It may be freely distributed, provided
+% that the following files are kept together:
+%  
+%   classes.tex, l_pic.tex, readme, tree_doc.aux, tree_doc.bbl
+%   tree_doc.dvi, tree_doc.tex, treetex.tex
+% 
+% Copyright is with Anne Brueggemann-Klein and Derick Wood. 
+% Print tree_doc.dvi to get more information about TreeTeX.
+% 
+% All remarks, bug reports etc. should be directed to
+% 
+%   Dr. Anne Brueggemann-Klein
+%   Institut fuer Informatik
+%   Rheinstr. 10--12
+%   7800 Freiburg, West Germany
+% 
+%   email: abk@sun1.ruf.uni-freiburg.dbp.de
+% 
+
+\catcode`\@=11                                                                  
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Only for testing, delete later                                       %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+\tracingonline=2                          %                                      
+% \showboxbreadth=100                     % Only for testing                     
+% \showboxdepth=100                       %                                      
+
+\newcount\cnta\newcount\cntb\newcount\cntc
+
+\def\showlasttree{%
+     \g\cnta\count\l@stdiminfo
+     \g\cntb\cnta
+     \g\advance\cntb 5 
+     \g\advance\cntb \count\l@sttreeheight
+     \g\advance\cntb \count\l@sttreeheight
+     \ifnum\count\l@sttreeheight=-1\relax
+           \g\advance\cntb by 2
+           \immediate\write16{Tree contour for dummy node:}
+      \else\immediate\write16{Tree contour:}% 
+        \fi
+     \for\cntc:=\cnta\to\cntb\do\immediate\write16{\the\dimen\cntc}\od}
+                                                                               
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% TeX vs. LaTeX                                                        %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+\def\lplain{lplain}                     % Set \LaTeXtrue if TreeTeX is          
+\newif\ifLaTeX                          % used together with LaTeX,             
+\ifx\fmtname\lplain\LaTeXtrue           % otherwise set \LaTeXfalse             
+    \else\LaTeXfalse\fi                 % (LaTeX defines \fmtname=={lplain}).   
+
+\immediate\write16{This is TreeTeX, Version 2.1, for use with \ifLaTeX LaTeX%     
+                   \else plain TeX\fi.}                                         
+                                                                                
+\ifLaTeX \let\lineseg\line              % latex_picture is part of latex.tex,   
+   \else \let\@line\line                % so you don't need it if you use       
+         \input l_pic                   % TreeTeX together with LaTeX. LaTeX    
+         \let\lineseg\line              % has the command \line for geometric   
+         \let\line\@line                % lines, and plain TeX has the same     
+   \fi                                  % command for lines of text. Because    
+                                        % both versions of \line play an        
+                                        % important role in the respective      
+                                        % macro packages, we introduce a new    
+                                        % command \lineseg in TreeTeX for the   
+                                        % geometric lines, and \line will have  
+                                        % the LaTeX-meaning if TreeTeX is used  
+                                        % with LaTeX, and the plain \TeX        
+                                        % meaning otherwise.                    
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% General programming environment                                      %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+\catcode`\@=11                                                                  
+\let\g\global                                                                   
+\def\gxdef{\global\xdef}                                                        
+                                                                                
+% The command \newcount is redefined such that it can be used           
+% inside a definition (i.e. it is no longer an \outer-command).          
+                                                                                
+\def\newcount{\alloc@0\count\countdef\insc@unt}                                 
+                                                                                
+% Implementing a for-loop (first argument must be a counter).                   
+% Usage: \for<counter>:=<start value>\to<stop value>\do<operations>\od          
+% Semantics: the same as a PASCAL for-loop                                      
+% Precautions: Don't change the counter-value inside the loop!                  
+%              for-loops cannot be nested (nor can the \loop-commands!).        
+                                                                                
+\def\for#1:=#2\to#3\do#4\od{%
+   \def\f@rcount{#1}\def\upp@rlimit{#3}\def\b@dy{#4}\f@rcount=#2\relax\dof@r}
+
+\def\dof@r{\ifnum\f@rcount>\upp@rlimit\relax\let\n@xt\relax
+                 \else\b@dy\advance\f@rcount\@ne\let\n@xt\dof@r\fi
+           \n@xt}
+                                                                                
+% \ex repeats a sequence of commands a predetermined number of times.           
+% Usage: \ex<number>\times<operations>\xe                                       
+% Semantics: <operations> is executed as often as <number> says                 
+% Precautions: \ex commands cannot be nested.                                   
+                                                                                
+\newcount\@xcount
+\newcount\t@mes                                                                    
+                                                                                
+\def\ex#1\times#2\xe{%                                                          
+   \@xcount1 \t@mes#1\def\b@dy{#2}\do@x}
+
+\def\do@x{\ifnum\@xcount>\t@mes\let\n@xt\relax
+                \else\b@dy\advance\@xcount\@ne\let\n@xt\do@x\fi
+          \n@xt}
+                                                                              
+% \rect@ngle produces a rectangle with horizontal edge length #1, vertical
+% edge length #2 and line thickness #3. The reference point is in the center of
+% the rectangle. The width is 0pt.
+
+\newskip\thickn@ss
+\newskip\@nner
+\newskip\@uter
+
+\def\rect@ngle#1#2#3{\hbox to 0pt{%
+     \thickn@ss#3%
+     \g\@nner#2\g\advance\@nner-\thickn@ss
+     \g\divide\@nner\tw@
+     \g\@uter#2\g\advance\@uter\thickn@ss
+     \g\divide\@uter\tw@
+     \hskip 0pt minus .5fil%
+     \vrule height\@uter depth\@nner width\thickn@ss
+     \vrule height\@uter depth-\@nner width#1%
+     \hskip 0pt minus 1fil%
+     \vrule height-\@nner depth\@uter width#1%
+     \vrule height\@nner depth\@uter width\thickn@ss
+     \hskip 0pt minus .5fil%
+     }% \hbox
+     }% \def
+
+% \s@ries takes two arguments. The first one is a name, say XXX, and            
+% the second is a series of arguments, devided by two slashs (//).              
+% \s@ries assigns this last series of arguments one after another to the        
+% control sequences \XXXi, \XXXii, and so on. Furthermore, a control           
+% sequence \XXX is defined, which takes a number k as its argument and          
+% expands to \XXXk', where k' is the roman numeral equivalent to k.             
+
+\def\s@ries#1#2{%                                                               
+     \g\t@mpcnta1                                                               
+     \gdef\t@mp{#1}%                                                            
+     \@ssign#2/\l@st  % \l@st is a sentinal element                                                        
+     \expandafter\gdef\csname#1\endcsname##1{%                                  
+                      \csname#1\romannumeral##1\endcsname}%                     
+     }                                                                          
+                                                                                
+\def\@ssign#1/#2{%
+      \expandafter\gdef\csname\t@mp\romannumeral\t@mpcnta\endcsname{#1}%    
+      \g\advance\t@mpcnta\@ne                                            
+      \ifx#2\l@st                                                               
+          \g\let\n@xt\relax                                                     
+     \else\g\let\n@xt\@ssign                                                    
+       \fi                                                                      
+      \n@xt}
+                                                                                 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Allocation of internal registers                                     %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+\newdimen\leftdist                                                              
+\newdimen\rightdist                                                             
+\newbox\TeXTree                                                                 
+                                                                                
+\newcount\sl@pe                                                                 
+\newcount\l@vels                                                                
+\newcount\s@ze                                                                  
+                                                                                
+\newbox\circleb@x                                                               
+\newbox\squareb@x                                                               
+\newbox\dotb@x                                                                  
+\newbox\triangleb@x
+\newbox\textb@x                                                             
+\newbox\frameb@x
+                                                                                
+\newdimen\circlew@dth                                                           
+\newdimen\squarew@dth                                                           
+\newdimen\dotw@dth                                                              
+\newdimen\trianglew@dth                                                         
+\newdimen\textw@dth                                                             
+\newdimen\framew@dth
+                                                         
+\newdimen\vd@st                                                                 
+\newdimen\hd@st                                                                 
+\newdimen\based@st                                                              
+\newdimen\dummyhalfcenterdim@n                                                  
+                                                                                
+\newcount\t@mpcnta                                                              
+\newcount\t@mpcntb                                                              
+\newcount\t@mpcntc                                                              
+\newcount\t@mpcntd                                                              
+\newdimen\t@mpdima                                                              
+\newdimen\t@mpdimb                                                              
+\newdimen\t@mpdimc                                                              
+\newbox\t@mpboxa                                                                
+\newbox\t@mpboxb                                                                
+                                                                                
+\newbox\leftb@x                                                                 
+\newbox\rightb@x                                                                
+\newbox\centerb@x                                                               
+\newbox\beneathb@x                                                              
+\newtoks\typ@                                                                   
+\newbox\centerb@@x                                                              
+\newdimen\centerdim@n                                                           
+\newdimen\halfcenterdim@n                                                       
+                                                                                
+\newdimen\mins@p                                                                
+\newdimen\halfmins@p                                                            
+\newdimen\tots@p                                                                
+\newdimen\halftots@p                                                            
+\newdimen\currs@p                                                               
+\newdimen\adds@p                                                                
+\newcount\l@ftht                                                                
+\newcount\r@ghtht                                                               
+\newcount\l@ftinfo                                                              
+\newcount\r@ghtinfo                                                             
+\newbox\l@ftbox                                                                 
+\newbox\r@ghtbox                                                                
+                                                                                
+\newif\ifr@ghthigher  % true iff the right subtree is higher than the left one  
+\newif\ifadds@p                                                                 
+                                                                                
+\newcount\@larg                                                                 
+\newcount\@rarg                                                                 
+                                                                                
+\newif\ifl@fttop                                                                
+\newif\ifl@ftonly                                                               
+\newif\ifr@ghtonly                                                              
+\newif\if@xt                                                                    
+\newif\ifl@ftedge                                                               
+\newif\ifr@ghtedge                                                              
+\newif\ifext@nded                                                               
+                                                                                
+\newdimen\lm@ff                                                                 
+\newdimen\rm@ff                                                                 
+\newdimen\lb@ff                                                                 
+\newdimen\rb@ff                                                                 
+\newdimen\lt@p                                                                  
+\newdimen\rt@p                                                                  
+                                                                                
+\newcount\l@sttreebox     % These four counter allocations have been copied
+\newcount\l@sttreeheight  % to this position from the \Tree command
+\newcount\l@stdiminfo     % (vs. 2.1). Previously each tree allocated its own
+\newcount\l@sttreetype    % counters, using up counters for nothing.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Slope handling for the edges                                         %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+% The picture environment of LaTeX gives us a choice of 24 positive             
+% slopes for lines (i.e. edges of trees in this context),                       
+% including vertical ones. The slope of a line is                               
+% given by an x- and an y-value, see L. Lamport, LaTeX, pp. 105f for            
+% further details. x/y can have the following values (decreasing amount         
+% of slope): 0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1 6/5 5/4        
+% 4/3 3/2 5/3 2/1 5/2 3/1 4/1 5/1 6/1.                                          
+% The x-values are allocated to \xv@li, \xv@lii,..., \xv@lxxiv, and             
+% they can conveniently be accessed by the command \xv@l{<number>}.             
+% The same holds for the y-values.                                              
+                                                                                
+\s@ries{xv@l}{0//1//1//1//1//2//1//3//2//3//4//5//1//6//%                       
+              5//4//3//5//2//5//3//4//5//6}                                     
+\s@ries{yv@l}{1//6//5//4//3//5//2//5//3//4//5//6//1//5//%                       
+              4//3//2//3//1//2//1//1//1//1}                                     
+                                                                                
+% \hv@ldef calculates \hv@li, \hv@lii,..., \hv@lxxiv for a given dimen          
+% \vd@st according to the following picture:                                    
+%                                                                               
+%          /-|                                                                  
+%         /  |                                                                  
+%        /   |                                                                  
+%       /    |                                                                  
+%      /     |\vd@st                                                            
+%     /      |                                                                  
+%    /       |                                                                  
+%   / -|     |                                                                  
+%  /   |\yv@l|                                                                  
+% /   _|    _|                                                                  
+%                                                                               
+% |___|                                                                         
+% \xv@l                                                                         
+% |_________|                                                                   
+%  .5\hv@l                                                                      
+%                                                                               
+% \hv@li,..., \hv@lxxiv are initialized in \beginTree, when the                 
+% actual value for \vd@st is known (\vd@st will depend on the point size of     
+% the picture). As before, these values can conveniently be accessed by the     
+% command \hv@l{<number>}.                                                      
+                                                                                
+\def\hv@ldef{%                                                                  
+     \for\t@mpcnta:=1\to24%                                                     
+      \do\g\t@mpdima\vd@st\g\multiply\t@mpdima by\xv@l{\t@mpcnta}%              
+         \g\divide\t@mpdima by\yv@l{\t@mpcnta}\g\multiply\t@mpdima by 2         
+         \expandafter\gxdef\csname hv@l\romannumeral\t@mpcnta\endcsname{%       
+                          \the\t@mpdima}%                                       
+      \od}                                                                      
+                                                                                
+\def\hv@l#1{\csname hv@l\romannumeral#1\endcsname}                              
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Naming trees                                                         %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+% A TeXtree is stored in TeX's internal registers in the following way:         
+% A TeXtree of height h has associated to itself the following internal         
+% TeX registers: a box, holding the graphical appearance of the tree,           
+% a consecutive number of 6+2h internal dimen registers, holding the        
+% additional information about the contour of the tree, a counter               
+% holding the height h of the tree, a counter holding the first                 
+% position of the additional information registers, and a toks register         
+% holding the type of the node (circle, square, dot, triangle, text, or frame).              
+% The height and position                                                       
+% of additional information are stored in consecutive order for                 
+% consecutive trees. The same is true for the boxes and toks.                   
+                                                                                
+% Four key numbers, the register numbers (addresses)
+% for the height, diminfo, box, and type 
+% of a tree, enable you to access all information which is stored about the     
+% tree. For the last tree on the stack, the four key numbers are stored in the  
+% counters \l@sttreeheight, \l@stdiminfo, \l@sttreebox, and \l@sttreetype,      
+% the key numbers for the next tree are \l@sttreeheight-2, \l@stdiminfo-2,      
+% \l@sttreebox-1, and \l@sttreetype-1, and so on.                                 
+                                                                                
+% The macro \n@metree gives names to some registers associated with the tree.   
+% The tree to be named is specified by its four key numbers. \n@metree takes    
+% five arguments, namely the keynumbers for height, info, box and type of the   
+% tree, and the name to be given to the tree. If the tree gets the name XXX and 
+% the key numbers are h, i, b, and t, the commands on the left side of the      
+% following list get the meaning on the right side.                             
+                                                                                
+% \XXXht	<---	\count h                                                          
+% \XXXinfo	<---	\count i                                                        
+% \XXXbox	<---	b                                                                
+% \XXXtype	<---	\toks t                                                         
+% \XXXlmoff	<---	\dimen f          where f is the address stored                
+%                                         in \count i                           
+% \XXXrmoff	<---	\dimen (f+1)                                                   
+% \XXXlboff	<---	\dimen (f+2)                                                   
+% \XXXrboff	<---	\dimen (f+3)                                                   
+% \XXXltop	<---	\dimen (f+4)                                                    
+% \XXXrtop	<---	\dimen (f+5)                                                    
+% \XXXloff	<---	\dimen (f+4+2g)   where g is the height stored in               
+% 					  \count h, i.e. \dimen (f+4+2g)                                         
+%  					  holds loff(1) of the tree, if g>0                                           
+% \XXXroff	<---	\dimen (f+5+2g)                                                 
+                                                                                
+% The macro \pr@vioustree sets \l@sttreeheight, \l@stdiminfo,                   
+% \l@sttreebox and \l@sttreetype to the key numbers of the previous tree        
+% and gives the name `l@st' to this tree.                                       
+                                                                                
+% The macro \@ddname which has two names n1 and n2 as arguments, gives          
+% the tree with name n1 the additional name n2.                                 
+                                                                                
+% The macro \n@mel@st gives the name `l@st' to the tree with the                
+% key numbers \l@sttreeheight, \l@stdiminfo, \l@sttreebox and \l@sttreetype.    
+                                                                                
+% The macro \n@xttree sets \l@sttreebox, \l@sttreeheight, \l@stdiminfo,         
+% \count\l@stdiminfo, and \l@sttreetype to the next free position.              
+                                                                                
+% The macro \@ppenddummy pushs a dummy onto the stack and names it `l@st'.      
+% The dummy has height -1, its box is the empty box, its type is circle,         
+% and all dimensions are 0pt.                                                   
+                                                                                
+% \p@s#1#2#3 sets counter #1 to position #2 of tree #3. #1 must be a counter,   
+% #3 must be a name for the tree. If the tree has the name XXX, \XXXinfo        
+% must be a number holding the first position of the dimen-parameters of        
+% the tree and \XXXht must hold the height of the tree.                         
+% #2 must be one of the following control sequences indicating the              
+% desired position: \lmoff, \rmoff, \lboff, \rboff, \ltop, \rtop, \loff, or     
+% \roff. \loff and \roff give the left resp. right offset of the *top*          
+% level of the tree.                                                            
+                                                                                
+\def\p@s#1#2#3{%                                                                
+     \g#1\csname#3info\endcsname                                                
+     \gxdef\t@mp{\csname#3ht\endcsname}%                                        
+     \ifnum\t@mp<0 \gxdef\t@mp{0}\fi                                            
+     #2{#1}%                                                                    
+     }                                                                          
+                                                                                
+\chardef\@lmoff0 \chardef\@rmoff1 \chardef\@ltop4 \chardef\@rtop5               
+\chardef\@lboff2 \chardef\@rboff3 \chardef\@loff4 \chardef\@roff5               
+                                                                                
+\def\lmoff#1{\g\advance#1 by\@lmoff}                                            
+\def\rmoff#1{\g\advance#1 by\@rmoff}                                            
+\def\lboff#1{\g\advance#1 by\@lboff}                                            
+\def\rboff#1{\g\advance#1 by\@rboff}                                            
+\def\ltop#1{\g\advance#1 by\@ltop}                                              
+\def\rtop#1{\g\advance#1 by\@rtop}                                              
+\def\loff#1{\g\advance#1 by\@loff\g\advance#1 by\t@mp                           
+     \g\advance#1 by\t@mp\relax}                                                
+\def\roff#1{\g\advance#1 by\@roff\g\advance#1 by\t@mp                           
+     \g\advance#1 by\t@mp\relax}                                                
+                                                                                
+% \n@meinfo#1 defines for an argument XXX (name of a tree) \XXXlmoff,           
+% \XXXrmoff, ... as lmoff(XXX), rmoff(XXX),... .                                
+% The following arguments will be used: l@ft, r@ght, l@st,                      
+% m@n, and m@x.                                                                 
+                                                                                
+\def\n@meinfo#1{%                                                               
+     \n@me@nfo{#1}{lmoff}\n@me@nfo{#1}{rmoff}%                                  
+     \n@me@nfo{#1}{lboff}\n@me@nfo{#1}{rboff}%                                  
+     \n@me@nfo{#1}{ltop}\n@me@nfo{#1}{rtop}%                                    
+     \n@me@nfo{#1}{loff}\n@me@nfo{#1}{roff}%                                    
+     }                                                                          
+                                                                                
+\def\n@me@nfo#1#2{%                                                             
+     \p@s\t@mpcnta{\csname#2\endcsname}{#1}%                                    
+     \expandafter\gxdef\csname#1#2\endcsname{\dimen\the\t@mpcnta}}              
+                                                                                
+\def\n@metree#1#2#3#4#5{%                                                       
+     \expandafter\gxdef\csname#5ht\endcsname{\count\the#1}%                     
+     \expandafter\gxdef\csname#5info\endcsname{\count\the#2}%                   
+     \expandafter\gxdef\csname#5box\endcsname{\the#3}%                          
+     \expandafter\gxdef\csname#5type\endcsname{\toks\the#4}%                    
+     \n@meinfo{#5}%                                                             
+     }                                                                          
+                                                                                
+\chardef\@cntoff3 \chardef\@boxoff1 \chardef\@dimoff2 \chardef\@typeoff1        
+                                                                                
+\def\pr@vioustree{%                                                             
+     \g\advance\l@sttreeheight by-\@cntoff                                      
+     \g\advance\l@stdiminfo by-\@cntoff                                         
+     \g\advance\l@sttreetype by-\@cntoff                                        
+     \g\advance\l@sttreebox by-\@boxoff                                         
+     \n@mel@st                                                                  
+     }                                                                          
+                                                                                
+\def\@ddname#1#2{%                                                              
+     \expandafter\gxdef\csname#2ht\endcsname{\csname#1ht\endcsname}%            
+     \expandafter\gxdef\csname#2info\endcsname{\csname#1info\endcsname}%        
+     \expandafter\gxdef\csname#2type\endcsname{\csname#1type\endcsname}%        
+     \expandafter\gxdef\csname#2box\endcsname{\csname#1box\endcsname}%          
+     \n@meinfo{#2}%                                                             
+     }                                                                          
+                                                                                
+\def\n@xttree{%                                                                 
+     \p@s\t@mpcnta\loff{l@st}\g\advance\t@mpcnta by\@dimoff                     
+     \g\advance\l@sttreeheight by\@cntoff                                       
+     \g\advance\l@stdiminfo by\@cntoff                                          
+     \g\advance\l@sttreetype by\@cntoff                                         
+     \g\advance\l@sttreebox by\@boxoff                                          
+     \g\count\l@stdiminfo\t@mpcnta                                              
+     }                                                                          
+                                                                                
+\def\@ppenddummy{% pushs a dummy onto the stack and names it `l@st'             
+                 % The dummy has height -1, its box is the empty box, the type   
+                 % is circle, and all dimensions are 0pt.                       
+     \n@xttree \g\count\l@sttreeheight-\@ne\n@mel@st                            
+     \l@sttype{circle}%                                                         
+     \g\setbox\l@stbox\copy\voidb@x                                             
+     \g\l@stlmoff=0pt\g\l@strmoff=0pt\g\l@stlboff=0pt\g\l@strboff=0pt%          
+     \g\l@stltop=0pt\g\l@strtop=0pt\g\l@stloff=0pt\g\l@stroff=0pt%              
+     }                                                                          
+                                                                                
+\def\g@tchildren{% enables us to talk about the left and the right child
+                 % (names l@ft resp. r@ght) and the smaller and the larger
+                 % child (names m@n resp. m@x)                                                             
+     \ifl@fttop\@ddname{l@st}{l@ft}%                                            
+               \pr@vioustree                                                    
+               \@ddname{l@st}{r@ght}%                                           
+          \else\@ddname{l@st}{r@ght}%                                           
+               \pr@vioustree                                                    
+               \@ddname{l@st}{l@ft}%                                            
+            \fi                                                                 
+     \ifnum\r@ghtht>\l@ftht\relax                                               
+               \r@ghthighertrue                                                 
+               \@ddname{r@ght}{m@x}%                                            
+               \@ddname{l@ft}{m@n}%                                             
+          \else\r@ghthigherfalse                                                
+               \@ddname{l@ft}{m@x}%                                             
+               \@ddname{r@ght}{m@n}%                                            
+            \fi                                                                 
+               }                                                                
+                                                                                
+\def\n@mel@st{%                                                                 
+     \n@metree\l@sttreeheight\l@stdiminfo\l@sttreebox\l@sttreetype{l@st}}       
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Initialization of the tree environment                               %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+\def\beginTree{%                                                                
+     \begingroup                                                                
+     \unitlength 1pt%                                                           
+     \divide\unitlength by 65536
+     \l@sttreebox\count14                                                       
+     \l@sttreeheight\count10                                                    
+     \advance\l@sttreeheight by \@ne                                            
+     \count\l@sttreeheight=-1                                                   
+     \l@stdiminfo\l@sttreeheight                                                
+     \advance\l@stdiminfo by \@ne                                               
+     \count\l@stdiminfo\count11                                                 
+     \advance\count\l@stdiminfo by -5                                           
+     \l@sttreetype\l@stdiminfo                                                  
+     \advance\l@sttreetype by\@ne                                               
+     \count\l@sttreetype\count15                                                
+     \n@mel@st\ignorespaces                                                     
+     }                                                                          
+                                                                                
+\let\Tree\beginTree                                                             
+                                                                                
+\def\endTree{%                                                                  
+     \g\leftdist-\l@stlmoff\g\advance\leftdist by \l@stltop                     
+     \g\rightdist\l@strmoff\g\advance\rightdist by\l@strtop                     
+     \g\setbox\TeXTree\box\l@stbox\endgroup\ignorespaces}                       
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Specification of nodes                                               %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+% A node is defined by the command \node{<specifications>}.                     
+% <specifications> defines the labels, graphical appearence and the order       
+% of the node and the thickness of the edges.                                   
+% Labels are defined by the commands \lft, \rght, \cntr,                        
+% and \bnth. The specification of empty labels may be omitted.                  
+% The graphical appearence is defined by the command \type{<type>}.             
+% <type> can have the values `circle', `square', `dot',                         
+% `triangle', 'text', or 'frame'. The thickness of the edges is defined by                      
+% \leftthick and \rightthick that give thick edges instead of the               
+% normal thin ones. Furthermore,                                                
+% the order of the node is given by the following commands:                     
+% \external (if the node is an external node), \leftonly (if the node has a     
+% left successor only), \rightonly (analogous), \unary (if the node is an       
+% unary one), and \lefttop (the                                                 
+% node which has been defined before this one, is supposed to be the left       
+% successor instead of the right one).                                          
+% Default: two children, no labels, type circle, thin edges,                    
+% left child has been entered first.                                            
+                                                                                
+\def\th@ck{\let\@linefnt\tenlnw                                                 
+     \@wholewidth\fontdimen8\tenlnw\@halfwidth.5\@wholewidth}                   
+                                                                                
+\def\leftthick{\g\let\l@ftthick\th@ck}                                          
+\def\rightthick{\g\let\r@ghtthick\th@ck}                                        
+\def\lft#1{\g\setbox\leftb@x\hbox{#1\ }}                                        
+\def\rght#1{\g\setbox\rightb@x\hbox{\ #1}}                                      
+\def\cntr#1{\g\setbox\centerb@x\hbox{#1\strut}}                   
+\def\bnth#1{\g\setbox\beneathb@x\hbox to0pt{\hss\strut#1\hss}}                        
+\def\type#1{%                                                                   
+     \g\setbox\centerb@@x\copy\csname#1b@x\endcsname                            
+     \g\centerdim@n\csname#1w@dth\endcsname                                     
+     \typ@{#1}%                                                                 
+     \g\halfcenterdim@n=.5\centerdim@n}                                         
+                                                                                
+\def\ext@nded{\g\ext@ndedfalse} % This definition must precede                  
+                                % \input TreeTeX.sty  (outdated now!)                           
+                                                                                
+\def\node#1{%                                                                   
+     %%% Initialization (node type and labels), defaults and actual values      
+     \g\setbox\leftb@x\copy\voidb@x                                             
+     \g\setbox\rightb@x\copy\voidb@x                                            
+     \g\setbox\centerb@x\copy\voidb@x                                           
+     \g\setbox\beneathb@x\copy\voidb@x                                          
+     \type{circle}%                                                             
+     \g\l@fttopfalse\g\l@ftonlyfalse\g\l@ftedgetrue                             
+     \g\r@ghtonlyfalse\g\r@ghtedgetrue\g\@xtfalse\ext@nded\n@dummy              
+     \g\let\l@ftthick\relax\g\let\r@ghtthick\relax                              
+     #1% 
+     \@pdcenter                                                                       
+     \d@mmy
+     \n@de
+     \ignorespaces                                                              
+     }
+
+\def\@pdcenter{\csname\the\typ@ @cntr\endcsname}
+
+\let\circle@cntr\relax
+\let\square@cntr\relax
+\let\triangle@cntr\relax
+\let\dot@cntr\relax
+
+\def\text@cntr{%
+     \g\centerdim@n\wd\centerb@x
+     \g\halfcenterdim@n.5\centerdim@n}                                                                          
+     
+\def\frame@cntr{% 
+     \g\setbox\centerb@x\hbox{\ \unhcopy\centerb@x\ }
+     \g\centerdim@n\wd\centerb@x
+     % \g\advance\centerdim@n\fontdimen2\font       
+     \g\halfcenterdim@n.5\centerdim@n
+     \g\setbox\centerb@@x\rect@ngle{\centerdim@n}{\squarew@dth}{.4pt}}
+                                                                           
+\def\leftonly{\g\l@ftonlytrue\g\r@ghtedgefalse\g\let\d@mmy\l@ftdummy}           
+\def\rightonly{\g\r@ghtonlytrue\g\l@ftedgefalse\g\let\d@mmy\r@ghtdummy}         
+\def\unary{\g\r@ghtedgefalse\g\let\d@mmy\@ndummy}                               
+\def\external{\g\@xttrue\g\l@ftedgefalse\g\r@ghtedgefalse\g\let\d@mmy\@xtdummy} 
+                                                                                
+\def\lefttop{\g\l@fttoptrue}                                                    
+                                                                                
+\def\@xtdummy{%                                                                 
+     \@ppenddummy                                                     
+     \g\l@strtop-\halfmins@p                                         
+     \@ppenddummy
+     \g\l@stltop-\halfmins@p                                         
+     }                                                                          
+                                                                                
+\def\n@dummy{\g\let\d@mmy\relax}                                                
+                                                                                
+\def\l@ftdummy{% cf. \g@tposition                                                               
+     \@ppenddummy                                                      
+     \g\l@stltop=\dummyhalfcenterdim@n                                          
+     \g\l@strtop=\dummyhalfcenterdim@n                                          
+     }                                                                          
+                                                                                
+\def\r@ghtdummy{% cf. \g@tposition                                                              
+     \lefttop                                                                   
+     \@ppenddummy                                                      
+     \g\l@stltop=\dummyhalfcenterdim@n                                          
+     \g\l@strtop=\dummyhalfcenterdim@n                                          
+     }                                                                          
+                                                                                
+\def\@ndummy{%                                                                  
+     \g\t@mpdima\l@strtop\relax                                                 
+     \@ppenddummy                                                     
+     \g\l@stltop-\mins@p\g\advance\l@stltop by-\t@mpdima                        
+     \g\l@strtop=\t@mpdima                                                      
+     }                                                                          
+                                                                                
+\def\n@de{%                                                                     
+     \g@tposition       % naming children and calculating \sl@pe and \tots@p    
+     \g@tlt@p\g@trt@p   % calculating \lt@p and \rt@p                           
+     \g@tlm@ff\g@trm@ff % calculating \lm@ff and \rm@ff                         
+     \g@tlb@ff\g@trb@ff % calculating \lb@ff and \rb@ff                         
+     \@pdlroff          % updating loff and roff for all levels but the top one 
+     \@pdloffl\@pdroffl % updating loff(1) and roff(1) of the parent tree             
+     \@pddim            % updating ltop, rtop, lmoff, rmoff, lboff, and rboff   
+     \@pdinfo\@pdht     % updating diminfo and treeheight                       
+     \@pdbox            % updating treebox                                      
+     \@pdtype           % updating type                                         
+     \n@mel@st          % giving the name `l@st' to the new tree 
+     \ignorespaces                                                              
+     }                                                                          
+                                                                                
+\def\g@tposition{% naming children and calculating \sl@pe, \tots@p, and node offsets
+     \g@tchildren\c@lcsep\c@lcslope\c@lcoffsets
+     \ifext@nded\relax                                                          
+           \else\ifl@ftonly\g\r@ghtrtop=-\tots@p                                
+                           \g\advance\r@ghtrtop by\l@ftrtop                     
+                        \fi                                                     
+                \ifr@ghtonly\g\l@ftltop=-\tots@p                                
+                            \g\advance\l@ftltop by\r@ghtltop                    
+                         \fi                                                    
+             \fi % cf. \l@ftdummy and \r@ghtdummy                                                               
+     }                                                                          
+                                                                                
+\def\@pdinfo{% updating diminfo                                                 
+     \g\l@stinfo=\m@xinfo\relax                                                 
+     }                                                                          
+                                                                                
+\def\@pdht{% updating treeheight                                                
+     \g\l@stht=\m@xht                                                           
+     \g\advance\l@stht by\@ne                                                   
+     }                                                                          
+                                                                                
+\def\@pdtype{% updating type                                                    
+     \g\l@sttype\typ@                                                           
+     }                                                                          
+                                                                                
+\def\g@tlt@p{% calculating \lt@p                                                
+     \g\lt@p\wd\leftb@x\g\advance\lt@p by\halfcenterdim@n                       
+     }                                                                          
+                                                                                
+\def\g@trt@p{% calculating \rt@p                                                
+     \g\rt@p\wd\rightb@x\g\advance\rt@p by\halfcenterdim@n                      
+     }                                                                          
+                                                                                
+\def\g@tlm@ff{% calculating \lm@ff                                              
+     % \lm@ff:=lmoff(left tree)-ltop(left tree)                                 
+     %          -.5\tots@p+\lt@p                                                
+     \g\lm@ff\l@ftlmoff                                                         
+     \g\advance\lm@ff by-\l@ftltop                                              
+     \g\advance\lm@ff by-\halftots@p                                            
+     \g\advance\lm@ff by\lt@p\relax                                             
+     % if ht(left tree) < ht(right tree)                                        
+     %    \t@mpdima:=lmoff(right tree)-ltop(right tree)+.5\tots@p+\lt@p         
+     %    \lm@ff:=min(\lm@ff,\t@mpdima) fi                                      
+     \ifnum\l@ftht<\r@ghtht\relax                                               
+           \g\t@mpdima\r@ghtlmoff                                               
+           \g\advance\t@mpdima by-\r@ghtltop                                    
+           \g\advance\t@mpdima by\halftots@p                                    
+           \g\advance\t@mpdima by\lt@p\relax                                    
+           \ifdim\t@mpdima<\lm@ff\relax                                         
+                 \g\lm@ff\t@mpdima                                              
+              \fi                                                               
+        \fi                                                                     
+     % \lm@ff:=min(\lm@ff,0pt)                                                  
+     \ifdim0pt<\lm@ff\relax                                                     
+           \g\lm@ff=0pt%                                                        
+        \fi                                                                     
+     }                                                                          
+                                                                                
+\def\g@trm@ff{% calculating \rm@ff                                              
+     % analog to lm@ff                                                          
+     % \rm@ff:=rmoff(right tree)+rtop(right tree)                               
+     %         +.5\tots@p-\rt@p                                                 
+     \g\rm@ff\r@ghtrmoff                                                        
+     \g\advance\rm@ff by\r@ghtrtop                                              
+     \g\advance\rm@ff by\halftots@p                                             
+     \g\advance\rm@ff by-\rt@p\relax                                            
+     % \t@mpdima:=rmoff(left tree)+rtop(left tree)-.5\tots@p-\rt@p              
+     \ifnum\r@ghtht<\l@ftht\relax                                               
+           \g\t@mpdima\l@ftrmoff                                                
+           \g\advance\t@mpdima by\l@ftrtop                                      
+           \g\advance\t@mpdima by-\halftots@p                                   
+           \g\advance\t@mpdima by-\rt@p\relax                                   
+           \ifdim\t@mpdima>\rm@ff\relax                                         
+                 \g\rm@ff\t@mpdima                                              
+              \fi                                                               
+        \fi                                                                     
+     % \rm@ff:=max(\rm@ff,0pt)                                                  
+     \ifdim0pt>\rm@ff\relax                                                     
+           \g\rm@ff=0pt                                                         
+        \fi                                                                     
+     }                                                                          
+                                                                                
+\def\g@tlb@ff{% calculating \lb@ff                                              
+     % \lb@ff:=lboff(right tree)-ltop(right tree)+.5\tots@p+\lt@p               
+     %  resp.:=lboff(left tree)-ltop(left tree)                                 
+     %         -.5\tots@p+\lt@p 
+     \if@xt\g\lb@ff0pt%
+      \else\ifnum\l@ftht<\r@ghtht\relax                                               
+                 \g\lb@ff\r@ghtlboff                                                  
+                 \g\advance\lb@ff by-\r@ghtltop                                       
+                 \g\advance\lb@ff by\halftots@p                                       
+                 \g\advance\lb@ff by\lt@p\relax                                       
+            \else\g\lb@ff\l@ftlboff                                                   
+                 \g\advance\lb@ff by-\l@ftltop                                        
+                 \g\advance\lb@ff by-\halftots@p                                      
+                 \g\advance\lb@ff by\lt@p\relax                                       
+              \fi
+        \fi                                                                     
+     }                                                                          
+                                                                                
+\def\g@trb@ff{% calculating \rb@ff                                              
+     % \rb@ff:=rboff(left tree)+rtop(left tree)-.5\tots@p-\rt@p                 
+     %  resp.:=rboff(right tree)+rtop(right tree)                               
+     %         +.5\tots@p-\rt@p                                                 
+     \if@xt\g\rb@ff0pt%
+      \else\ifnum\r@ghtht<\l@ftht\relax                                               
+                 \g\rb@ff\l@ftrboff                                                   
+                 \g\advance\rb@ff by\l@ftrtop                                         
+                 \advance\rb@ff by-\halftots@p                                        
+                 \g\advance\rb@ff by-\rt@p\relax                                      
+            \else\g\rb@ff\r@ghtrboff                                                  
+                 \g\advance\rb@ff by\r@ghtrtop                                        
+                 \g\advance\rb@ff by\halftots@p                                       
+                 \g\advance\rb@ff by-\rt@p\relax                                      
+              \fi
+        \fi                                                                     
+     }                                                                          
+                                                                                
+\def\@pdlroff{% updating loff and roff for all levels but the top one           
+     % if right tree higher \t@mpdima:=-ltop(right tree)                        
+     %                      \t@mpdimb:=lboff(left tree)-ltop(left tree)         
+     %                      % \t@mpdimb holds the offset between the node       
+     %                      % and the left edge of the bottom of the left tree  
+     %                 else \t@mpdima:=rtop(left tree)                          
+     %                      \t@mpdimb:=lboff(right tree)+rtop(right tree)       
+     %                      % substitute left by right                          
+     %                   fi                                                     
+     \ifr@ghthigher\g\t@mpdima-\r@ghtltop\relax                                 
+                   \g\t@mpdimb\l@ftlboff                                        
+                   \g\advance\t@mpdimb by-\l@ftltop\relax                       
+              \else\g\t@mpdima\l@ftrtop\relax                                   
+                   \g\t@mpdimb\r@ghtlboff                                       
+                   \g\advance\t@mpdimb by\r@ghtrtop\relax                       
+                \fi                                                             
+     \ifr@ghthigher\p@s\t@mpcnta\loff{m@n}% pointer to loff(1) of smaller tree  
+                   \p@s\t@mpcntb\loff{m@x}% pointer to loff(1) of larger tree  
+              \else\p@s\t@mpcnta\roff{m@n}% pointer to roff(1) of smaller tree  
+                   \p@s\t@mpcntb\roff{m@x}% pointer to roff(1) of larger tree  
+                \fi  % if the right tree is the higher one you have to shift    
+                     % the left profile of the smaller tree, otherwise the      
+                     % right one                                                
+     % For every level, \t@mpdima contains the offset between the node of the   
+     % higher tree and the inner edge of the next level. Furthermore, if the    
+     % right tree is the higher one, the left profile of the left tree becomes  
+     % the upper part of the left profile of the parent tree, otherwise         
+     % substitute `left' by `right.'                                            
+     \ex\m@nht\times                                                            
+        \g\advance\t@mpdima by\dimen\t@mpcntb                                   
+        \g\dimen\t@mpcntb\dimen\t@mpcnta                                        
+        \g\advance\t@mpcnta by-\@dimoff                                         
+        \g\advance\t@mpcntb by-\@dimoff\relax                                   
+     \xe                                                                        
+     % The link between the last outer level of the smaller tree and the next   
+     % level of the higher one:                                                 
+     % \dimen\t@mpcntb:=\dimen\t@mpcntb+\t@mpdima+\tots@p-\t@mpdimb             
+     %                   if left tree is smaller than right tree                
+     %              resp.\dimen\t@mpcntb+\t@mpdima-\tots@p-\t@mpdimb            
+     %                   if right tree is smaller than left tree                
+     \ifnum\m@xht=\m@nht\relax                                                  
+      \else\g\advance\dimen\t@mpcntb by\t@mpdima                                
+           \ifnum\l@ftht<\r@ghtht\relax                                         
+                 \g\advance\dimen\t@mpcntb by\tots@p                            
+            \else\g\advance\dimen\t@mpcntb by-\tots@p                           
+              \fi                                                               
+           \g\advance\dimen\t@mpcntb by-\t@mpdimb                               
+        \fi                                                                     
+     }                                                                          
+                                                                                
+\def\@pdloffl{% updating loff(1) of parent tree                                 
+     % loff(1) of parent tree:=+\lt@p-.5\tots@p-ltop(left tree)                 
+     \p@s\t@mpcnta\loff{m@x}%                                                   
+     \g\advance\t@mpcnta by \@dimoff\relax % pointer to loff(0) of parent tree  
+     \g\dimen\t@mpcnta\lt@p                                                     
+     \g\advance\dimen\t@mpcnta by-\halftots@p                                   
+     \g\advance\dimen\t@mpcnta by-\l@ftltop\relax                               
+     }                                                                          
+                                                                                
+\def\@pdroffl{% updating roff(1) of parent tree                                 
+     % roff(l) of parent tree:=-\rt@p+.5\tots@p+rtop(right tree)                
+     \p@s\t@mpcnta\roff{m@x}%                                                   
+     \g\advance\t@mpcnta by \@dimoff\relax % pointer to roff(0) of parent tree  
+     \g\dimen\t@mpcnta-\rt@p                                                    
+     \g\advance\dimen\t@mpcnta by\halftots@p                                    
+     \g\advance\dimen\t@mpcnta by\r@ghtrtop\relax                               
+     }                                                                          
+                                                                                
+\def\@pddim{% updating ltop, rtop, lmoff, rmoff, lboff, and rboff               
+     \g\m@xlmoff=\lm@ff\g\m@xrmoff=\rm@ff                                       
+     \g\m@xlboff=\lb@ff\g\m@xrboff=\rb@ff                                       
+     \g\m@xltop=\lt@p\g\m@xrtop=\rt@p                                           
+     }                                                                          
+                                                                                
+\def\@pdbox{% pushing the nodebox on the stack: updating treebox                
+     \g\@xarg\xv@l\sl@pe\g\@yarg\yv@l\sl@pe                                     
+     \ifnum\sl@pe=1 % vertical edge                                             
+           \g\t@mpdima\vd@st                                                    
+           \g\advance\t@mpdima by-\y@ff\typ@                                    
+           \g\advance\t@mpdima by-\y@ff\l@fttype                                
+           \g\@larg\t@mpdima % \@larg is a number register!                     
+           \g\t@mpdima\vd@st                                                    
+           \g\advance\t@mpdima by-\y@ff\typ@                                    
+           \g\advance\t@mpdima by-\y@ff\r@ghttype                               
+           \g\@rarg\t@mpdima % \@rarg is a number register!                     
+      \else\g\t@mpdima\halftots@p                                               
+           \g\advance\t@mpdima by-\x@ff\typ@                                    
+           \g\advance\t@mpdima by-\x@ff\l@fttype                                
+           \g\@larg\t@mpdima % \@larg is a number register!                     
+           \g\t@mpdima\halftots@p                                               
+           \g\advance\t@mpdima by-\x@ff\typ@                                    
+           \g\advance\t@mpdima by-\x@ff\r@ghttype                               
+           \g\@rarg\t@mpdima % \@rarg is a number register!                     
+        \fi                                                                     
+     \g\setbox\l@sttreebox\hbox{%
+           \ifvoid\leftb@x\relax
+             \else\hskip-\halfcenterdim@n\hskip-\wd\leftb@x
+                  \unhcopy\leftb@x\hskip\halfcenterdim@n
+               \fi
+           \ifvoid\centerb@x\relax
+             \else\g\t@mpdima-.5\wd\centerb@x\hskip\t@mpdima
+                  \unhbox\centerb@x\hskip\t@mpdima
+               \fi
+           \ifvoid\rightb@x\relax
+             \else\g\t@mpdima-\wd\rightb@x\hskip\halfcenterdim@n
+                  \unhbox\rightb@x\hskip\t@mpdima\hskip-\halfcenterdim@n
+               \fi
+           \raise\based@st\copy\centerb@@x
+           \if@xt\relax
+                 \lower\s@ze pt\hbox to0pt{\hss\unhbox\beneathb@x\hss}%
+            \else\hskip-\halftots@p
+                 \lower\vd@st\box\l@ftbox
+                 \ifl@ftedge\drawl@ftedge\else\hskip\halftots@p\fi
+                 \ifr@ghtedge\drawr@ghtedge\else\hskip\halftots@p\fi
+                 \lower\vd@st\box\r@ghtbox
+                 \hskip-\halftots@p
+              \fi
+           }% of hbox
+     }                                                                          
+                                                                                
+\def\drawl@ftedge{%                                                             
+           \hskip\x@ff\l@fttype                                                 
+           \g\t@mpdimc\y@ff\l@fttype\g\advance\t@mpdimc by\based@st
+           \g\advance\t@mpdimc-\vd@st
+           \raise\t@mpdimc                                                      
+           \hbox{\l@ftthick\lineseg(\@xarg,\@yarg){\@larg}}%
+           \hskip\x@ff\typ@                                                     
+     }                                                                          
+                                                                                
+\def\drawr@ghtedge{%                                                            
+           \hskip\x@ff\typ@                                                     
+           \g\t@mpdimc\vd@st                                                      
+           \g\advance\t@mpdimc by \based@st
+           \g\advance\t@mpdimc by -\y@ff\typ@\relax
+           \g\advance\t@mpdimc by- \vd@st
+           \raise\t@mpdimc                                                      
+           \hbox{\r@ghtthick\lineseg(\@xarg,-\@yarg){\@rarg}}% 
+           \hskip\x@ff\r@ghttype                                                
+     }                                                                          
+                                                                                
+\def\x@ff#1{%                                                                   
+     \csname\the#1x@ff\endcsname\sl@pe                                          
+     }                                                                          
+                                                                                
+\def\y@ff#1{%                                                                   
+     \csname\the#1y@ff\endcsname\sl@pe                                          
+     }                                                                          
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Calculating the separation of subtrees                               %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+% \c@lcslope will calculate the required slope of the edges                     
+% when the nodes are to be \vd@st apart vertically                              
+% and at least \tots@p apart horizontally. This slope is returned by            
+% the value of the counter \sl@pe (a number between 1 and 23).                  
+% Furthermore, \tots@p is updated in order to fit to this slope.                
+                                                                                
+\def\c@lcslope{%                                                                
+     \g\sl@pe1                                                                  
+       \loop                                                                    
+      \ifdim\hv@l\sl@pe < \tots@p                                               
+            \g\advance\sl@pe by1                                                
+     \repeat
+     \g\tots@p\hv@l\sl@pe                                                       
+     \g\halftots@p.5\tots@p}                                                    
+
+                                                                                
+\def\c@lcsep{%                                                                  
+     %%% \tots@p:=\mins@p + rtop(left tree) + ltop(right tree)                  
+     %%% \currs@p:=\mins@p                                                      
+     \g\tots@p\mins@p                                                           
+     \g\advance\tots@p by\l@ftrtop                                              
+     \g\advance\tots@p by\r@ghtltop\relax                                       
+     \g\currs@p\mins@p                                                          
+     %%% \t@mpcnta:= pointer to roff(0) of left tree                            
+     %%% \t@mpcntb:= pointer to loff(0) of right tree                           
+     \p@s\t@mpcnta\roff{l@ft}%                                                  
+     \p@s\t@mpcntb\loff{r@ght}%                                                 
+     %%% Calculate \currs@p and update \tots@p for each level of the           
+     %%% smaller tree                                                           
+     %%% If at any level the subtrees are as close or closer than at            
+     %%% the level of their roots, they will be moved apart by the additional   
+     %%% amount of \adds@p                                                      
+     \g\adds@pfalse                                                             
+     \g\t@mpcntc\m@nht                               
+     \ex\t@mpcntc\times                                                         
+        \g\advance\currs@p by-\dimen\t@mpcnta                                   
+        \g\advance\currs@p by \dimen\t@mpcntb                                   
+        \ifdim\mins@p<\currs@p                                                  
+         \else\g\adds@ptrue                                                     
+           \fi                                                                  
+        \ifdim\currs@p<\mins@p                                                  
+              \g\advance\tots@p by\mins@p                                       
+              \g\advance\tots@p by -\currs@p                                    
+              \g\currs@p\mins@p                                                 
+           \fi                                                                  
+        \g\advance\t@mpcnta by -\@dimoff                                        
+        \g\advance\t@mpcntb by -\@dimoff                                        
+     \xe                                                                        
+     \ifadds@p\g\advance\tots@p by\adds@p\fi}                                   
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Predefined trees                                                     %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+% \tri@ngle produces a triangle which covers \l@vels many level of a tree.      
+% The slope of the edges is given by \sl@pe, the reference point of the         
+% triangle is in the top, the width is 0pt.                                     
+                                                                                
+\def\tri@ngle{%                                                                 
+     \vtop{\g\@xarg\xv@l\sl@pe \g\@yarg\yv@l\sl@pe                              
+           \g\t@mpdimc\l@vels\vd@st 
+           \g\advance\t@mpdimc by .5\squarew@dth
+           \g\multiply\t@mpdimc\xv@l\sl@pe
+           \g\divide\t@mpdimc\yv@l\sl@pe
+           \g\@larg\t@mpdimc                                                    
+           \offinterlineskip                                                    
+           \vskip0pt% Force the reference point to the top                                                         
+           \hbox to0pt{\hss\lineseg(\@xarg,\@yarg){\@larg}%                     
+                       \hskip\t@mpdimc\rlap{\lineseg(-\@xarg,\@yarg){\@larg}}%  
+                       \hss}%                                                   
+           \setbox\t@mpboxa                                                          
+           \hbox to0pt{\hss\vrule height.2pt depth.2pt width2\t@mpdimc\hss}%
+           \t@mpdimc-.5\squarew@dth\advance\t@mpdimc\based@st
+           \ht\t@mpboxa0pt\dp\t@mpboxa\t@mpdimc\copy\t@mpboxa    
+          }%                                                                    
+     }                                                                          
+                                                                                
+\def\lvls#1{\g\l@vels#1}                                                        
+\def\slnt#1{\g\sl@pe#1}                                                         
+                                                                                
+\def\treesymbol#1{%                                                             
+     \g\setbox\leftb@x\copy\voidb@x                                             
+     \g\setbox\rightb@x\copy\voidb@x                                            
+     \g\setbox\centerb@x\copy\voidb@x                                           
+     \g\setbox\beneathb@x\copy\voidb@x                                          
+     \lvls{1}\slnt{3}%                                                          
+     #1%                                                                        
+     \g\centerdim@n\trianglew@dth                                               
+     \g\halfcenterdim@n.5\trianglew@dth                                         
+     \n@xttree                                                                  
+     \g\count\l@sttreeheight\l@vels% \g\advance\count\l@sttreeheight by\tw@  
+     \g\toks\l@sttreetype{triangle}%                                            
+     \n@mel@st                                                                  
+     \g\hd@st\hv@l\sl@pe \g\divide\hd@st by\tw@                                 
+     \g\l@stltop=\halfcenterdim@n\g\advance\l@stltop by\wd\leftb@x              
+     \g\l@strtop=\halfcenterdim@n\g\advance\l@strtop by\wd\rightb@x             
+     \g\l@stlboff=-\hd@st \g\multiply\l@stlboff by\l@vels   
+     \g\advance\l@stlboff by\wd\leftb@x
+     \g\l@strboff=\hd@st \g\multiply\l@strboff by\l@vels 
+     \g\advance\l@strboff by-\wd\rightb@x
+     \g\l@stlmoff=\l@stlboff\relax
+     \ifdim\l@stlmoff>0pt\relax\g\l@stlmoff=0pt\fi   
+     \g\l@strmoff=\l@strboff
+     \ifdim\l@strmoff<0pt\relax\g\l@strmoff=0pt\fi 
+     \g\t@mpcnta\l@stinfo\g\advance\t@mpcnta by6% preliminary                   
+     \ex\l@vels\times                                                           
+        \g\dimen\t@mpcnta-\hd@st\g\advance\t@mpcnta by\@ne                      
+        \g\dimen\t@mpcnta\hd@st\g\advance\t@mpcnta by\@ne                       
+     \xe                                                                        
+     \g\advance\t@mpcnta by-\tw@                                                
+     \g\advance\dimen\t@mpcnta by\wd\leftb@x                                    
+     \g\advance\t@mpcnta by\@ne                                                 
+     \g\advance\dimen\t@mpcnta by-\wd\rightb@x                                  
+     \g\setbox\l@stbox\vtop % to\l@vels\vd@st
+            {\offinterlineskip                   
+             \g\setbox\t@mpboxa                                                 
+             \hbox{\hskip-\halfcenterdim@n\hskip-\wd\leftb@x\unhbox\leftb@x
+                   \hskip\halfcenterdim@n
+                   \raise\based@st\tri@ngle
+                   \hskip\halfcenterdim@n\t@mpdima-\wd\rightb@x
+                   \unhbox\rightb@x\hskip\t@mpdima\hskip-\halfcenterdim@n}                                     
+             \g\ht\t@mpboxa=0pt\box\t@mpboxa                                    
+             \setbox\centerb@x\hbox to0pt{\hss\unhbox\centerb@x\hss}%
+             \ht\centerb@x0pt\dp\centerb@x0pt\box\centerb@x
+             \vskip\s@ze pt
+             \ht\beneathb@x0pt\box\beneathb@x                                                 
+             \vskip-\dp\beneathb@x\vskip-\ht\beneathb@x}%
+     \ignorespaces                                                              
+     }                                                                          
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Node sizes                                                           %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+% The algorithm (macros \@pdbox, \drawl@ftedge, \drawr@ghtedge) accesses the
+% horizontal and vertical offset fo any node type XXX (circle, square,
+% dot, triangle, text, and frame) via the macros \XXXx@ff resp. \XXXy@ff.
+% These two macros take the slope of the outgoing edges
+% of the current node as their argument. Though horizontal offsets can
+% be calculated from the vertical offsets and vice versa, there is no
+% room to do so in the \XXXx@ff or \YYYy@ff macros, because these macros
+% have to expand to a dimension!
+%
+% Let k be a <number>. Actually k will be the slope of the outgoing
+% edges of the current node.
+% 
+% There are three methods how, e.g., \XXXx@ff can be defined , depending
+% on the node type and the x- or y-orientation.
+% First, \XXXx@ff can be defined to expand to \XXXx@ffk', k' beeing
+% the roman numeral representation of the value of k, that in turn
+% expands to the appropriate dimension (example: \circley@ff).
+% In this case, \XXXx@ffi,...,\XXXx@ffiv are predefined by a \s@ries
+% command.
+% Second, \XXXx@ff can be defined to expand to a fixed dimension,
+% independent of its argument (example: \dotx@ff).
+% Third, the value of \XXXx@ff can be defined by the macro
+% \c@lcoffsets, when the slope k is already known. In this case,
+% the computation of \XXXx@ff makes use of the actual value
+% of k and possibly other offsets that are already predefined by method I
+% (examples: \circlex@ff, \squarex@ff).
+                                                                                
+\def\norm@ff{% everything set up for 10pt node size                                                                 
+\s@ries{circley@ff}{0.50000pt//0.49320pt//0.49029pt//0.48507pt//%               
+                    0.47434pt//0.46424pt//0.44721pt//0.42875pt//%               
+                    0.41603pt//0.40000pt//0.39043pt//0.38411pt//%               
+                    0.35355pt//0.32009pt//0.31235pt//0.30000pt//%               
+                    0.27735pt//0.25725pt//0.22361pt//0.18570pt//%               
+                    0.15811pt//0.12127pt//0.09806pt//0.08220pt}%                
+     }                                                                          
+                                                                                
+\def\dotx@ff#1{0pt}
+\def\doty@ff#1{0pt} 
+
+\def\trianglex@ff#1{0pt}
+\def\triangley@ff#1{0pt} 
+
+\def\c@lcoffsets{%
+     % \circlex@ff uses predefined \circley@ffi, \circley@ffii etc.
+     \ifnum\sl@pe=\@ne\relax
+           \xdef\circlex@ff##1{0pt}%
+      \else\g\t@mpcnta26 % number of slopes + 2
+           \g\advance\t@mpcnta-\sl@pe
+           \xdef\circlex@ff##1{\circley@ff\t@mpcnta}%
+        \fi
+     % \squarex@ff and \squarey@ff are computed directly from \sl@pe and \squarew@dth
+     \ifnum\sl@pe<13\relax % incoming edge meets upper border of a square node
+                           % (slope 13 corresponds to 45 degrees)
+           \g\t@mpdima.5\squarew@dth
+           \xdef\squarey@ff##1{\the\t@mpdima}%
+           \g\multiply\t@mpdima\xv@l\sl@pe
+           \g\divide\t@mpdima\yv@l\sl@pe
+           \xdef\squarex@ff##1{\the\t@mpdima}%
+      \else\g\t@mpdima.5\squarew@dth
+           \xdef\squarex@ff##1{\the\t@mpdima}%
+           \g\multiply\t@mpdima\yv@l\sl@pe
+           \g\divide\t@mpdima\xv@l\sl@pe
+           \xdef\squarey@ff##1{\the\t@mpdima}%
+        \fi
+     % \texty@ff is .5\squarew@dth, \textx@ff is adjusted accordingly
+     \g\t@mpdima.5\squarew@dth
+     \xdef\texty@ff##1{\the\t@mpdima}%
+     \g\multiply\t@mpdima\xv@l\sl@pe
+     \g\divide\t@mpdima\yv@l\sl@pe
+     \xdef\textx@ff##1{\the\t@mpdima}% 
+     \let\framex@ff\textx@ff
+     \let\framey@ff\texty@ff
+    }
+                                                                             
+\def\upds@ze#1{%                                                                
+     \for\t@mpcntc:=1\to24                                                      
+      \do\g\t@mpdimc=\csname#1\romannumeral\t@mpcntc\endcsname\relax            
+         \g\multiply\t@mpdimc by\s@ze                                           
+         \expandafter\gxdef\csname#1\romannumeral\t@mpcntc\endcsname            
+                            {\the\t@mpdimc}%                                    
+      \od}                                                                      
+                                                                                
+\def\nodes@ze{%                                                                 
+     \begingroup                                                                
+     \unitlength 1pt%                                                           
+     \divide\unitlength by 65536                                                
+     \g\based@st\s@ze pt\g\divide\based@st by 10 % \based@st is 10 % of         
+                                                 % circle diameter
+     \g\dummyhalfcenterdim@n=\s@ze pt\g\divide\dummyhalfcenterdim@n by\tw@      
+     \g\circlew@dth=\s@ze pt%                                                   
+     \g\t@mpcntc\s@ze\g\multiply\t@mpcntc by 65536                              
+     \g\setbox\circleb@x\hbox to0pt{\circle{\t@mpcntc}\hss}%                     
+     \upds@ze{circley@ff}%                                  
+     \g\squarew@dth.9pt\g\multiply\squarew@dth by\s@ze                          
+     \g\setbox\squareb@x\rect@ngle{\squarew@dth}{\squarew@dth}{.4pt}%      
+     \g\dotw@dth=\s@ze pt\g\divide\dotw@dth by 5                                
+     \ifdim\dotw@dth < 1pt\relax                                                
+           \g\dotw@dth1pt\relax                                                 
+        \fi                                                                     
+     \g\t@mpcntc\dotw@dth                                               
+     \g\setbox\dotb@x\hbox to 0pt{\circle*{\t@mpcntc}\hss}%
+     \g\trianglew@dth=\s@ze pt\g\multiply\trianglew@dth by \tw@                 
+     \g\divide\trianglew@dth by 3 
+     \g\textw@dth=0pt%
+     \g\setbox\textb@x\copy\voidb@x
+     \g\framew@dth0pt%
+     \g\setbox\frameb@x\copy\voidb@x
+     \hv@ldef                                                                   
+     \endgroup                                                                  
+     }                                                                          
+                                                                                
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+%%% Changing the style                                                   %%%    
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
+                                                                                
+\def\treefonts#1{#1}                                                            
+\def\vdist#1{\g\vd@st=#1\relax}                                                 
+\def\minsep#1{\g\mins@p=#1\relax\g\halfmins@p=.5\mins@p}                        
+\def\addsep#1{\g\adds@p=#1\relax}                                               
+\def\extended{\def\ext@nded{\g\ext@ndedtrue}}                                   
+\def\noextended{\def\ext@nded{\g\ext@ndedfalse}}                                
+\def\nodesize#1{\g\t@mpdima=#1\relax\g\s@ze=\t@mpdima                           
+     \g\divide\s@ze by 65536\relax} % conversion from dimension to number       
+\def\Treestyle#1{\norm@ff#1\nodes@ze\ignorespaces}                                           
+                                                                                
+\input classes                                                             
+                                                                                
+\Treestyle{%                                                                    
+     \ifLaTeX\treefonts{\normalsize\rm}%                                        
+        \else\treefonts{\tenrm}%                                                
+          \fi                                                                   
+     \vdist{60pt}%                                                              
+     \minsep{20pt}%                                                             
+     \addsep{0pt}%                                                              
+     \nodesize{20pt}%                                                           
+     }                                                                          
+                                                                                
+                                                                                
+%
+
+