Tree::Nary - Perl implementation of N-ary search trees. |

- NAME
- SYNOPSIS
- DESCRIPTION
- GLOBAL VARIABLES
- METHODS
- new( [DATA] )
- insert( PARENT, POSITION, NODE )
- insert_before( PARENT, SIBLING, NODE )
- append( PARENT, NODE )
- prepend( PARENT, NODE )
- insert_data( PARENT, POSITION, DATA )
- insert_data_before( PARENT, SIBLING, DATA )
- append_data( PARENT, DATA )
- prepend_data( PARENT, DATA )
- reverse_children( NODE )
- traverse( NODE, ORDER, FLAGS, MAXDEPTH, FUNCTION, DATA )
- children_foreach( NODE, FLAGS, FUNCTION, DATA )
- get_root( NODE )
- find( NODE, ORDER, FLAGS, DATA )
- find_child( NODE, FLAGS, DATA )
- child_index( NODE, DATA )
- child_position( NODE, CHILD )
- first_child( NODE )
- last_child( NODE )
- nth_child( NODE, INDEX )
- first_sibling( NODE )
- prev_sibling( NODE )
- next_sibling( NODE )
- last_sibling( NODE )
- is_leaf( NODE )
- is_root( NODE )
- depth( NODE )
- n_nodes( NODE, FLAGS )
- n_children( NODE )
- is_ancestor( NODE, DESCENDANT )
- max_height( NODE )
- unlink( NODE )
- EXAMPLES
- AUTHOR
- COPYRIGHT
- SEE ALSO

Tree::Nary - Perl implementation of N-ary search trees.

use Tree::Nary;

$node = new Tree::Nary;

$inserted_node = $node->insert($parent, $position, $node); $inserted_node = $node->insert_before($parent, $sibling, $node); $inserted_node = $node->append($parent, $node); $inserted_node = $node->prepend($parent, $node); $inserted_node = $node->insert_data($parent, $position, $data); $inserted_node = $node->insert_data_before($parent, $sibling, $data); $inserted_node = $node->append_data($parent, $data); $inserted_node = $node->prepend_data($parent, $data);

$node->reverse_children($node);

$node->traverse($node, $order, $flags, $maxdepth, $funcref, $argref);

$node->children_foreach($node, $flags, $funcref, $argref);

$root_node = $obj->get_root($node);

$found_node = $node->find($node, $order, $flags, $data); $found_child_node = $node->find_child($node, $flags, $data);

$index = $node->child_index($node, $data); $position = $node->child_position($node, $child);

$first_child_node = $node->first_child($node); $last_child_node = $node->last_child($node);

$nth_child_node = $node->nth_child($node, $index);

$first_sibling = $node->first_sibling($node); $next_sibling = $node->next_sibling($node); $prev_sibling = $node->prev_sibling($node); $last_sibling = $node->last_sibling($node);

$bool = $node->is_leaf($node); $bool = $node->is_root($node);

$cnt = $node->depth($node);

$cnt = $node->n_nodes($node); $cnt = $node->n_children($node);

$bool = $node->is_ancestor($node);

$cnt = $obj->max_height($node);

$node->unlink($node);

The **Tree::Nary** class implements N-ary trees (trees of data with any
number of branches), providing the organizational structure for a tree (collection)
of any number of nodes, but knowing nothing about the specific type of node used.
It can be used to display hierarchical database entries in an internal application (the
NIS netgroup file is an example of such a database). It offers the capability to select
nodes on the tree, and attachment points for nodes on the tree. Each attachment point
can support multiple child nodes.

The data field contains the actual data of the node. The next and previous fields point
to the node's siblings (a sibling is another node with the same parent). The parent
field points to the parent of the node, or is *undef* if the node is the root of the
tree. The children field points to the first child of the node. The other children are
accessed by using the next pointer of each child.

This module is a translation (albeit not a direct one) from the C implementation of
N-ary trees, available in the **GLIB distribution** (see SEE ALSO).

**TRUE**

**FALSE**

Specifies which nodes are visited during several of the tree functions, including
`traverse()`

and find().

**TRAVERSE_LEAFS**

- Specifies that only leaf nodes should be visited.
**TRAVERSE_NON_LEAFS**

- Specifies that only non-leaf nodes should be visited.
**TRAVERSE_ALL**

- Specifies that all nodes should be visited.
**TRAVERSE_MASK**

- Combination of multiple traverse flags.

Specifies the type of traversal performed by `traverse()`

and find().

**PRE_ORDER**

- Visits a node, then its children.
**IN_ORDER**

- Visits a node's left child first, then the node itself, then its right child. This is the one to use if you want the output sorted according to the compare function.
**POST_ORDER**

- Visits the node's children, then the node itself.
**LEVEL_ORDER**

- Calls the function for each child of the node, then recursively visits each child.

Creates a new Tree::Nary object. Used to create the first node in a tree. Insert optional DATA into new created node.

Inserts a NODE beneath the PARENT at the given POSITION, returning inserted NODE. If POSITION is -1, NODE is inserted as the last child of PARENT.

Inserts a NODE beneath the PARENT before the given SIBLING, returning
inserted NODE. If SIBLING is *undef*, the NODE is inserted as the last child
of PARENT.

Inserts a NODE as the last child of the given PARENT, returning inserted NODE.

Inserts a NODE as the first child of the given PARENT, returning inserted NODE.

Inserts a **new** node containing DATA, beneath the PARENT at the given POSITION.
Returns the new inserted node.

Inserts a **new** node containing DATA, beneath the PARENT, before the given
SIBLING. Returns the new inserted node.

Inserts a **new** node containing DATA as the last child of the given PARENT.
Returns the new inserted node.

Inserts a **new** node containing DATA as the first child of the given PARENT.
Returns the new inserted node.

Reverses the order of the children of NODE. It doesn't change the order of the grandchildren.

Traverses a tree starting at the given root NODE. It calls the given FUNCTION (with optional user DATA to pass to the FUNCTION) for each node visited.

The traversal can be halted at any point by returning TRUE from FUNCTION.

The ORDER in which nodes are visited is one of IN_ORDER, PRE_ORDER, POST_ORDER and LEVEL_ORDER.

FLAGS specifies which types of children are to be visited, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.

MAXDEPTH is the maximum depth of the traversal. Nodes below this depth will not be visited. If MAXDEPTH is -1, all nodes in the tree are visited. If MAXDEPTH is 1, only the root is visited. If MAXDEPTH is 2, the root and its children are visited. And so on.

Calls a FUNCTION (with optional user DATA to pass to the FUNCTION) for each of the children of a NODE. Note that it doesn't descend beneath the child nodes. FLAGS specifies which types of children are to be visited, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.

Gets the root node of a tree, starting from NODE.

Finds a NODE in a tree with the given DATA.

The ORDER in which nodes are visited is one of IN_ORDER, PRE_ORDER, POST_ORDER and LEVEL_ORDER.

FLAGS specifies which types of children are to be searched, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.

Returns the found node, or *undef* if the DATA is not found.

Finds the first child of a NODE with the given DATA.

FLAGS specifies which types of children are to be searched, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.

Returns the found child node, or *undef* if the DATA is not found.

Gets the position of the first child of a NODE which contains the given DATA. Returns the index of the child of node which contains data, or -1 if DATA is not found.

Gets the position of a NODE with respect to its siblings. CHILD must be a child of NODE. The first child is numbered 0, the second 1, and so on. Returns the position of CHILD with respect to its siblings.

Returns the first child of a NODE. Returns *undef* if NODE is *undef* or has
no children.

Returns the last child of a NODE. Returns *undef* if NODE is *undef* or has
no children.

Gets a child of a NODE, using the given INDEX. The first child is at INDEX 0.
If the INDEX is too big, *undef* is returned. Returns the child of NODE at INDEX.

Returns the first sibling of a NODE. This could possibly be the NODE itself.

Returns the previous sibling of a NODE.

Returns the next sibling of a NODE.

Returns the last sibling of a NODE. This could possibly be the NODE itself.

Returns TRUE if NODE is a leaf node (no children).

Returns TRUE if NODE is a root node (no parent nor siblings).

Returns the depth of NODE. If NODE is *undef*, the depth is 0. The root node has
a depth of 1. For the children of the root node, the depth is 2. And so on.

Returns the number of nodes in a tree.

FLAGS specifies which types of children are to be counted, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.

Returns the number of children of NODE.

Returns TRUE if NODE is an ancestor of DESCENDANT. This is true if NODE is the parent of DESCENDANT, or if NODE is the grandparent of DESCENDANT, etc.

Returns the maximum height of all branches beneath NODE. This is the maximum distance from NODE to all leaf nodes.

If NODE is *undef*, 0 is returned. If NODE has no children, 1 is returned.
If NODE has children, 2 is returned. And so on.

Unlinks NODE from a tree, resulting in two separate trees. The NODE to unlink becomes the root of a new tree.

An example for each function can be found in the test script **test.pl**.

Frederic Soriano, <frederic.soriano@alcatel.fr>

This package is free software and is provided ``as is'' without express or implied warranty. It may be used, redistributed and/or modified under the same terms as Perl itself.

API from the GLIB project, http://developer.gnome.org/doc/API/glib/glib-n-ary-trees.html.

Tree::Nary - Perl implementation of N-ary search trees. |