1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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};
}
}
|