lab_trees
Tempestuous Trees
PreorderTraversal< T > Class Template Reference

A derived, templatized class for preorder traversal algorithms on trees. More...

#include <PreorderTraversal.h>

Inheritance diagram for PreorderTraversal< T >:
[legend]
Collaboration diagram for PreorderTraversal< T >:
[legend]

Public Member Functions

 PreorderTraversal (typename BinaryTree< T >::Node *root)
 Initializes a Preorder TreeTraversal of a tree, with the traversal storing the tree's root. More...
 
TreeTraversal< T >::Iterator begin ()
 Returns an iterator for the traversal starting at the root node. More...
 
TreeTraversal< T >::Iterator end ()
 Returns an iterator for the traversal one past the end of the traversal. More...
 
void add (typename BinaryTree< T >::Node *&treeNode)
 Adds the children of the given node to the stack to be processed later The right child is added before the left child to ensure that the left is popped before the right, thus following the rules of preorder traversals. More...
 
BinaryTree< T >::Node * pop ()
 Removes and returns the current node in the traversal. More...
 
BinaryTree< T >::Node * peek () const
 Returns the current node in the traversal or NULL if the stack is empty. More...
 
bool empty () const
 Returns true if the traversal is empty. More...
 

Private Attributes

std::stack< typename BinaryTree< T >::Node * > stack
 
BinaryTree< T >::Node * root
 

Detailed Description

template<typename T>
class PreorderTraversal< T >

A derived, templatized class for preorder traversal algorithms on trees.

Simulates an iterative traversal of a given tree using a stack and a given root node.

Constructor & Destructor Documentation

◆ PreorderTraversal()

template<typename T >
PreorderTraversal< T >::PreorderTraversal ( typename BinaryTree< T >::Node *  root)
inline

Initializes a Preorder TreeTraversal of a tree, with the traversal storing the tree's root.

Parameters
rootThe root node of the tree

Member Function Documentation

◆ add()

template<typename T >
void PreorderTraversal< T >::add ( typename BinaryTree< T >::Node *&  treeNode)
inlinevirtual

Adds the children of the given node to the stack to be processed later The right child is added before the left child to ensure that the left is popped before the right, thus following the rules of preorder traversals.

Parameters
treeNodeThe subroot whose children should be added

Implements TreeTraversal< T >.

◆ begin()

template<typename T >
TreeTraversal<T>::Iterator PreorderTraversal< T >::begin ( )
inlinevirtual

Returns an iterator for the traversal starting at the root node.

Important for the sake of looping through an iterator's contents.

Returns
The iterator object pointing to the first node in the traversal

Implements TreeTraversal< T >.

◆ empty()

template<typename T >
bool PreorderTraversal< T >::empty ( ) const
inlinevirtual

Returns true if the traversal is empty.

Returns
true if the traversal is empty.

Implements TreeTraversal< T >.

◆ end()

template<typename T >
TreeTraversal<T>::Iterator PreorderTraversal< T >::end ( )
inlinevirtual

Returns an iterator for the traversal one past the end of the traversal.

Important for the sake of looping through an iterator's contents.

Returns
The iterator object pointing to the element after the end of the traversal.

Implements TreeTraversal< T >.

◆ peek()

template<typename T >
BinaryTree<T>::Node* PreorderTraversal< T >::peek ( ) const
inlinevirtual

Returns the current node in the traversal or NULL if the stack is empty.

Returns
The current node in the traversal

Implements TreeTraversal< T >.

◆ pop()

template<typename T >
BinaryTree<T>::Node* PreorderTraversal< T >::pop ( )
inlinevirtual

Removes and returns the current node in the traversal.

Returns
The current node in the traversal

Implements TreeTraversal< T >.


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