blob: 9a23055eda0354ee11abc81b1c929af281d02fab (
plain) (
tree)
|
|
#!/usr/bin/env perl
use strict;
use warnings;
use utf8;
use 5.006;
# Start with an empty tree
my $root = undef;
# Read lines one by one
while ( defined( my $line = <> ) ) {
# Create a new node with this line's value, and empty "left" and "right"
# references
my $new = {
line => $line,
left => undef,
right => undef,
};
# If the tree is empty, this can be our first node; skip the rest of this
# iteration
if ( not defined $root ) {
$root = $new;
next;
}
# Starting at the root ...
my $cur = $root;
# Until we don't have any more nodes for comparison (i.e. we've found the
# place for our new node)...
while ( defined $cur ) {
# Decide whether to add this to the "left" subtree or the "right"
# subtree, depending on whether it's less than the current node or not
my $dir =
$line lt $cur->{line}
? 'left'
: 'right';
# If that reference is undefined, then that's where we'll put this new
# node; unset $cur so the loop stops
if ( not defined $cur->{$dir} ) {
$cur->{$dir} = $new;
$cur = undef;
next;
}
# Otherwise, we resume descent with the next node
$cur = $cur->{$dir};
}
}
# Start a stack of node items to fall back to once we've processed a node, and
# begin at the root
my @stack;
my $cur = $root;
# Keep going as long as there are nodes left in the stack or we have a
# "current" node to print
while ( @stack or defined $cur ) {
# Drill down through the "left" nodes, stacking them up, until we hit NULL
while ( defined $cur ) {
push @stack, $cur;
$cur = $cur->{left};
}
# If there is anything in the stack after doing that, pop off the first
# one, print it, and then move to its "right" node
if (@stack) {
$cur = pop @stack;
print "\t$cur->{line}";
$cur = $cur->{right};
}
}
|