Mid Term Question
CS201 MID TERM SOLVED MCQs || PAST PAPERS || GROUP-1 || INTRODUCTION TO PROGRAMMING || VuTech Visit Website For More Solutions www.vutechofficial.blogspot.com …
 |
CS301 ASSIGNMENT NO. 2 FALL 2022 |
Visit Website For More Solutions
www.vutechofficial.blogspot.com
SEND WHATSAPP OR E-MAIL FOR ANY QUERY
0325-6644800
kamranhameedvu@gmail.com
Instructions
Please read the following instructions carefully before submitting the
assignment solution:
It should be clear that your assignment will not
get any credit/marks if:
o
Assignment is
submitted after due date.
o
Submitted
assignment does not open or file is corrupt.
o Assignment is copied (From internet/students).
Recommended Tools
Assignment Submission
Instructions
You have to submit only “.cpp” file of your code on the assignments
interface from your LMS account.
Assignment
submitted in any other format will not be accepted and will be scaled with zero marks. No excuse will be accepted
on submitting solution file in any other format.
For any query related to assignment, please contact cs301@vu.edu.pk.
Problem Statement:
You are required to create a program using C++ programming language to implement binary search tree (BST).
Use the information given in the
following table as data source.
|
10 |
8 |
12 |
4 |
11 |
15 |
6 |
17 |
7 |
9 |
16 |
You are required to build the
binary search tree using the above data. Then search any number and check the
following details.
|
Query |
Possible Reply |
|
Element found? |
Yes/No |
|
Is it leaf node? |
Yes/No |
|
Sibling of node found? |
b is sibling or no sibling |
|
Left child? |
c is left child or no left
child |
|
Right child? |
d is right child or no right child |
|
Is node even or odd? |
Odd/Even |
|
Is prime? |
Yes/No |
|
Parent of node? |
e is parent of node |
|
Total external node? |
Count of external nodes |
|
Total internal nodes? |
Count of internal nodes |
|
Total internal links |
Count of internal links |
|
Total external links |
Count of external links |
Node: “b”, “c”, “d” and “e” are nodes which are associated with searched node.
Important Instructions:
You need to fulfill the following
requirements while solving the assignment task.
1. For the construction of BST use
only class, the use of struct will be considered an invalid
solution.
2. Read the whole give data from
left to right and save into BST (using 10 as root node).
Hint:
Graphical
Representation:
Sample Output:
|
Lectures
Covered: Lecture # 16 - 27 Due
Date: 24th
January, 2023 |
#include <iostream>
using namespace std;
class TreeNode {
int data;
TreeNode *left, *right;
public:
TreeNode(int data) {
this->data = data;
left = right = NULL;
}
void insert(int value) {
if (value < data) {
if (left == NULL) {
left = new TreeNode(value);
} else {
left->insert(value);
}
} else if (value > data) {
if (right == NULL) {
right = new TreeNode(value);
} else {
right->insert(value);
}
}
}
bool search(int value) {
if (data == value) {
cout << "Yes, " << value << " is found" << endl;
if (isLeaf()) {
cout << "Yes, it is a leaf node" << endl;
} else {
cout << "No, it is not a leaf node" << endl;
}
if (left != NULL) {
cout << "The left child of " << value << " is " << left->data << endl;
} else {
cout << "There is no left child for " << value << endl;
}
if (right != NULL) {
cout << "The right child of " << value << " is " << right->data << endl;
} else {
cout << "There is no right child for " << value << endl;
}
return true;
} else if (value < data) {
if (left != NULL) {
return left->search(value);
}
} else if (value > data) {
if (right != NULL) {
return right->search(value);
}
}
cout << "No, " << value << " is not found" << endl;
return false;
}
bool isLeaf() {
if (left == NULL && right == NULL) {
return true;
}
return false;
}
int internalNodes() {
int count = 0;
if (left != NULL) {
count += left->internalNodes();
}
if (right != NULL) {
count += right->internalNodes();
}
if (!isLeaf()) {
count++;
}
return count;
}
int externalNodes() {
int count = 0;
if (left != NULL) {
count += left->externalNodes();
}
if (right != NULL) {
count += right->externalNodes();
}
if (isLeaf()) {
count++;
}
return count;
}
int internalLinks() {
int count = 0;
if (left != NULL) {
count += left->internalLinks();
count++;
}
if (right != NULL) {
count += right->internalLinks();
count++;
}
return count;
}
int externalLinks() {
int count =0;
if (left != NULL) {
if (left->isLeaf()) {
count++;
}
count += left->externalLinks();
}
if (right != NULL) {
if (right->isLeaf()) {
count++;
}
count += right->externalLinks();
}
return count;
}
int findParent(int value, int parent) {
if (data == value) {
cout << "The parent of " << value << " is " << parent << endl;
return parent;
} else if (value < data) {
if (left != NULL) {
return left->findParent(value, data);
}
} else if (value > data) {
if (right != NULL) {
return right->findParent(value, data);
}
}
return 0;
}
int findSibling(int value, int parent) {
if (data == value) {
if (parent != 0) {
TreeNode *temp = new TreeNode(parent);
if (temp->left != NULL && temp->left->data == value) {
cout << "The sibling of " << value << " is " << temp->right->data << endl;
} else if (temp->right != NULL && temp->right->data == value) {
cout << "The sibling of " << value << " is " << temp->left->data << endl;
} else {
cout << "No sibling found" << endl;
}
} else {
cout << "No sibling found" << endl;
}
} else if (value < data) {
if (left != NULL) {
return left->findSibling(value, data);
}
} else if (value > data) {
if (right != NULL) {
return right->findSibling(value, data);
}
}
return 0;
}
void isPrimeEvenodd(int value) {
if (data == value) {
if (isPrime(value)) {
cout << value << " is a prime number" << endl;
} else {
cout << value << " is not a prime number" << endl;
}
if (value % 2 == 0) {
cout << value << " is an Even number" << endl;
} else {
cout << value << " is an Odd number" << endl;
}
} else if (value < data) {
if (left != NULL) {
left->isPrimeEvenodd(value);
}
} else if (value > data) {
if (right != NULL) {
right->isPrimeEvenodd(value);
}
}
}
bool isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
};
int main() {
int data[] = {10, 8, 12, 4, 11, 15, 6, 17, 7, 9, 16};
int choice, value;
TreeNode *root = new TreeNode(data[0]);
for (int i = 1; i < 11; i++) {
root->insert(data[i]);
}
cout << "Data" << endl << "____________" << endl;
cout << "Marks: ";
for (int i = 0; i < 11; i++) {
cout << data[i] << ",";
}
cout << endl << endl;
while (true) {
cout << "Enter your choice" << endl;
cout << "Entrer 1 to create BST" << endl;
cout << "Entrer 2 to search the node" << endl;
cout << "Entrer 3 to find the no. of internal nodes" << endl;
cout << "Entrer 4 to find the no. of external nodes" << endl;
cout << "Entrer 5 to find the no. of internal links" << endl;
cout << "Entrer 6 to find the no. of external links" << endl;
cout << "Entrer 0 to terminate the program" << endl;
cin >> choice;
if (choice == 1) {
cout << endl << "BST is being created..." << endl;
cout << "Done" << endl;
} else if (choice == 2) {
cout << "Enter the number you want to search in BST" << endl;
cin >> value;
if (root->search(value)) {
root->findParent(value, 0);
root->findSibling(value, 0);
root->isPrimeEvenodd(value);
}
} else if (choice == 3) {
cout << "Total internal nodes = " << root->internalNodes() << endl;
} else if (choice == 4) {
cout << "Total external nodes = " << root->externalNodes() << endl;
} else if (choice == 5) {
cout << "Total internal links = " << root->internalLinks() << endl;
} else if (choice == 6) {
cout << "Total external links = " << root->externalLinks() << endl;
} else if (choice == 0) {
break;
}
}
return 0;
}
Visit Website For More Solutions
www.vutechofficial.blogspot.com
KINDLY, DON’T COPY PASTE
SUBSCRIBE, SHARE, LIKE AND COMMENTS FOR MORE UPDATES
SEND WHATSAPP OR E-MAIL FOR ANY QUERY
0325-6644800
kamranhameedvu@gmail.com
About VuTech
Soratemplates is a blogger resources site is a provider of high quality blogger template with premium looking layout and robust design. The main mission of soratemplates is to provide the best quality blogger templates which are professionally designed and perfectlly seo optimized to deliver best result for your blog.
We provide Virtual University of Pakistan Study Materials such as Solution of Assignments, GDBs, Mid Term Solved Papers, Final Term Solved Papers, Mid Term Solved MCQs, and Final Term Solved MCQs. We also provide regular Semester Quizzes, Updated Handouts, and Short Questions and Answers. We help you with your research and many other educational-related topics, as far as we know. Furthermore, Share your problem with us and Please feel free to ask any related questions.
