aGrUM  0.13.2
gum::BinTreeNode< Val > Class Template Reference

Nodes of a binary trees. More...

#include <agrum/core/binTreeNode.h>

Public Member Functions

Class constructors and destructors
 BinTreeNode (const Val &v)
 Basic constructor: a node without parent nor children. More...
 
 BinTreeNode (const BinTreeNode< Val > &from)
 copy constructor: creates a new disconnected node with the same value as "from". More...
 
 ~BinTreeNode ()
 Class destructor. More...
 
Class operators
BinTreeNode< Val > & operator= (const BinTreeNode< Val > &from)
 Copy operator: copy the value of from into this. More...
 
Val & operator* ()
 Alias for method value. More...
 
Class accessors and modifiers
Val & value ()
 Returns the value stored in a node of the binary search tree. More...
 
BinTreeNode< Val > * child (BinTreeDir dir) const
 Returns the given child of a node. More...
 
BinTreeNode< Val > * leftChild () const
 Returns the given child of a node. More...
 
BinTreeNode< Val > * rightChild () const
 Returns the given child of a node. More...
 
BinTreeNode< Val > * parent () const
 Returns the parent of a node. More...
 
BinTreeDir parentDir () const
 Returns the direction of the edge parent->current node, if any. More...
 
BinTreeNode< Val > * insertLeftChild (const Val &val)
 Adds a new left child to the current node. More...
 
void insertLeftChild (BinTreeNode< Val > &new_child)
 Adds a new left child to the current node. More...
 
BinTreeNode< Val > * insertRightChild (const Val &val)
 Adds a new left child to the current node. More...
 
void insertRightChild (BinTreeNode< Val > &new_child)
 Adds a new right child to the current node. More...
 
BinTreeNode< Val > * insertChild (const Val &val, BinTreeDir child_dir)
 Adds a new child to the current node. More...
 
void insertChild (BinTreeNode< Val > &new_child, BinTreeDir child_dir)
 Adds a new child to the current node. More...
 
void eraseLeftLink ()
 Remove the link between the current node and its left child. More...
 
void eraseRightLink ()
 Remove the link between the current node and its right child. More...
 
void eraseLink (BinTreeDir tree_dir)
 Remove the link between the current node and one of its children. More...
 
BinTreeNode< Val > * leftmostNode () const
 Returns the leftmost node of the current tree. More...
 
BinTreeNode< Val > * rightmostNode () const
 Returns the rightmost node of the current tree. More...
 
BinTreeNode< Val > * root () const
 Returns the top ancestor of the current tree. More...
 

Protected Attributes

Val _val
 The value stored in a node of the tree. More...
 
BinTreeNode< Val > * _parent
 The parent of the node. More...
 
BinTreeDir _parent_dir
 the direction to follow from the parent to reach the current node. More...
 
BinTreeNode< Val > * _children [2]
 The children of the current node. More...
 

Detailed Description

template<typename Val>
class gum::BinTreeNode< Val >

Nodes of a binary trees.

BinTreeNode is the base class for nodes of binary trees. It is equipped with the material to add nodes to or remove them from the tree. The class ensures that trees are always a coherent structure, that is, it is not possible to have a node X having, say, a left child, and this child having no parent or a parent different from X.

Template Parameters
ValThe value's type storde in the gum::BinTreeNode.
Usage example:
// create a node containing an integer
BinTreeNode<int> node1 (33);
// get the integer contained in the node
std::cerr << node1.value () << std::endl;
std::cerr << *node1 << std::endl;
// create a disconnected node containing the same value as node1
BinTreeNode<int> node2 = node1;
BinTreeNode<int> node3 (3); node3 = node1;
// insert left and right children
node1.insertLeftChild(node2);
node1.insertRightChild(node3);
BinTreeNode<int>* node4 = node2.insertLeftChild(3);
BinTreeNode<int>* node5 = node2.insertRightChild(4);
BinTreeNode<int>* node6 = node4.insertChild(5, GUM_BIN_TREE_LEFT_CHILD);
BinTreeNode<int>* node7 = node4.insertChild(6, GUM_BIN_TREE_RIGHT_CHILD);
BinTreeNode<int> node8 (55), node9(44);
node3.insertChild(node8, GUM_BIN_TREE_LEFT_CHILD);
node3.insertChild(node9, GUM_BIN_TREE_RIGHT_CHILD);
// get the parents and children
BinTreeNode<int>* node8 = node.parent();
node8 = node1.leftChild();
node8 = node1.rightChild();
node8 = node1.child(gum::GUM_BIN_TREE_LEFT_CHILD);
node8 = node1.child(gum::GUM_BIN_TREE_RIGHT_CHILD);
// remove links between parents and children
node1.eraseLeftLink(); // erase the connection between node1 and node2
node1.eraseRightLink(); // erase the connection between node1 and node3
node2.eraseLink(gum::GUM_BIN_TREE_LEFT_CHILD); // erase (node2,node4)
node2.eraseLink(gum::GUM_BIN_TREE_RIGHT_CHILD); // erase (node2;node5)

Definition at line 97 of file binTreeNode.h.

Constructor & Destructor Documentation

template<typename Val>
gum::BinTreeNode< Val >::BinTreeNode ( const Val &  v)

Basic constructor: a node without parent nor children.

Parameters
vThe value stored in the node.
template<typename Val>
gum::BinTreeNode< Val >::BinTreeNode ( const BinTreeNode< Val > &  from)

copy constructor: creates a new disconnected node with the same value as "from".

Warning
Although the new node contains the same value as from, it has no parent, nor any children, even if from has some.
Parameters
fromThe node to copy.
template<typename Val>
gum::BinTreeNode< Val >::~BinTreeNode ( )

Class destructor.

In addition to removing the node, this method updates appropriately its parent and children

Member Function Documentation

template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::child ( BinTreeDir  dir) const

Returns the given child of a node.

Warning
If the child does not exists, the method returns a 0 pointer.
Parameters
dirThe direction where we loog for a child.
Returns
Returns the child of a node.
template<typename Val>
void gum::BinTreeNode< Val >::eraseLeftLink ( )

Remove the link between the current node and its left child.

Note that only the link is removed, i.e., the left child is not removed itself nor, a fortiori, the left subtree of the current node. If there is no left child, the method does nothing. In particular, it does not raise any exception.

template<typename Val>
void gum::BinTreeNode< Val >::eraseLink ( BinTreeDir  tree_dir)

Remove the link between the current node and one of its children.

Note that only the link is removed, i.e., the child is not removed itself nor, a fortiori, its subtree. If the child does not exist, the method does nothing. In particular, it does not raise any exception.

Parameters
tree_dirThe direction where to remove the link.
template<typename Val>
void gum::BinTreeNode< Val >::eraseRightLink ( )

Remove the link between the current node and its right child.

Note that only the link is removed, i.e., the right child is not removed itself nor, a fortiori, the right subtree of the current node. If there is no right child, the method does nothing. In particular, it does not raise any exception.

template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::insertChild ( const Val &  val,
BinTreeDir  child_dir 
)

Adds a new child to the current node.

Parameters
valThe value to add.
child_dirThe direction where to add the child.
Returns
Returns a pointer on the new created child
Exceptions
DuplicateElementRaised if the current node had already a child in the child_dir subtree.
template<typename Val>
void gum::BinTreeNode< Val >::insertChild ( BinTreeNode< Val > &  new_child,
BinTreeDir  child_dir 
)

Adds a new child to the current node.

Parameters
new_childThe child to add.
child_dirThe direction where to add the child.
Exceptions
DuplicateElementRaised if the current node had already a child in the child_dir direction or if new_child already has a parent .
template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::insertLeftChild ( const Val &  val)

Adds a new left child to the current node.

Warning
the new child is created on the C++ heap (i.e., using a dynamic memory allocation)
Parameters
valThe value to store in the new child.
Returns
a pointer on the new created child
Exceptions
DuplicateElementif the current node had already a left child
template<typename Val>
void gum::BinTreeNode< Val >::insertLeftChild ( BinTreeNode< Val > &  new_child)

Adds a new left child to the current node.

Parameters
new_childThe child to add.
Exceptions
DuplicateElementRaised if the current node had already a left child or if new_child already has a parent.
template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::insertRightChild ( const Val &  val)

Adds a new left child to the current node.

Warning
the new child is created on the C++ heap (i.e., using a dynamic memory allocation)
Parameters
valThe value to store in the new child.
Returns
a pointer on the new created child
Exceptions
DuplicateElementif the current node had already a left child
template<typename Val>
void gum::BinTreeNode< Val >::insertRightChild ( BinTreeNode< Val > &  new_child)

Adds a new right child to the current node.

Parameters
new_childThe child to add.
Exceptions
DuplicateElementRaised if the current node had already a right child or if new_child already has a parent.
template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::leftChild ( ) const

Returns the given child of a node.

Warning
If the child does not exists, the method returns a 0 pointer.
Returns
Retuns the left child of this node.
template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::leftmostNode ( ) const

Returns the leftmost node of the current tree.

If there is no left child, the method returns this.

Returns
The left most node in the current tree.
template<typename Val>
Val& gum::BinTreeNode< Val >::operator* ( )

Alias for method value.

Returns
Return the value stored in this node.
template<typename Val>
BinTreeNode< Val >& gum::BinTreeNode< Val >::operator= ( const BinTreeNode< Val > &  from)

Copy operator: copy the value of from into this.

However, this does not change the current connections (parents and children) of this.

Parameters
fromThe node to copy.
Returns
Returns this gum::BinTreeNode.
template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::parent ( ) const

Returns the parent of a node.

Warning
If the parent does not exists, the method returns a 0 pointer.
Returns
Returns the parent of this node.
template<typename Val>
BinTreeDir gum::BinTreeNode< Val >::parentDir ( ) const

Returns the direction of the edge parent->current node, if any.

Returns
Returns the direction of the edge parent->current node, if any.
template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::rightChild ( ) const

Returns the given child of a node.

Warning
If the child does not exists, the method returns a 0 pointer.
Returns
Retuns the right child of this node.
template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::rightmostNode ( ) const

Returns the rightmost node of the current tree.

If there is no right child, the method returns this.

Returns
The right most node in the current tree.
template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::root ( ) const

Returns the top ancestor of the current tree.

If the current node has no parent, the the method returns this.

Returns
Returns the top ancestor of the current tree.
template<typename Val>
Val& gum::BinTreeNode< Val >::value ( )

Returns the value stored in a node of the binary search tree.

Returns
The value stored in this node.

Member Data Documentation

template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::_children[2]
protected

The children of the current node.

Definition at line 325 of file binTreeNode.h.

template<typename Val>
BinTreeNode< Val >* gum::BinTreeNode< Val >::_parent
protected

The parent of the node.

Definition at line 319 of file binTreeNode.h.

template<typename Val>
BinTreeDir gum::BinTreeNode< Val >::_parent_dir
protected

the direction to follow from the parent to reach the current node.

Definition at line 322 of file binTreeNode.h.

template<typename Val>
Val gum::BinTreeNode< Val >::_val
protected

The value stored in a node of the tree.

Definition at line 316 of file binTreeNode.h.


The documentation for this class was generated from the following file: