Nodes of a binary trees. More...

#include <agrum/tools/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

Val	The 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 104 of file binTreeNode.h.

Constructor & Destructor Documentation

◆ BinTreeNode() [1/2]

template<typename Val >

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

Basic constructor: a node without parent nor children.

Parameters

v	The value stored in the node.

◆ BinTreeNode() [2/2]

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

from	The node to copy.

◆ ~BinTreeNode()

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

◆ child()

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

dir	The direction where we loog for a child.

Returns: Returns the child of a node.

◆ eraseLeftLink()

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.

◆ eraseLink()

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_dir The direction where to remove the link.

◆ eraseRightLink()

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.

◆ insertChild() [1/2]

template<typename Val >

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

Adds a new child to the current node.

Parameters

val	The value to add.
child_dir	The direction where to add the child.

Returns: Returns a pointer on the new created child

Exceptions

DuplicateElement Raised if the current node had already a child in the child_dir subtree.

◆ insertChild() [2/2]

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_child	The child to add.
child_dir	The direction where to add the child.

Exceptions

DuplicateElement Raised if the current node had already a child in the child_dir direction or if new_child already has a parent .

◆ insertLeftChild() [1/2]

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

val	The value to store in the new child.

Returns: a pointer on the new created child

Exceptions

DuplicateElement if the current node had already a left child

◆ insertLeftChild() [2/2]

template<typename Val >

void gum::BinTreeNode< Val >::insertLeftChild ( BinTreeNode< Val > & new_child )

Adds a new left child to the current node.

Parameters

new_child The child to add.

Exceptions

DuplicateElement Raised if the current node had already a left child or if new_child already has a parent.

◆ insertRightChild() [1/2]

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

val	The value to store in the new child.

Returns: a pointer on the new created child

Exceptions

DuplicateElement if the current node had already a left child

◆ insertRightChild() [2/2]

template<typename Val >

void gum::BinTreeNode< Val >::insertRightChild ( BinTreeNode< Val > & new_child )

Adds a new right child to the current node.

Parameters

new_child The child to add.

Exceptions

DuplicateElement Raised if the current node had already a right child or if new_child already has a parent.

◆ leftChild()

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.

◆ leftmostNode()

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.

◆ operator*()

template<typename Val >

Val& gum::BinTreeNode< Val >::operator* ( )

Alias for method value.

Returns: Return the value stored in this node.

◆ operator=()

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

from	The node to copy.

Returns: Returns this gum::BinTreeNode.

◆ parent()

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.

◆ parentDir()

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.

◆ rightChild()

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.

◆ rightmostNode()

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.

◆ root()

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.

◆ value()

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

◆ children_

template<typename Val >

BinTreeNode< Val >* gum::BinTreeNode< Val >::children_[2]

protected

The children of the current node.

Definition at line 332 of file binTreeNode.h.

◆ parent_

template<typename Val >

BinTreeNode< Val >* gum::BinTreeNode< Val >::parent_

protected

The parent of the node.

Definition at line 326 of file binTreeNode.h.

◆ parent_dir_

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 329 of file binTreeNode.h.

◆ val_

template<typename Val >

Val gum::BinTreeNode< Val >::val_

protected

The value stored in a node of the tree.

Definition at line 323 of file binTreeNode.h.

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

agrum/tools/core/binTreeNode.h

Public Member Functions

Protected Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ BinTreeNode() [1/2]

◆ BinTreeNode() [2/2]

◆ ~BinTreeNode()

Member Function Documentation

◆ child()

◆ eraseLeftLink()

◆ eraseLink()

◆ eraseRightLink()

◆ insertChild() [1/2]

◆ insertChild() [2/2]

◆ insertLeftChild() [1/2]

◆ insertLeftChild() [2/2]

◆ insertRightChild() [1/2]

◆ insertRightChild() [2/2]

◆ leftChild()

◆ leftmostNode()

◆ operator*()

◆ operator=()

◆ parent()

◆ parentDir()

◆ rightChild()

◆ rightmostNode()

◆ root()

◆ value()

Member Data Documentation

◆ children_

◆ parent_

◆ parent_dir_

◆ val_

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