Tree::Binary 0.07

Tree::Binary is a Object Oriented Binary Tree for Perl.

SYNOPSIS

use Tree::Binary;

# a tree representaion of the expression:
# ((2 + 2) * (4 + 5))
my $btree = Tree::Binary->new("*")
->setLeft(
Tree::Binary->new("+")
->setLeft(Tree::Binary->new("2"))
->setRight(Tree::Binary->new("2"))
)
->setRight(
Tree::Binary->new("+")
->setLeft(Tree::Binary->new("4"))
->setRight(Tree::Binary->new("5"))
);
# Or shown visually:
# +---(*)---+
# | |
# +-(+)-+ +-(+)-+
# | | | |
# (2) (2) (4) (5)

# get a InOrder visitor
my $visitor = Tree::Binary::Visitor::InOrderTraversal->new();
$btree->accept($visitor);

# print the expression in infix order
print $visitor->getAccumulation(); # prints "2 + 2 * 4 + 5"

# get a PreOrder visitor
my $visitor = Tree::Binary::Visitor::PreOrderTraversal->new();
$btree->accept($visitor);

# print the expression in prefix order
print $visitor->getAccumulation(); # prints "* + 2 2 + 4 5"

# get a PostOrder visitor
my $visitor = Tree::Binary::Visitor::PostOrderTraversal->new();
$btree->accept($visitor);

# print the expression in postfix order
print $visitor->getAccumulation(); # prints "2 2 + 4 5 + *"

# get a Breadth First visitor
my $visitor = Tree::Binary::Visitor::BreadthFirstTraversal->new();
$btree->accept($visitor);

# print the expression in breadth first order
print $visitor->getAccumulation(); # prints "* + + 2 2 4 5"

# be sure to clean up all circular references
$btree->DESTROY();

This module is a fully object oriented implementation of a binary tree. Binary trees are a specialized type of tree which has only two possible branches, a left branch and a right branch. While it is possible to use an n-ary tree, like Tree::Simple, to fill most of your binary tree needs, a true binary tree object is just easier to mantain and use.

Binary Tree objects are especially useful (to me anyway) when building parse trees of things like mathematical or boolean expressions. They can also be used in games for such things as descisions trees. Binary trees are a well studied data structure and there is a wealth of information on the web about them.

This module uses exceptions and a minimal Design By Contract style. All method arguments are required unless specified in the documentation, if a required argument is not defined an exception will usually be thrown. Many arguments are also required to be of a specific type, for instance the $tree argument to both the setLeft and setRight methods, must be a Tree::Binary object or an object derived from Tree::Binary, otherwise an exception is thrown. This may seems harsh to some, but this allows me to have the confidence that my code works as I intend, and for you to enjoy the same level of confidence when using this module. Note however that this module does not use any Exception or Error module, the exceptions are just strings thrown with die.

This object uses a number of methods copied from another module of mine, Tree::Simple. Users of that module will find many similar methods and behaviors. However, it did not make sense for Tree::Binary to be derived from Tree::Simple, as there are a number of methods in Tree::Simple that just wouldnt make sense in Tree::Binary. So, while I normally do not approve of cut-and-paste code reuse, it was what made the most sense in this case.