(Printing Trees) Write a recursive member function outputTree to display a binary tree ob- ject on the screen. The function should output the tree row by row, with the top of the tree at the left of the screen and the bottom of the tree toward the right of the screen. Each row is output verti- cally. For example, the binary tree illustrated in Fig. 20.24 is output as follows:
Note that the rightmost leaf node appears at the top of the output in the rightmost column and the root node appears at the left of the output. Each column of output starts five spaces to the right of the previous column. Function outputTree should receive an argument totalSpaces representing the number of spaces preceding the value to be output (this variable should start at zero, so the root node is output at the left of the screen). The function uses a modified inorder traversal to output the tree—it starts at the rightmost node in the tree and works back to the left. The algorithm is as
follows:
While the pointer to the current node is not null
Recursively call outputTree with the right subtree of the current node and
totalSpaces + 5
Use a for statement to count from 1 to totalSpaces and output spaces
Output the value in the current node
Set the pointer to the current node to point to the left subtree of the current node Increment totalSpaces by 5.
// Template Tree class definition.
#ifndef TREE_H
#define TREE_H
#include
#include
#include "TreeNode.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 outputTree() 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;
void outputTreeHelper( TreeNode< NODETYPE > *, int ) 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
// print the tree
template< typename NODETYPE >
void Tree< NODETYPE >::outputTree() const
{
outputTreeHelper( rootPtr, 0 );
} // end function outputTree
// utility function to print the tree
template< typename NODETYPE >
void Tree< NODETYPE >::outputTreeHelper( TreeNode< NODETYPE > *ptr,
int totalSpaces ) const
{
if ( ptr != 0 )
{
outputTreeHelper( ptr->rightPtr, totalSpaces + 5 );
for ( int i = 1; i <= totalSpaces; i++ )
cout << ' ';
cout << ptr->data << '\n';
outputTreeHelper( ptr->leftPtr, totalSpaces + 5 );
} // end if
} // end function outputTreeHelper
#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";
for ( int i = 1; i <= 15; i++ )
{
intVal = rand() % 100;
cout << intVal << ' ';
intTree.insertNode( intVal );
23 } // end loop
cout << "\n\nThe tree is:\n";
intTree.outputTree();
return 0; // indicates successful termination
} // end main
The values being placed in the tree are:
54 78 81 14 74 20 84 59 71 8 76 41 65 27 47
The tree is:
84
81
78
76
74
71
65
59
54
47
41
27
20
14
8
You might also like to view...
What is one of the advantages to using HTML5 elements?
What will be an ideal response?
A(n) _______ is one snapshot of the operating system taken by the System Restore utility
Fill in the blank(s) with correct word
What is the general name of the processor feature that AMD calls HyperTransport?
A. multicore processing B. multithreading C. virtualization support D. integrated graphics
Unless you specify otherwise, variables in C++ are automatically passed by reference.
Answer the following statement true (T) or false (F)