Created
February 4, 2010 13:45
-
-
Save masak/294621 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use v6; | |
role Found { has Int $.found is rw } | |
enum Traversal <pre-order in-order post-order>; | |
my %root; | |
for ^20 { | |
insert(%root, (0..^1000).pick); | |
} | |
say 'Pre order: ', (gather { show(%root, pre-order) }).perl; | |
say 'In order: ', (gather { show(%root, in-order) }).perl; | |
say 'Post order: ', (gather { show(%root, post-order) }).perl; | |
while defined (my $sought = prompt('Search? ')) { | |
if search(%root, $sought) -> $node { | |
say "Found $sought at node #{$node.WHICH}: {$node<VALUE>}"; | |
if $node<VALUE>.found > 1 { | |
say '(again!)'; | |
} | |
} | |
else { | |
say "No $sought in tree"; | |
} | |
} | |
exit; | |
sub insert(%tree is rw, Int $val) { | |
unless %tree { | |
%tree = | |
LEFT => {}, | |
RIGHT => {}, | |
VALUE => $val but Found(0), | |
; | |
return; | |
} | |
given %tree<VALUE> { | |
when * > $val { insert(%tree<LEFT>, $val) } | |
when * < $val { insert(%tree<RIGHT>, $val) } | |
default { warn "dup insert of $val" } | |
} | |
} | |
sub show(%tree, Traversal $method) { | |
return unless %tree; | |
given $method { | |
when pre-order { | |
show(%tree<RIGHT>, $method); | |
show(%tree<LEFT>, $method); | |
take %tree<VALUE>; | |
} | |
when in-order { | |
show(%tree<RIGHT>, $method); | |
take %tree<VALUE>; | |
show(%tree<LEFT>, $method); | |
} | |
when post-order { | |
take %tree<VALUE>; | |
show(%tree<RIGHT>, $method); | |
show(%tree<LEFT>, $method); | |
} | |
} | |
} | |
sub search(%tree is rw, $sought) { | |
return unless %tree; | |
if %tree<VALUE> == $sought { | |
%tree<VALUE>.found++; | |
return %tree; | |
} | |
return search(%tree<LEFT>, $sought) if $sought < %tree<VALUE>; | |
return search(%tree<RIGHT>, $sought); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment