Debian Codegraph @

texmf-dist/tex/plain/treetex/classes.tex

raw
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