%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 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}
