\$BOXWID = .30; \$BOXHT = .25; \$HSPACE = .2; \$VSPACE = -.5; \$ARROW = ''; # set to '->' to get arrows on verticals. sub make_tree { my (\$base, \$degree, \$x, \$y, \$labels) = @_; my \$ind = ' ' x (4- \$degree); (\$x, \$y) = (0,0) unless defined \$x; print STDERR "\${ind}make_tree(\$base, \$degree) at (\$x, \$y)\n"; # emit pic code for box with base number # call make_tree recursively for child trees # accumulate width of subtrees to compute total height and width # draw horizontal line # draw vertical line(s) # return total height and width my (\$xs, \$ys) = (0, \$VSPACE); my \$label = \$labels->[\$base] ; \$label = \$base unless defined \$label; print qq{N\$base: box "\$label" at (\$x, \$y)\n}; # \$base = 2<<\$degree if \$base == 0; # Fake this print STDERR "\$ind loop is ", \$degree-1, ".. 0\n"; for my \$bitpos (reverse (0 .. \$degree-1)) { my \$bit = 1 << \$bitpos; print STDERR "\$ind bit is \$bit\n"; next if \$base & \$bit; my \$subnode = \$base | \$bit; my (\$w, \$h) = make_tree(\$subnode, \$bitpos, \$x+\$xs, \$y+\$ys, \$labels); if (\$bitpos == \$degree - 1) { # vertical line directly from node print qq{L\$base: line from N\$base.s to N\$subnode.n \$arrow\n}; print qq{P\$base: 1/2 of the way between L\$base.start and L\$base.end\n}; } else { # vertical line from right part of horizontal line my \$xx = \$x + \$xs; my \$yy = \$y + \$VSPACE/2; print qq{line from (\$xx, P\$base.y) to N\$subnode.n \$arrow\n}; } \$xs += \$w+\$HSPACE; # \$ys += \$h; } # Horizontal line if (\$degree > 1) { print qq{line from P\$base right \$xs-\$HSPACE\n} ; } return (\$xs, \$ys); } print ".PS\n"; print "boxwid := \$BOXWID; boxht := \$BOXHT\n"; print "linethick=1;\n"; my \$depth = shift; make_tree(0, \$depth, 0, 0, \@ARGV); print ".PE\n"; sub position { my (\$n, \$d) = @_; my (\$x, \$y); return (0,0) if \$n == 0; for my \$b (0 .. \$d-1) { my \$bv = \$n & 1; \$y += \$bv; if (\$saw1 && \$bv == 0) { \$x += 1<<(\$b-1); } \$saw1 ||= \$bv; \$n >>= 1; } (\$x, \$y); }