note
hdb
<p>
For that you require a left/right flag to indicate which side of a subtree you are in. The logic is probably even simpler:
</p>
<code>
use strict;
use warnings;
use constant { LEFT => 0, RIGHT => 1 };
sub prepare {
my( $subtree, $lr, $level, $col, $graph ) = @_;
if( ref($subtree) ) {
my $lcol = prepare( $subtree->[LEFT ], LEFT, $level+1, $col, $graph );
$$col+=2;
my $rcol = prepare( $subtree->[RIGHT], RIGHT, $level+1, $col, $graph );
$graph->[$level]->[$lcol] = '/';
$graph->[$level-1]->[$_] = '_' for $lcol+1..$rcol-1;
$graph->[$level]->[$rcol] = '\\';
return $lr == LEFT ? $rcol : $lcol; # intentionally the other way round !!
} else {
$graph->[$level]->[$$col] = $subtree;
return $$col;
}
}
my $root = do {
my $r;
my @a = ( 'a'..'z', 1..9, 'A'..'Z' );
$r = int( rand $#a ), splice @a, $r, 2, [ @a[ $r, $r+1 ]] while @a > 1;
$a[0];
};
my @graph;
my $col = 0;
prepare( $root, LEFT, 1, \$col, \@graph ); # need to start with $level = 1 !
for my $row ( @graph ) {
print $_ // ' ' for @$row;
print "\n";
}
</code>
<p>and it looks like this:</p>
<c>
_____________
_____________/ \_________________
_____/ \_________ _/ \___________________________
_____________/ \_______ _/ \ / \ _____________/ \_________
_________/ \ _/ \_ / \___ 4 5 6 _/ \_______ ___/ \_
_/ \_____ o _/ \_ _/ \ x / \_ / \_ ___/ \_ _/ \_ _/ \
_/ \_ ___/ \_ / \ / \_ / \ w y _/ \_ 7 / \_ ___/ \___ / \_ / \ _/ \_ / \ Z
/ \ / \ _/ \_ _/ \_ p q r / \ u v / \ / \ 8 / \ / \_ / \_ J / \___ Q R / \ / \_ X Y
a b c d / \_ / \ / \ / \_ s t z 1 2 3 9 A B _/ \ F _/ \ K / \_ S T U / \
e / \ h i j k l / \ / \ E / \ I L _/ \_ V W
f g m n C D G H / \ / \
M N O P
</c>
<p>UPDATE:</p>
<p>Replacing the 2 in line <c>$$col+=2;</c> with a larger number makes the tree wider which might be useful for readability.</p>
<p>Replacing the line <c>$graph->[$level]->[$$col] = $subtree;</c> with <c>$graph->[$level++]->[$$col] = $_ for split //, $subtree;</c> will print leaf values vertically.</p>
998803
1055154