PreorderTraversal< T > Class Template Reference

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

#include <PreorderTraversal.h>

Inheritance diagram for PreorderTraversal< T >:

Collaboration diagram for PreorderTraversal< T >:

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

root	The 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

treeNode

The 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:

• TreeTraversals/PreorderTraversal.h