Rechercher une page de manuel
Tree::Binary.3pm
Langue: en
Version: 2010-02-10 (ubuntu - 24/10/10)
Section: 3 (Bibliothèques de fonctions)
NAME
Tree::Binary - An implementation of a binary treeSYNOPSIS
my $tree = Tree::Binary->new( 'root' ); my $left = Tree::Binary->new( 'left' ); $tree->left( $left ); my $right = Tree::Binary->new( 'left' ); $tree->right( $right ); my $right_child = $tree->right; $tree->right( undef ); # Unset the right child. my @nodes = $tree->traverse( $tree->POST_ORDER ); my $traversal = $tree->traverse( $tree->IN_ORDER ); while ( my $node = $traversal->() ) { # Do something with $node here }
DESCRIPTION
This is an implementation of a binary tree. This class inherits from Tree, which is an N-ary tree implemenation. Because of this, this class actually provides an implementation of a complete binary tree vs. a sparse binary tree. The empty nodes are instances of Tree::Null, which is described in Tree. This should have no effect on your usage of this class.METHODS
In addition to the methods provided by Tree, the following items are provided or overriden.- •
- "left([$child])" / "right([$child])"
These access the left and right children, respectively. They are mutators, which means that their behavior changes depending on if you pass in a value.
If you do not pass in any parameters, then it will act as a getter for the specific child, return the child (if set) or undef (if not).
If you pass in a child, it will act as a setter for the specific child, setting the child to the passed-in value and returning the $tree. (Thus, this method chains.)
If you wish to unset the child, do "$tree>left( undef );"
- •
- "children()"
This will return the children of the tree.
NOTE: There will be two children, always. Tree::Binary implements a complete binary tree, filling in missing children with Tree::Null objects. (Please see Tree::Fast for more information on Tree::Null.)
- •
- traverse( [$order] )
When called in list context ("my @traversal = $tree->traverse()"), this will return a list of the nodes in the given traversal order. When called in scalar context ("my $traversal = $tree->traverse()"), this will return a closure that will, over successive calls, iterate over the nodes in the given traversal order. When finished it will return false.
The default traversal order is pre-order.
In addition to the traversal orders provided by Tree, Tree::Binary provides in-order traversals.
-
- •
- In-order
This will return the result of an in-order traversal on the left node (if any), then the node, then the result of an in-order traversal on the right node (if any).
-
NOTE: You have access to all the methods provided by Tree, but it is not recommended that you use many of them, unless you know what you're doing. This list includes "add_child()" and "remove_child()".
TODO
- •
- Make in-order closure traversal work iteratively
- •
- Make post-order closure traversal work iteratively
CODE COVERAGE
Please see the relevant sections of Tree.SUPPORT
Please see the relevant sections of Tree.AUTHORS
Rob Kinyon <rob.kinyon@iinteractive.com>Stevan Little <stevan.little@iinteractive.com>
Thanks to Infinity Interactive for generously donating our time.
COPYRIGHT AND LICENSE
Copyright 2004, 2005 by Infinity Interactive, Inc.<http://www.iinteractive.com>
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
Contenus ©2006-2024 Benjamin Poulain
Design ©2006-2024 Maxime Vantorre