BinarySearchTree.pm (1722B) - raw
1 package BinarySearchTree; 2 use strict; 3 use warnings; 4 use Exporter qw<import>; 5 our @EXPORT_OK = qw<tree treeSort>; 6 7 # 8 # implementation of binary search tree 9 # as demonstrated in "Perl Cookbook" by Tom Christiansen and Nathan Torkington 10 # https://www.oreilly.com/library/view/perl-cookbook/1565922433/ 11 # 12 13 sub create_new_node { 14 my $value = shift; 15 # create anonymous array to represent the new node 16 my $tree = {}; 17 $tree->{data} = $value; 18 $tree->{left} = undef; 19 $tree->{right} = undef; 20 return $tree; 21 } 22 23 sub insert { 24 my ( $tree, $value ) = @_; 25 26 # if node we want to insert (at any location in the tree) does not exist, 27 # create it and return a reference to the anonymous array containing it 28 # by updating the value that was passed to the subroutine ($tree) 29 unless ( $tree ) { 30 $_[0] = create_new_node ( $value ); 31 return; # need to return since we just created a new node 32 } 33 34 # recursively find where to place new node in the tree 35 if ( $tree->{data} < $value ) { insert ( $tree->{right}, $value ) } 36 else { insert ( $tree->{left}, $value ) } 37 } 38 39 sub tree { 40 my ($data) = @_; 41 my $tree; 42 insert ( $tree, $_ ) foreach ( @{ $data } ); 43 return $tree; 44 } 45 46 # recurse on left subtree, obtain root, recurse on right tree 47 # until we get to empty node 48 sub in_order { 49 my($tree) = @_; 50 return () unless $tree; 51 return ( 52 in_order($tree->{left}), 53 $tree->{data}, 54 in_order($tree->{right}) 55 ); 56 } 57 58 # You are expected to create a tree and then do an in-order walk. 59 # Using the sort() function is cheating! 60 sub treeSort { 61 my ($data) = @_; 62 return [in_order( tree ( $data ) )]; 63 } 64 65 1;