You are required to create a program using C++ programming language to implement binary search tree (BST).
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 |
crossorigin="anonymous">
style="display:block; text-align:center;"
data-ad-layout="in-article"
data-ad-format="fluid"
data-ad-client="ca-pub-7200085558568021"
data-ad-slot="3193586076">
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 |
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:
- The structure of classes which you need to create in the
required program is given below.
crossorigin="anonymous">
style="display:block"
data-ad-format="autorelaxed"
data-ad-client="ca-pub-7200085558568021"
data-ad-slot="6426802817">
Graphical
Representation:
Sample Output:
crossorigin="anonymous">
style="display:block; text-align:center;"
data-ad-layout="in-article"
data-ad-format="fluid"
data-ad-client="ca-pub-7200085558568021"
data-ad-slot="3193586076">
Solution:
Program:
#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;
}
};
crossorigin="anonymous">
style="display:block"
data-ad-format="autorelaxed"
data-ad-client="ca-pub-7200085558568021"
data-ad-slot="6426802817">
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;
}
OUTPUT:
No comments