perl 二叉树数据结构

[perl]代码库

#-----------------------------
#!/usr/bin/perl -w
# bintree - binary tree demo program
use strict;
my ( $root, $n );

# first generate 20 random inserts
while ( $n++ < 20 ) { 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
for ( print "Search? "; <>; print "Search? " )
{
	chomp;
	my $found = search ( $root, $_ );
	if ( $found ) { print "Found $_ at $found, $found->{VALUE}\n" }
	else        { print "No $_ in tree\n" }
}

exit;

#########################################

# insert given value into proper point of
# provided tree.  If no tree provided,
# use implicit pass by reference aspect of @_
# to fill one in for our caller.
sub insert
{
	my ( $tree, $value ) = @_;
	unless ( $tree )
	{
		$tree = {};
# allocate new node
		$tree-> {VALUE}  = $value;
		$tree-> {LEFT}   = undef;
		$tree-> {RIGHT}  = undef;
		$_[0] = $tree;
# $_[0] is reference param!
		return;
	}
	if    ( $tree->{VALUE} > $value ) { insert ( $tree-> {LEFT},  $value ) }
	elsif ( $tree->{VALUE} < $value ) { insert ( $tree-> {RIGHT}, $value ) }
	else                            { warn "dup insert of $value\n"  }
# XXX: no dups
}

# recurse on left child,
# then show current value,
# then recurse on right child.
sub in_order
{
	my ( $tree ) = @_;
	return unless $tree;
	in_order ( $tree->{LEFT} );
	print $tree->{VALUE}, " ";
	in_order ( $tree->{RIGHT} );
}

# show current value,
# then recurse on left child,
# then recurse on right child.
sub pre_order
{
	my ( $tree ) = @_;
	return unless $tree;
	print $tree->{VALUE}, " ";
	pre_order ( $tree->{LEFT} );
	pre_order ( $tree->{RIGHT} );
}

# recurse on left child,
# then recurse on right child,
# then show current value.
sub post_order
{
	my ( $tree ) = @_;
	return unless $tree;
	post_order ( $tree->{LEFT} );
	post_order ( $tree->{RIGHT} );
	print $tree->{VALUE}, " ";
}

# find out whether provided value is in the tree.
# if so, return the node at which the value was found.
# cut down search time by only looking in the correct
# branch, based on current value.
sub search
{
	my ( $tree, $value ) = @_;
	return unless $tree;
	if ( $tree->{VALUE} == $value )
	{
		return $tree;
	}
	search ( $tree->{ ( $value < $tree->{VALUE} ) ? "LEFT" : "RIGHT"}, $value )
}

#-----------------------------