(Level-Order Binary Tree Traversal) The program of Figs. 20.20–20.22 illustrated three re- cursive methods of traversing a binary tree—inorder, preorder and postorder traversals. This exer- cise presents the level-order traversal of a binary tree, in which the node values are printed level by level, starting at the root node level. The nodes on each level are printed from left to right. The
level- order traversal is not a recursive algorithm. It uses a queue object to control the output of the nodes. The algorithm is as follows:
1) Insert the root node in the queue
2) While there are nodes left in the queue,
Get the next node in the queue
Print the node’s value
If the pointer to the left child of the node is not null
Insert the left child node in the queue
If the pointer to the right child of the node is not null
Insert the right child node in the queue.
Write member function levelOrder to perform a level-order traversal of a binary tree object. Modify the program of Figs. 20.20–20.22 to use this function. [Note: You will also need to modify and incorporate the queue-processing functions of Fig. 20.16 in this program.]
// Definition of template class QueueNode
#ifndef QUEUENODE_H
#define QUEUENODE_H
template< typename T > class Queue; // forward declaration
template < typename T >
class QueueNode
{
friend class Queue< T >;
public:
QueueNode( const T & = 0 );
T getData() const;
private:
T data;
QueueNode *nextPtr;
}; // end class QueueNode
// Member function definitions for class QueueNode
// constructor for class QueueNode
template < typename T >
QueueNode< T >::QueueNode( const T &d )
{
data = d;
nextPtr = 0;
} // end Queue constructor
// get function returns data
template < typename T >
T QueueNode< T >::getData() const
{
return data;
} // end function getData
#endif
// Definition of template class Queue
#ifndef QUEUE_H
#define QUEUE_H
#include
#include
#include "QueueNode.h"
using namespace std;
template < typename T >
class Queue
{
public:
Queue(); // default constructor
~Queue(); // destructor
void enqueue( T ); // insert item in queue
T dequeue(); // remove item from queue
bool isEmpty() const; // is the queue empty?
void print() const; // output the queue
private:
QueueNode< T > *headPtr; // pointer to first QueueNode
QueueNode< T > *tailPtr; // pointer to last QueueNode
}; // end class
// Member function definitions for class Queue
// constructor
template < typename T >
Queue< T >::Queue()
{
headPtr = tailPtr = 0;
} // end Queue constructor
// destructor
template < typename T >
Queue< T >::~Queue()
{
QueueNode< T > *tempPtr, *currentPtr = headPtr;
while ( currentPtr != 0 )
{
tempPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
delete tempPtr;
} // end while loop
} // end Queue destructor
// enqueue function
template < typename T >
void Queue< T >::enqueue( T d )
{
// create pointer to new node
QueueNode< T > *newPtr = new QueueNode< T >( d );
// if queue is empty
if ( isEmpty() )
headPtr = tailPtr = newPtr;
else // add to end
{
tailPtr->nextPtr = newPtr;
tailPtr = newPtr;
} // end else
} // end function enqueue
// dequeue function
template < typename T >
T Queue< T >::dequeue()
{
QueueNode< T > *tempPtr = headPtr;
headPtr = headPtr->nextPtr;
T value = tempPtr->data;
delete tempPtr;
if ( headPtr == 0 )
tailPtr = 0;
return value; // return value taken out
} // end function dequeue
// is the queue empty?
template < typename T >
bool Queue< T >::isEmpty() const
{
return headPtr == 0;
} // end function isEmpty
// print the queue
template < typename T >
void Queue< T >::print() const
{
QueueNode< T > *currentPtr = headPtr;
// Queue is empty
if ( isEmpty() )
cout << "Queue is empty\n";
else // Queue is not empty
{
cout << "The queue is:\n";
while ( currentPtr != 0 )
{
cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
} // end while
cout << endl;
} // end if...else
} // end function print
#endif
// Template TreeNode class definition.
#ifndef TREENODE_H
#define TREENODE_H
// forward declaration of class Tree
template< typename NODETYPE > class Tree;
// TreeNode class-template definition
template< typename NODETYPE >
class TreeNode
{
friend class Tree< NODETYPE >;
public:
// constructor
TreeNode( const NODETYPE &d )
: leftPtr( 0 ), // pointer to left subtree
data( d ), // tree node data
rightPtr( 0 ) // pointer to right subtree
{
// empty body
} // end TreeNode constructor
// return copy of node's data
NODETYPE getData() const
{
return data;
} // end getData function
private:
TreeNode< NODETYPE > *leftPtr; // pointer to left subtree
NODETYPE data;
TreeNode< NODETYPE > *rightPtr; // pointer to right subtree
}; // end class TreeNode
#endif
// Template Tree class definition.
#ifndef TREE_H
#define TREE_H
#include
#include
#include "TreeNode.h"
#include "Queue.h"
using namespace std;
// Tree class-template definition
template< typename NODETYPE > class Tree
{
public:
Tree(); // constructor
void insertNode( const NODETYPE & );
void preOrderTraversal() const;
void inOrderTraversal() const;
void postOrderTraversal() const;
void levelOrder() const;
private:
TreeNode< NODETYPE > *rootPtr;
// utility functions
void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & );
void preOrderHelper( TreeNode< NODETYPE > * ) const;
void inOrderHelper( TreeNode< NODETYPE > * ) const;
void postOrderHelper( TreeNode< NODETYPE > * ) const;
}; // end class Tree
// constructor
template< typename NODETYPE >
Tree< NODETYPE >::Tree()
{
rootPtr = 0; // indicate tree is initially empty
} // end Tree constructor
// insert node in Tree
template< typename NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{
insertNodeHelper( &rootPtr, value );
} // end function insertNode
// utility function called by insertNode; receives a pointer
// to a pointer so that the function can modify pointer's value
template< typename NODETYPE >
void Tree< NODETYPE >::insertNodeHelper(
TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
// subtree is empty; create new TreeNode containing value
if ( *ptr == 0 )
*ptr = new TreeNode< NODETYPE >( value );
else // subtree is not empty
{
// data to insert is less than data in current node
if ( value < ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
{
// data to insert is greater than data in current node
if ( value > ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
else // duplicate data value ignored
cout << value << " dup" << endl;
} // end else
} // end else
} // end function insertNodeHelper
// begin preorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{
preOrderHelper( rootPtr );
} // end function preOrderTraversal
// utility function to perform preorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 )
{
cout << ptr->data << ' '; // process node
preOrderHelper( ptr->leftPtr ); // traverse left subtree
preOrderHelper( ptr->rightPtr ); // traverse right subtree
} // end if
} // end function preOrderHelper
// begin inorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{
inOrderHelper( rootPtr );
} // end function inOrderTraversal
// utility function to perform inorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 )
{
inOrderHelper( ptr->leftPtr ); // traverse left subtree
cout << ptr->data << ' '; // process node
inOrderHelper( ptr->rightPtr ); // traverse right subtree
} // end if
} // end function inOrderHelper
// begin postorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{
postOrderHelper( rootPtr );
} // end function postOrderTraversal
// utility function to perform postorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 )
{
postOrderHelper( ptr->leftPtr ); // traverse left subtree
postOrderHelper( ptr->rightPtr ); // traverse right subtree
cout << ptr->data << ' '; // process node
} // end if
} // end function postOrderHelper
// perform level-order traversal
template< typename NODETYPE >
void Tree< NODETYPE >::levelOrder() const
{
Queue< TreeNode< NODETYPE > * > queue;
TreeNode< NODETYPE > *nodePtr;
if ( rootPtr != 0 )
queue.enqueue( rootPtr );
while ( !queue.isEmpty() )
{
nodePtr = queue.dequeue();
cout << nodePtr->data << ' ';
if ( nodePtr->leftPtr != 0 )
queue.enqueue( nodePtr->leftPtr );
if ( nodePtr->rightPtr != 0 )
queue.enqueue( nodePtr->rightPtr );
} // end while
} // end function levelOrder
#endif
#include
#include
#include
using namespace std;
#include "Tree.h"
int main()
{
srand( time( 0 ) ); // randomize the random number generator
Tree< int > intTree;
int intVal;
cout << "The values being placed in the tree are:\n";
// adding values into intTree
for ( int i = 1; i <= 15; i++ )
{
intVal = rand() % 100;
cout << intVal << ' ';
intTree.insertNode( intVal );
} // end for
cout << "\n\nThe level-order traversal is:\n";
intTree.levelOrder();
cout << endl;
return 0; // indicates successful termination
} // end main
The values being placed in the tree are:
82 6 27 35 91 85 68 23 41 32 11 87 96 60 84
The level-order traversal is:
82 6 91 27 85 96 23 35 84 87 11 32 68 41 60
Computer Science & Information Technology
You might also like to view...
What is the value of y after the following code executes:
float y = 3.4 + sqrt (25.0);
Computer Science & Information Technology
A(n) __________ is a unit of activity characterized by the execution of a sequence of instructions, a current state, and an associated set of system resources.
A) ?identifier B) ?process ? C) ?state D) ?kernel
Computer Science & Information Technology
VMM stores virtual hard disks in the library.
Answer the following statement true (T) or false (F)
Computer Science & Information Technology
A computer-generated report includes inventory information for 220 items. The information for each item is given on a separate line. If 50 lines will fit on a page, how many pages will it take to print the report?
Identify the data, condition, and unknown (Polya's components).
Computer Science & Information Technology