Write a C++ program that creates a tree from given input, and prints the height
ID: 3686865 • Letter: W
Question
Write a C++ program that creates a tree from given input, and prints the height of the tree using the level-order traversal, where the height of a tree is defined as the maximum level number for any node in the tree.
The following is how we define tree nodes:
struct node
{ int item; node *l, *r;
node(int x)
{ item = x; l = 0; r = 0; }
};
typedef node* link;
(Hint: You may want to add a new field to the above definition to store the height of a node)
The trees for this assignment have the following properties:
1) Each node has zero, one, or two children (left child and right child);
2) Each node has a unique key. That is, the item in each node is different from items in all other nodes.
3) Each input item is also unique.
You may find the following function useful. This function visits nodes in a tree in level order starting at the given root h using a QUEUE (you can use any implementation for QUEUE):
void traverse(link root, int n)
{
link h;
QUEUE q(n);
q.put(root);
while (!q.empty())
{
h = q.get(); // get link h at the head of the queue
if (h->l != 0) q.put(h->l);
if (h->r != 0) q.put(h->r);
}
}
Your program will receive the following input and do the following for each input:
C <int r> : Create the root node with item r. If the tree is not empty (i.e. the root exists), return an error
L <int p> <int l>: Find the node with item p. Let u be that node. Create a new node v with item l. Make node v node u’s left child. If node u has already a left child, return an error
R <int p> <int r>: Find the node with item p. Let u be that node. Create a new node v with item r. Make node v node u’s right child. If node u has already a right child, return an error
P: Print the tree height using a level order traversal
See the example dialogue below:
C 5
Root node with item 5 has been created
C 10
Error: Tree is not empty
L 5 3
Node with item 3 has been added
R 5 4
Node with item 4 has been added
P
the tree height is 2 (using the level order traversal of the entire tree)
L 4 7
R 7 8
R 3 9
L 9 11
R 4 12
L 7 13
L 8 14
R 12 15
R 8 16
L 13 17
P
the tree height is 5 (using the level order traversal of the entire tree)
L 14 19
P
the tree height is 6 (using the level order traversal of the entire tree)
Explanation / Answer
#include < iostream >
using namespace std ;
struct node
{
int item ; node* l, node* r ;
node( int x )
{
item =x ; l =0 ; r =0 ;
}
node ( int x ,node* l ,node* r )
{
item =x ;
this->l =l ; this->r =r ;
}
} ;
typedef node* link ;
class QUEUE
{
private: link* q ;
int Node ;
int h, t ;
public:
QUEUE ( int maxiNode )
{
q =new link[maxiNode +1] ;
Node =maxiNode + 1 ;
h =Node ;
t =0 ;
}
int empty() const
{
return h % Node == t ;
}
void put ( link item )
{
q[t++] =item ;
t = t %Node ;
}
link get ( )
{
h =h %Node ;
return q[h++] ;
}
} ;
link h =0 ; // Initial head of the tree
link discover ( int x )
{
if( h ==0 )
{
cout<<" Empty Tree " ;
return 0 ;
}
link nperminent =h ;
// To discover the node with the value x and return its link
QUEUE q ( 100 ) ;
q.put ( nperminent ) ;
while( !q.empty ( ) )
{
nperminent =q.get ( ) ;
if( nperminent-> item ==x )
{
return nperminent ;
}
if( nperminent-> l !=0 ) q.put ( nperminent-> l ) ;
if( nperminent-> r !=0 ) q.put ( nperminent-> r ) ;
}
return 0 ;
}
void print ( link nperminent )
{
QUEUE q ( 100 ) ;
q.put ( nperminent ) ;
while( !q.empty ( ) )
{
nperminent =q.get ( ) ;
cout<< nperminent ->item<< ", " ;
if( nperminent -> l !=0 ) q.put ( nperminent -> l ) ;
if( nperminent -> r !=0 ) q.put ( nperminent -> r ) ;
}
}
void allDelete(link h)
{
// This deletes the entire binary tree
QUEUE q ( 100 ) ;
q.put ( h ) ;
while( !q.empty ( ) )
{
h =q.get ( ) ;
if( h -> l !=0 ) q.put ( h -> l ) ;
if( h -> r !=0 ) q.put ( h -> r ) ;
delete h ;
}
}
int main ( )
{
link nperminent =0 ;
char c ;
int n1 ,n2 ;
cout<<" Please type the i/p instructions ( X to quit): " ;
do
{
cin>>c ;
switch( c )
{
case 'C' :
cin >>n1 ;
if( h ==0 )
{
h =new node ( n1 ) ;
cout<<" Root node with item" <<n1 <<" has been created " ;
}
else
{
cout<<" Error : Tree isn't empty " ;
}
break ;
case 'L' :
cin>>n1 >>n2 ;
nperminent =discover ( n1 ) ;
if( nperminent !=0 )
{
if( nperminent -> l ==0 )
{
nperminent->l =new node ( n2 ) ;
cout<<" Node with item" <<n2 <<"has been added " ;
}else
{
cout<<" Error : The specified node already has a left child " ;
}
}else
{
cout<<" Error : The specified node does not exist " ;
}
break ;
case 'R' :
cin >>n1 >>n2 ;
nperminent =discover ( n1 ) ;
if( nperminent !=0 )
{
if( nperminent->r ==0)
{
nperminent->r =new node ( n2 ) ;
cout<<" Node with item" <<n2 <<" has been added " ;
}else
{
cout<<" Error : The specified node already has a right child " ;
}
}else
{
cout<<" Error : The specified node does not exist " ;
}
break ;
case 'P':
cin >>n1 ;
nperminent =discover ( n1 ) ;
if( h !=0 )
{
cout<<" Level-order traversal of the entire tree :" ;
print ( nperminent ) ;
}else
{
cout<<" Error : No elements to print " ;
}
break ;
case 'D':
cin >>n1 ;
nperminent =discover ( n1 ) ;
allDelete ( nperminent ) ;
nperminent =0 ;
break ;
case 'X':
cout<< " Exiting Program " ;
break ;
default:
cout<<" Invalid input entered. Try again. " ;
}
}
while( c !='X' ) ;
system ( " pause " ) ;
return 0 ;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.