 |
CS301P ASSIGNMENT NO. 2 FALL 2022 |
KINDLY, DON’T COPY PASTE
CS301P ASSIGNMENT NO. 2 FALL 2022 || 100% RIGHT SOLUTION || DATA STRUCTURES (Practical) || BY VuTech
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 solving & submitting assignment:
It should be clear that your assignment will not get any credit (zero marks) if:
Ø The assignment is submitted after due date.
Ø The submitted assignment is other than .CPP file.
Ø The submitted code does NOT compile.
Ø The submitted assignment does NOT open or file is corrupted.
Ø The assignment is copied (from other student or ditto copy from handouts or internet).
Uploading instructions
For clarity and simplicity, you are required to upload/submit only one .CPP file.
Note: Use only Dev-C++ IDE.
Objectives
The objectives of this assignment are;
ü To make you familiar of programming with stack and Tree data structure
ü To traverse Binary Search Tree (BST) using different traversal methods
ü To perform some basic operations on BST and stack
For any query about the assignment, contact at cs301p@vu.edu.pk
Good Luck!
Problem Statement:
Write C++ program to create a Binary Search Tree from the data given below.
Values = {11,6,15,4,8,13,19,16}
Perform the post-order, preorder and inorder traversals on the BST constructed using above data. You will store these traversals in three different stacks using the push() method of stack. After that you will print these traversals in reverse order using the pop() method of stack.
You are required to develop a C++ program implementing Binary Search Tree (BST) and Stack data structure for the above scenario. Your program must meet the following requirements:
|
Details: Your solution must contain the following:
Required Output: |
Problem Statement:
Write C++ program to create a Binary Search Tree from the data given below.
Values = {11,6,15,4,8,13,19,16}
Perform the post-order, preorder and inorder traversals on the BST constructed using above data. You will store these traversals in three different stacks using the push() method of stack. After that you will print these traversals in reverse order using the pop() method of stack.
You are required to develop a C++ program implementing Binary Search Tree (BST) and Stack data structure for the above scenario. Your program must meet the following requirements:
Construct Binary Search Tree, based upon above given data.
Perform the In-order, pre-order, post-order traversals on BST.
Store the In-order, pre-order, post-order traversals in three different stacks using a single Stack class. (You will create only a single Stack class in your code. Using more than one Stack class is not allowed).
Stack should be implemented using linked list.
Print all three traversals in reverse order using pop() method of stack
Details:
Your solution must contain the following:
1. Node Class (for creating nodes of Stack)
2. Stack Class (for storing the traversals of BST. Same stack class will be used for making three different stacks)
3. TreeNode template Class (to create the BST given above. The class should contain the constructors, necessary getter and setters, insert() method for inserting the nodes in tree,3 traversal methods inOrder(), preOrder(), postOrder()
4. Main() method.
Required Output:
Note:
Make sure to follow the instructions mentioned above in the scenario. Moreover, your solution must be according to the Required Output and . Otherwise, you will get Zero marks.
Labs Covered: (Lab 5-9)
Deadline: Your assignment must be uploaded / submitted on or before, Tuesday January 24th 2023.
SOLUTION
#include <iostream>
#include <stack>
using namespace std;
template <typename T>
class TreeNode {
public:
T data;
TreeNode<T>* left;
TreeNode<T>* right;
TreeNode(T data) {
this->data = data;
left = NULL;
right = NULL;
}
void insert(T data) {
if (data < this->data) {
if (left == NULL) {
left = new TreeNode<T>(data);
} else {
left->insert(data);
}
} else {
if (right == NULL) {
right = new TreeNode<T>(data);
} else {
right->insert(data);
}
}
}
void inOrder(stack<T> &s) {
if (left != NULL) {
left->inOrder(s);
}
s.push(data);
if (right != NULL) {
right->inOrder(s);
}
}
void preOrder(stack<T> &s) {
s.push(data);
if (left != NULL) {
left->preOrder(s);
}
if (right != NULL) {
right->preOrder(s);
}
}
void postOrder(stack<T> &s) {
if (left != NULL) {
left->postOrder(s);
}
if (right != NULL) {
right->postOrder(s);
}
s.push(data);
}
};
int main() {
stack<int> s;
TreeNode<int>* root = new TreeNode<int>(11);
root->insert(6);
root->insert(15);
root->insert(4);
root->insert(8);
root->insert(13);
root->insert(19);
root->insert(16);
cout << "Reverse Order of In-Order Travsersal" << endl;
root->inOrder(s);
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
cout << "Reverse Order of Pre-Order Travsersal" << endl;
root->preOrder(s);
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
cout << "Reverse Order of Post-Order Travsersal" << endl;
root->postOrder(s);
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
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