%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Complete binary trees %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The macro \b@nary{} expands to the description of a complete
% binary tree with 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}
%