summaryrefslogtreecommitdiff
path: root/binary-tree.pl
diff options
context:
space:
mode:
Diffstat (limited to 'binary-tree.pl')
-rw-r--r--binary-tree.pl79
1 files changed, 79 insertions, 0 deletions
diff --git a/binary-tree.pl b/binary-tree.pl
new file mode 100644
index 0000000..9a23055
--- /dev/null
+++ b/binary-tree.pl
@@ -0,0 +1,79 @@
+#!/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};
+ }
+}