| 1 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 2 |
%%% Complete binary trees %%% |
| 3 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 4 |
|
| 5 |
% The macro \b@nary{<number>} expands to the description of a complete |
| 6 |
% binary tree with <number> many internal nodes, where each level is filled with |
| 7 |
% the maximal number of internal nodes, and the last level of internal nodes |
| 8 |
% is filled from left to right. |
| 9 |
|
| 10 |
\newcount\b@nno % number of nodes |
| 11 |
\newcount\b@nlv % number of complete levels |
| 12 |
\newcount\b@ndl % number of nodes on incomplete level |
| 13 |
|
| 14 |
\def\ld(#1,#2,#3){% #1, #2, and #3 must be counter registers. |
| 15 |
% #1 is the input, #1 must be >= 1. |
| 16 |
% \ld makes the following assignments: |
| 17 |
% #2:=|_log_2(#1)_|, #3:=2^#2. |
| 18 |
% The contents of #1 is destroyed during the computation. |
| 19 |
#2=0 #3=1 |
| 20 |
\loop\ifnum #1>\@ne\relax |
| 21 |
\divide #1 by\tw@ % this is integer division |
| 22 |
\advance #2 by\@ne |
| 23 |
\multiply #3 by\tw@ |
| 24 |
\repeat} |
| 25 |
|
| 26 |
\def\b@nary#1{% draws a complete binary tree with #1 internal nodes, |
| 27 |
% a complete binary tree with N internal nodes has |
| 28 |
% lv:=|_log_2(N+1)_| many |
| 29 |
% complete level of binary nodes and dl:=N-2^{lv}+1 many internal |
| 30 |
% nodes on an incomplete level. |
| 31 |
\b@nno=#1\relax\advance\b@nno by \@ne |
| 32 |
\ld(\b@nno,\b@nlv,\b@ndl)% |
| 33 |
\b@ndl=-\b@ndl\advance\b@ndl by #1\advance\b@ndl by\@ne |
| 34 |
\b@n} |
| 35 |
|
| 36 |
\def\b@n{% |
| 37 |
\ifnum\b@nlv>\@ne |
| 38 |
\advance\b@nlv by-\@ne |
| 39 |
\b@n |
| 40 |
\b@n |
| 41 |
\advance\b@nlv by\@ne |
| 42 |
\node{} |
| 43 |
\else\ifnum\b@ndl>\@ne |
| 44 |
\advance\b@ndl by-\tw@ |
| 45 |
\node{\le@f\external}\node{\le@f\external}\node{}% |
| 46 |
\node{\le@f\external}\node{\le@f\external}\node{}% |
| 47 |
\node{}% |
| 48 |
\else\ifnum\b@ndl=\@ne |
| 49 |
\advance\b@ndl by-\@ne |
| 50 |
\node{\le@f\external}\node{\le@f\external}\node{}% |
| 51 |
\node{\le@f\external}% |
| 52 |
\node{}% |
| 53 |
\else\node{\le@f\external}\node{\le@f\external}\node{}% |
| 54 |
\fi |
| 55 |
\fi |
| 56 |
\fi} |
| 57 |
|
| 58 |
\def\circleleaves{\def\le@f{\type{circle}}} |
| 59 |
\def\squareleaves{\def\le@f{\type{square}}} |
| 60 |
|
| 61 |
\newcount\no@ |
| 62 |
\def\no#1{\no@=#1\relax} |
| 63 |
|
| 64 |
\def\binary#1{% |
| 65 |
\no{1}\circleleaves |
| 66 |
#1% |
| 67 |
\b@nary{\no@}} |
| 68 |
|
| 69 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 70 |
%%% Fibonacci trees %%% |
| 71 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 72 |
|
| 73 |
% \f@b expands to the description of a Fibonacci tree |
| 74 |
% of height \f@bht. |
| 75 |
|
| 76 |
\newcount\f@bht |
| 77 |
|
| 78 |
\def\f@b{% draws a Fibonacci tree of depth #1 |
| 79 |
\ifnum\f@bht>1 |
| 80 |
\advance\f@bht by-\@ne\f@b\advance\f@bht by\@ne |
| 81 |
\advance\f@bht by-\tw@\f@b\advance\f@bht by\tw@ |
| 82 |
\ifunn@des\node{\unary} |
| 83 |
\fi |
| 84 |
\node{\lefttop} |
| 85 |
\else\ifnum\f@bht=1 |
| 86 |
\node{\external\le@f} |
| 87 |
\node{\external\le@f} |
| 88 |
\node{} |
| 89 |
\else\node{\external\le@f} |
| 90 |
\fi |
| 91 |
\fi} |
| 92 |
|
| 93 |
\newif\ifunn@des |
| 94 |
|
| 95 |
\let\unarynodes\unn@destrue |
| 96 |
\def\hght#1{\f@bht=#1\relax} |
| 97 |
|
| 98 |
\def\fibonacci#1{% |
| 99 |
\hght{0}\unn@desfalse\circleleaves |
| 100 |
#1% |
| 101 |
\f@b} |
| 102 |
|
| 103 |
|
| 104 |
% |
| 105 |
|