#!/local/bin/perl
#
# Linked list binary tree implementation
#
# File: tree.pl
#
# Author: Nem W Schlecht
# Last Modification: $Date$
#
# $Id$
# $Log$
#

$expr="5+9-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:\n\t";
preorder($orig);
print "\n";

print "Inorder:\n\t";
inorder($orig);
print "\n";

print "Postorder:\n\t";
postorder($orig);
print "\n";

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

exit;

sub lookup {
    my($node,$info)=$_[0];
    print "Node: $node\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};
}