aGrUM  0.13.2
binTreeNode.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
26 #ifndef GUM_BIN_TREE_NODE_H
27 #define GUM_BIN_TREE_NODE_H
28 
29 #include <agrum/agrum.h>
30 
31 namespace gum {
32 
34  enum class BinTreeDir : char { LEFT_CHILD = 0, RIGHT_CHILD = 1, NO_PARENT = 2 };
35 
36  // ===========================================================================
37  // === GENERIC NODE FOR A BINARY TREE ===
38  // ===========================================================================
39 
96  template < typename Val >
97  class BinTreeNode {
98  public:
99  // ============================================================================
101  // ============================================================================
103 
108  BinTreeNode(const Val& v);
109 
119  BinTreeNode(const BinTreeNode< Val >& from);
120 
127  ~BinTreeNode();
128 
130  // ============================================================================
132  // ============================================================================
134 
144  BinTreeNode< Val >& operator=(const BinTreeNode< Val >& from);
145 
150  Val& operator*();
151 
153  // ============================================================================
155  // ============================================================================
157 
162  Val& value();
163 
170  BinTreeNode< Val >* child(BinTreeDir dir) const;
171 
177  BinTreeNode< Val >* leftChild() const;
178 
184  BinTreeNode< Val >* rightChild() const;
185 
191  BinTreeNode< Val >* parent() const;
192 
197  BinTreeDir parentDir() const;
198 
207  BinTreeNode< Val >* insertLeftChild(const Val& val);
208 
215  void insertLeftChild(BinTreeNode< Val >& new_child);
216 
225  BinTreeNode< Val >* insertRightChild(const Val& val);
226 
233  void insertRightChild(BinTreeNode< Val >& new_child);
234 
243  BinTreeNode< Val >* insertChild(const Val& val, BinTreeDir child_dir);
244 
252  void insertChild(BinTreeNode< Val >& new_child, BinTreeDir child_dir);
253 
262  void eraseLeftLink();
263 
272  void eraseRightLink();
273 
283  void eraseLink(BinTreeDir tree_dir);
284 
292  BinTreeNode< Val >* leftmostNode() const;
293 
301  BinTreeNode< Val >* rightmostNode() const;
302 
310  BinTreeNode< Val >* root() const;
311 
313 
314  protected:
316  Val _val;
317 
320 
323 
325  BinTreeNode< Val >* _children[2];
326  };
327 
328 } /* namespace gum */
329 
330 
331 extern template class gum::BinTreeNode< int >;
332 
333 
334 // always include the implementation of the templates
336 
337 #endif // GUM_BIN_TREE_NODE_H
Val _val
The value stored in a node of the tree.
Definition: binTreeNode.h:316
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
BinTreeDir
The direction of a given edge in a binary tree.
Definition: binTreeNode.h:34
BinTreeDir _parent_dir
the direction to follow from the parent to reach the current node.
Definition: binTreeNode.h:322
Formula operator*(const Formula &a, const Formula &b)
Definition: formula_inl.h:469
Nodes of a binary trees.
Definition: binTreeNode.h:97
BinTreeNode< Val > * _parent
The parent of the node.
Definition: binTreeNode.h:319
Node class for various binary search trees.