use strict;
use warnings;

my($root, $n);

# zuerst 20 zufaellige Knoten erzeugen
for $n (0..19) 
  { insert($root, int(rand(1000))); }

# now dump out the tree all three ways
print "Pre order:  ";  pre_order($root);  print "\n";
print "In order:   ";  in_order($root);   print "\n";
print "Post order: ";  post_order($root); print "\n";

# prompt until EOF
print "Suchen nach: ";
while (<STDIN>) 
  { 
  chomp;
  my $found = search($root, $_);
  if ($found) { print "$_ gefunden in $found, Wert: $found->{VALUE}\n"; }
  else        { print "$_ ist nicht im Baum\n"; }
  print "Suchen nach: ";
  }

sub insert 
  {
  my($tree, $value) = @_;
  unless ($tree) 
    {
    # neuen Knoten erzeugen
    $tree = {};
    $tree->{VALUE} = $value;
    $tree->{LEFT}  = undef;
    $tree->{RIGHT} = undef;
    # $_[0] is Referenzparameter!
    $_[0] = $tree;              
    return;
    }
  if    ($tree->{VALUE} > $value) { insert($tree->{LEFT},  $value); }
  elsif ($tree->{VALUE} < $value) { insert($tree->{RIGHT}, $value); }
  else                            { warn "Doppelter Wert: $value\n"; }
  }

sub in_order 
  {
  my($tree) = @_;
  return unless $tree;
  in_order($tree->{LEFT});
  print $tree->{VALUE}, " ";
  in_order($tree->{RIGHT});
  }

sub pre_order 
  {
  my($tree) = @_;
  return unless $tree;
  print $tree->{VALUE}, " ";
  pre_order($tree->{LEFT});
  pre_order($tree->{RIGHT});
  }

sub post_order 
  {
  my($tree) = @_;
  return unless $tree;
  post_order($tree->{LEFT});
  post_order($tree->{RIGHT});
  print $tree->{VALUE}, " ";
  }

sub search 
  {
  my($tree, $value) = @_;
  return unless $tree;
  if ($tree->{VALUE} == $value) 
    { return $tree; }
  elsif ($tree->{VALUE} > $value) { search($tree->{LEFT},  $value); }
  elsif ($tree->{VALUE} < $value) { search($tree->{RIGHT}, $value); }
  }