#!/local/bin/perl
#
# Liste chainee pour arbres binaires
#
# arbre.pl
#

$expr="5+9/2-3*2";

%ops = map{$_,1} qw(+ - * /);
%nums = map{$_,1} (0..9);

$tree={};
$orig=$tree;

@input=split(//,$expr);
for (@input) {
    my($temp);
    $tree->{data}=$_;
    $tree->{left}={};
    $tree->{right}={};
    $tree->{left}->{data}="";
    $tree=$tree->{right};
}

$tree=$orig;
while ($tree->{right} != 0) {
    print "$tree->{data}";
    $tree=$tree->{right};
}

print "n";

print "Preorder:nt";
preorder($orig);
print "n";

print "Inorder:nt";
inorder($orig);
print "n";

print "Postorder:nt";
postorder($orig);
print "n";

$spam=lookup($orig,'2');
print "Lookup: $spam :", $spam->{data}, ":n";

exit;

sub lookup {
    my($node,$info)=$_[0];
    print "Node: $node ", $node->{data}, "n";
    return if (!$_[0]);
    return $node if ($node->{data} eq $info);
    my($recur)=lookup($node->{left});
    return if (!$recur);
    return lookup($node->{right});
}

sub preorder {
    my($node)=$_[0];
    print $node->{data};
    preorder($node->{left}) if ($node->{left} != 0);
    preorder($node->{right}) if ($node->{right} != 0);
}

sub inorder {
    my($node)=$_[0];
    inorder($node->{left}) if ($node->{left} != 0);
    print $node->{data};
    inorder($node->{right}) if ($node->{right} != 0);
}

sub postorder {
    my($node)=$_[0];
    postorder($node->{left}) if ($node->{left} != 0);
    postorder($node->{right}) if ($node->{right} != 0);
    print $node->{data};
}