Main Page | Modules | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

# BasicDataStructures::BinarySearchTree< BinarySearchTreeType > Class Template Reference

`#include <BinarySearchTree.h>`

Inheritance diagram for BasicDataStructures::BinarySearchTree< BinarySearchTreeType >:

List of all members.

## Public Member Functions
| BinarySearchTree ()
virtual | ~BinarySearchTree ()
| BinarySearchTree (const BinarySearchTree &original_type)
BinarySearchTree & | operator= (const BinarySearchTree &original_copy)
const unsigned long | size (void)
void | clear (void)
const unsigned long | height (node *starting_node=0)
node * | add (const BinarySearchTreeType &input)
node * | del (const BinarySearchTreeType &input)
bool | is_in (const BinarySearchTreeType &input)
void | display_inorder (BinarySearchTreeType *return_array)
void | display_preorder (BinarySearchTreeType *return_array)
void | display_postorder (BinarySearchTreeType *return_array)
void | display_breadth_first_search (BinarySearchTreeType *return_array)
BinarySearchTreeType *& | get_pointer_to_node (const BinarySearchTreeType &element)
## Protected Types
enum | Direction_Types { NOT_FOUND, LEFT, RIGHT, ROOT }
## Protected Member Functions
const unsigned long | height_recursive (node *current)
node *& | find (const BinarySearchTreeType &element, node **parent)
node *& | find_parent (const BinarySearchTreeType &element)
void | display_postorder_recursive (node *current, BinarySearchTreeType *return_array, unsigned long &index)
void | fix_tree (node *current)
## Protected Attributes
node * | root
enum BasicDataStructures::BinarySearchTree::Direction_Types | direction
unsigned long | BinarySearchTree_size
## Classes
struct | node

## Detailed Description

### template<class BinarySearchTreeType>
class BasicDataStructures::BinarySearchTree< BinarySearchTreeType >

Initilize with the following structure

BinarySearchTree<TYPE>

OR

AVLBalancedBinarySearchTree<TYPE>

Use the AVL balanced tree if you want the tree to be balanced after every deletion and addition. This avoids the potential worst case scenario where ordered input to a binary search tree gives linear search time results. It's not needed if input will be evenly distributed, in which case the search time is O (log n). The search time for the AVL balanced binary tree is O (log n) irregardless of input.

Has the following member functions unsigned long height(<index>) - Returns the height of the tree at the optional specified starting index. Default is the root add(element) - adds an element to the BinarySearchTree bool del(element) - deletes the node containing element if the element is in the tree as defined by a comparison with the == operator. Returns true on success, false if the element is not found bool is_in(element) - returns true if element is in the tree as defined by a comparison with the == operator. Otherwise returns false display_inorder(array) - Fills an array with an inorder search of the elements in the tree. USER IS REPONSIBLE FOR ALLOCATING THE ARRAY!. display_preorder(array) - Fills an array with an preorder search of the elements in the tree. USER IS REPONSIBLE FOR ALLOCATING THE ARRAY!. display_postorder(array) - Fills an array with an postorder search of the elements in the tree. USER IS REPONSIBLE FOR ALLOCATING THE ARRAY!. display_breadth_first_search(array) - Fills an array with a breadth first search of the elements in the tree. USER IS REPONSIBLE FOR ALLOCATING THE ARRAY!. clear - Destroys the tree. Same as calling the destructor unsigned long height() - Returns the height of the tree unsigned long size() - returns the size of the BinarySearchTree get_pointer_to_node(element) - returns a pointer to the comparision element in the tree, allowing for direct modification when necessary with complex data types. Be warned, it is possible to corrupt the tree if the element used for comparisons is modified. Returns NULL if the item is not found

EXAMPLE

     BinarySearchTree<int> A;
     A.add(10);
     A.add(15);
     A.add(5);
     int* array = new int [A.size()];
     A.display_inorder(array);
     array[0]; // returns 5
     array[1]; // returns 10
     array[2]; // returns 15

compress - reallocates memory to fit the number of elements. Best used when the number of elements decreases

clear - empties the BinarySearchTree and returns storage The assignment and copy constructors are defined

Note:
  The template type must have the copy constructor and assignment operator defined and must work with >, <, and == All elements in the tree MUST be distinct The assignment operator is defined between BinarySearchTree and AVLBalancedBinarySearchTree as long as they are of the same template type. However, passing a BinarySearchTree to an AVLBalancedBinarySearchTree will lose its structure unless it happened to be AVL balanced to begin with Requires queue_linked_list.cpp for the breadth first search used in the copy constructor, overloaded assignment operator, and display_breadth_first_search.

## Member Enumeration Documentation

template<class BinarySearchTreeType>
enum BasicDataStructures::BinarySearchTree::Direction_Types`[protected]`

  | Enumeration values:
  NOT_FOUND |
  LEFT |
  RIGHT |
  ROOT |

## Constructor & Destructor Documentation

template<class BinarySearchTreeType>
BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree | ( |  | ) |

| Default Constructor

template<class BinarySearchTreeType>
BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::~BinarySearchTree | ( |  | ) | `[virtual]`

| Destructor

template<class BinarySearchTreeType>
BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree | ( | const BinarySearchTree< BinarySearchTreeType > & | original_type | ) |

  | Copy constructor Parameters:
  | original_type | The tree to duplicate

## Member Function Documentation

template<class BinarySearchTreeType>
BinarySearchTree< BinarySearchTreeType >::node * BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::add | ( | const BinarySearchTreeType & | input | ) |

  | Add input to the tree and return its node. Parameters:
  | input | the value to add to the tree.
Returns: node a pointer to the node of the tree corresponding to input. Reimplemented in BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >, BasicDataStructures::AVLBalancedBinarySearchTree< RPCNode >, and BasicDataStructures::AVLBalancedBinarySearchTree< ObjectIDNode >.

template<class BinarySearchTreeType>
void BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::clear | ( | void |  | ) | `[inline]`

| Clear the tree removind all values.

template<class BinarySearchTreeType>
BinarySearchTree< BinarySearchTreeType >::node * BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::del | ( | const BinarySearchTreeType & | input | ) |

  | Remove input from the tree and return a pointer to the node previously containing input. Parameters:
  | input | The value to remove of the tree
Returns: A pointer to the node previously containing input. Reimplemented in BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >, BasicDataStructures::AVLBalancedBinarySearchTree< RPCNode >, and BasicDataStructures::AVLBalancedBinarySearchTree< ObjectIDNode >.

template<class BinarySearchTreeType>
void BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::display_breadth_first_search | ( | BinarySearchTreeType * | return_array | ) |

  | Display the tree using a breadth first search. Put the children of the current node into the queue. Pop the queue, put its children into the queue, repeat until queue is empty. Parameters:
  | return_array | The resulting array of elements.

template<class BinarySearchTreeType>
void BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::display_inorder | ( | BinarySearchTreeType * | return_array | ) |

  | Store all element of the tree in return_array. The element of the resulting arrayare in order. Parameters:
  | return_array | The resulting array of elements.

template<class BinarySearchTreeType>
void BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::display_postorder | ( | BinarySearchTreeType * | return_array | ) | `[inline]`

  | Store all element of the tree in return_array. The element of the resulting array follow a postfix order walk throught the nodes of the tree. Parameters:
  | return_array | The resulting array of elements.

template<class BinarySearchTreeType>
void BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::display_postorder_recursive | ( | node * | current,
|  | BinarySearchTreeType * | return_array,
|  | unsigned long & | index
| ) | `[protected]`

  | Does the recursive operation of filling the array. Used by display_postorder. Parameters:
  | current | The node to start the postfix order walk throught of the tree.
  | return_array | The resulting array storing elements.
  | index | The index of the next element in the array.

template<class BinarySearchTreeType>
void BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::display_preorder | ( | BinarySearchTreeType * | return_array | ) |

  | Store all element of the tree in return_array. The element of the resulting array follow a prefix order walk throught the nodes of the tree. Parameters:
  | return_array | The resulting array of elements.

template<class BinarySearchTreeType>
BinarySearchTree< BinarySearchTreeType >::node *& BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::find | ( | const BinarySearchTreeType & | element,
|  | node ** | parent
| ) | `[protected]`

  | Find recursively a node of the tree. Parameters:
  | element | The value to search for
  `[out]` | parent | a pointer to the parent node
Returns: The node storing the element.

template<class BinarySearchTreeType>
BinarySearchTree< BinarySearchTreeType >::node *& BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::find_parent | ( | const BinarySearchTreeType & | element | ) | `[protected]`

  | Find the parent node of an element Parameters:
  | element | The element to search for.
Returns: The node parent of the node containing element

template<class BinarySearchTreeType>
void BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::fix_tree | ( | node * | current | ) | `[protected]`

  | Reorganized the nodes of the tree following an insertion or a deletion of a node. Parameters:
  | current | the node to fix.

template<class BinarySearchTreeType>
BinarySearchTreeType *& BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::get_pointer_to_node | ( | const BinarySearchTreeType & | element | ) |

  | Get a pointer to the node containing element. Parameters:
  | element | The element to find
Returns: a pointer to the element if found, 0 otherwise.

template<class BinarySearchTreeType>
const unsigned long BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::height | ( | node * | starting_node = `0` | ) |

  | Get the height of the tree or one of its subtree. Parameters:
  | starting_node | compute the height of the tree starting at node. if starting_node is 0 then the height is computed from the root node.
Returns: the height of the tree.

template<class BinarySearchTreeType>
const unsigned long BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::height_recursive | ( | node * | current | ) | `[protected]`

template<class BinarySearchTreeType>
bool BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::is_in | ( | const BinarySearchTreeType & | input | ) |

  | Test if the tree contains input. Parameters:
  | input | The element to search for.
Returns: true if the element is in the tree false otherwise.

template<class BinarySearchTreeType>
BinarySearchTree< BinarySearchTreeType > & BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::operator= | ( | const BinarySearchTree< BinarySearchTreeType > & | original_copy | ) |

  | Assignment operator Parameters:
  | original_copy | The object to copy
Returns: a reference to the current object.

template<class BinarySearchTreeType>
const unsigned long BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::size | ( | void |  | ) |

| Retrieve the number of element of the tree.

## Member Data Documentation

template<class BinarySearchTreeType>
unsigned long BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::BinarySearchTree_size`[protected]`

| Store the number of node composing the tree.

template<class BinarySearchTreeType>
enum BasicDataStructures::BinarySearchTree::Direction_Types BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::direction`[protected]`

template<class BinarySearchTreeType>
node* BasicDataStructures::BinarySearchTree< BinarySearchTreeType >::root`[protected]`

| Root of the tree.

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

- Projects/raknet/include/raknet/BinarySearchTree.h