Write a C++ program that creates a tree from given input, and prints the height
ID: 3685780 • 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.h> // input output stream header file
#include <stdio.h> // standard input output header file
#include <stdlib.h> // standard library header file
//#include <string.h> // header file with string function
// #include <conio.h> // console input output header file
/*
Algorithm:
Define function: DisplayLevelOrder(input Tree)
open loop: for depth = 1 to height of the tree
call function: displayPresentLevel (parameter Tree, parameter depth);
displayPresentLevel (input Tree, input depth)
if depth > 1 then
recursive calls:
displayPresentLevel (tree->LeftChild, depth-1);
displayPresentLevel (tree->rightChild, depth-1);
*/
struct node {
int item;
node *l, *r; // left, right
node(int x) {
item = x;
l = 0;
r = 0;
}
int height;
}; // end struct node tag
typedef node *link;
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);
} // end while
} // end function traverse
struct node * makeTree(int item) {
// create a tree from input given
struct node *link = (struct node *) malloc(sizeof(struct node)); // allocate memory for new node
node->item = item;
node->l =
mode ->r =
return (node);
}
int main() // start main
{
cout << " Enter Data: C = Create Root node r = item value";
char c; int r;
cin >> c >> r ;
if ( c == "C" )
makeTree(r);
return 0; // exit
} // end of main()
// print height using level order traversal
// tree height = maximum level number of any node of tree
#include <iostream.h> // input output stream header file
#include <stdio.h> // standard input output header file
#include <stdlib.h> // standard library header file
//#include <string.h> // header file with string function
// #include <conio.h> // console input output header file
/*
Algorithm:
Define function: DisplayLevelOrder(input Tree)
open loop: for depth = 1 to height of the tree
call function: displayPresentLevel (parameter Tree, parameter depth);
displayPresentLevel (input Tree, input depth)
if depth > 1 then
recursive calls:
displayPresentLevel (tree->LeftChild, depth-1);
displayPresentLevel (tree->rightChild, depth-1);
*/
struct node {
int item;
node *l, *r; // left, right
node(int x) {
item = x;
l = 0;
r = 0;
}
int height;
}; // end struct node tag
typedef node *link;
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);
} // end while
} // end function traverse
void makeTree() {
// create a tree from input given
// print height using level order traversal
// tree height = maximum level number of any node of tree
}
int main() // start main
{
makeTree();
return 0; // exit
} // end of main()
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.