binarysearchtree.pm

PERL语言资料 可以用于PERL程序设计

# Fig. 20.11: BinarySearchTree.pm
# Implementation of a binary search tree.

use warnings;
use strict;

package TreeNode;
my $class;

# TreeNode constructor
sub new 
{
   my $type = shift();
   $class = ref( $type ) || $type;
   my $self = 
      { left => undef, data => shift(), right => undef };

   bless( $self, $class );
   return $self;
}

# insert a TreeNode in a tree that contains nodes;
# ignore duplicate values
sub insert 
{
   my ( $self, $data ) = @_;

   if ( $data < $self->{ data } ) {
      if ( defined( $self->{ left } ) ) {
         $self->{ left }->insert( $data );
      }
      else {
         $self->{ left } = new TreeNode( $data );
      }
   }
   elsif ( $data > $self->{ data } ) {
      if ( defined( $self->{ right } ) ) {
         $self->{ right }->insert( $data );
      }
      else {
         $self->{ right } = new TreeNode( $data );
      }
   }
}

# performs a preorder traversal of a binary search tree
sub preOrder 
{
   my $self = shift();

   print( "$self->{ data } " );

   $self->{ left }->preOrder() 
      if ( defined( $self->{ left } ) );
   
   $self->{ right }->preOrder() 
      if ( defined( $self->{ right } ) );
}

# performs an inorder traversal of a binary search tree
sub inOrder 
{
   my $self = shift();

   $self->{ left }->inOrder() 
      if ( defined( $self->{ left } ) );
   
   print( "$self->{ data } " );
   
   $self->{ right }->inOrder() 
      if ( defined( $self->{ right } ) );
}

# performs a postorder traversal of a binary search tree
sub postOrder 
{
   my $self = shift();

   $self->{ left }->postOrder() 
      if ( defined( $self->{ left } ) );

   $self->{ right }->postOrder() 
      if ( defined( $self->{ right } ) );

   print( "$self->{ data } " );
}

# recursively outputs the binary tree in a tree format turned
# on its side with the root node at the left of the output, the
# rightmost child at the top of the output and the leftmost 
# child at the bottom of the output
sub outputTree 
{
   my ( $self, $depth ) = @_;
   
   if ( defined( $self->{ right } ) ) {
      $self->{ right }->outputTree( $depth + 3 );
   }

   print( ' ' x $depth, "$self->{ data }\n" );

   if ( defined( $self->{ left } ) ) {
      $self->{ left }->outputTree( $depth + 3 );
   }
}

package BinarySearchTree;

# BinarySearchTree constructor
sub new 
{
   my $type = shift();
   my $class = ref( $type ) || $type;
   
   my $self = { root => undef };
   bless( $self, $class );
   return $self;
}

# inserts a node in a binary search tree
sub insertNode 
{
   my ( $self, $data ) = @_;

   unless ( defined( $self->{ root } ) ) {
      $self->{ root } = new TreeNode( $data );
   }
   else {
      $self->{ root }->insert( $data );
   }
}

# begins the preorder traversal
sub printPreOrder 
{
   my ( $self, $node ) = @_;
   $self->{ root }->preOrder();
}

# begins the inorder traversal
sub printInOrder 
{
   my ( $self, $node ) = @_;
   $self->{ root }->inOrder();
}

# begins the postorder traversal
sub printPostOrder 
{
   my ( $self ) = shift();
   $self->{ root }->postOrder();
}

# begin output of tree in tree format
sub printTree 
{
   my ( $self ) = shift();
   $self->{ root }->outputTree( 0 );
}      
      
return 1;

###########################################################################
#  (C) Copyright 2001 by Deitel & Associates, Inc. and Prentice Hall.     #
#  All Rights Reserved.                                                   #
#                                                                         #
#  DISCLAIMER: The authors and publisher of this book have used their     #
#  best efforts in preparing the book. These efforts include the          #
#  development, research, and testing of the theories and programs        #
#  to determine their effectiveness. The authors and publisher make       #
#  no warranty of any kind, expressed or implied, with regard to these    #
#  programs or to the documentation contained in these books. The authors #
#  and publisher shall not be liable in any event for incidental or       #
#  consequential damages in connection with, or arising out of, the       #
#  furnishing, performance, or use of these programs.                     #
###########################################################################