Er, i hate to say this but i dont think thats a great idea unless you have seriously good reasons.

The way to do this is to make sure the reference that is blessed is not part of the cyclic structure. Consider the following code:

use strict;
use warnings;

sub MyBinTree::insert {
  my ($self,$string,$node)=@_;

  my $ins_ref;
  unless ($node) {
    unless ($self->{root}) {
      $ins_ref=\$self->{root}
    } else {
      $node=$self->{root};
    }
  }
  unless ($ins_ref) {
    if ($string lt $node->{val}) {
      if ($node->{left}) {
        return $self->insert($string,$node->{left})
      } else {
        $ins_ref=\$node->{left};
      }
    } elsif ($string gt $node->{val}) {
      if ($node->{right}) {
        return $self->insert($string,$node->{right})
      } else {
        $ins_ref=\$node->{right};
      }
    } else {
      return $node;
    }
  }
  $$ins_ref={val=>$string,parent=>$node};
  return $$ins_ref
}

sub MyBinTree::new {
  my ($class)=@_;
  my $self= bless { },$class;
  print "Created new $self\n";
  return $self;
}

sub MyBinTree::_traverse {
  my ($self,$node,$sub)=@_;

  if ($node->{left}) {
    $self->_traverse($node->{left},$sub);
  }
  {
    local $_=$node;
    $sub->();
  }
  if ($node->{right}) {
    $self->_traverse($node->{right},$sub);
  }
}

sub MyBinTree::traverse {
  my ($self,$sub)=@_;

  $self->_traverse($self->{root},$sub)
    if $self->{root};
}

sub MyBinTree::DESTROY {
  my $self=shift;
  print "Destroying new $self\n";
  $self->traverse(sub { delete $_->{parent} });
  print "Destroyed\n";
}

{
  my $container=MyBinTree->new();
  $container->insert($_) for (my @words=qw(foo bar baz bop fop cool));
  $container->traverse(sub { print $_->{val},"\n" });
  print "Exiting scope.\n";
}
[download]

Which outputs:

Created new MyBinTree=HASH(0x1acef24)
bar
baz
bop
cool
foo
fop
Exiting scope.
Destroying new MyBinTree=HASH(0x1acef24)
Destroyed
[download]

The internal data structure is entirely self referential and cyclic. Yet it destroys just fine, and with no weakref.