Write a C++ program that creates a tree from given input, and prints the leaf no
ID: 3684384 • Letter: W
Question
Write a C++ program that creates a tree from given input, and prints the leaf nodes using the level-order traversal.
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;
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 : Create the root node with item r. If the tree is not empty (i.e. the root exists), return an error
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 : 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 items in nodes in a level order traversal manner
S : Find the node with item p. Let u be that node. Print the items in nodes in the subtree rooted at u in level order traversal manner
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
level order traversal of the entire tree: 5 3 4
S 4
Level order traversal of the asked subtree: 4
L 4 7
R 7 8
R 3 9
L 9 11
R 4 12
L 7 13
S 3
level order traversal of the asked subtree: 3 9 11
S 4
level order traversal of the asked subtree: 4 7 12 13 8
L 8 14
R 12 15
R 8 16
L 13 17
P
level order traversal of the entire tree: 5 3 4 9 7 12 11 13 8 15 17 14 16
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 N;
int head;
int tail;
public:
QUEUE(int maxN) {
q = new link[maxN + 1];
N = maxN + 1;
head = N;
tail = 0;
}
int empty() const {
return head % N == tail;
}
void put(link item) {
q[tail++] = item;
tail = tail % N;
}
link get() {
head = head % N;
return q[head++];
}
};
link head = 0;
link find(int x) {
if (head == 0) {
cout << " Empty Tree ";
return 0;
}
link temp = head;
QUEUE q(100);
q.put(temp);
while (!q.empty()) {
temp = q.get();
if (temp->item == x) {
return temp;
}
if (temp->l != 0) q.put(temp->l);
if (temp->r != 0) q.put(temp->r);
}
return 0;
}
void print(link temp) {
QUEUE q(100);
q.put(temp);
while (!q.empty()) {
temp = q.get();
cout << temp->item << ", ";
if (temp->l != 0) q.put(temp->l);
if (temp->r != 0) q.put(temp->r);
}
}
void deleteAll(link h)
{
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 temp = 0;
char c;
int n1, n2;
cout << " Please enter the input";
do {
cin >> c;
switch (c) {
case 'C': cin >> n1;
if (head == 0) {
head = new node(n1);
cout << " Root node with item " << n1 << " has been created ";
} else {
cout << " Error: Tree is not empty ";
}
break;
case 'L': cin >> n1 >> n2;
temp = find(n1);
if (temp != 0) {
if (temp->l == 0) {
temp->l = new node(n2);
cout << " Node with item " << n2 << " has been added ";
}
else {
cout << " Error! ";
}
}
else {
cout << " Error!! ";
}
break;
case 'R': cin >> n1 >> n2;
temp = find(n1);
if (temp != 0) {
if (temp->r == 0) {
temp->r = new node(n2);
cout << " Node with item " << n2 << " has been added ";
}
else {
cout << " Error! ";
}
}
else {
cout << " Error!";
}
break;
case 'P': cin >> n1;
temp = find(n1);
if (head != 0) {
cout << " Level-order traversal of the entire tree: ";
print(temp);
}
else {
cout << " Error! No elements ";
}
break;
case 'D': cin >> n1;
temp = find(n1);
deleteAll(temp);
temp = 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.