Assignment No.
02
Total Marks: 20
SEMESTER Fall 2024
Due Date: November 21, 2024
CS301- Data Structures
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:
o The assignment is submitted after the due date.
o The submitted code does NOT compile.
o The submitted assignment is other than .CPP file.
o The submitted assignment does NOT open or file is corrupted.
o 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.
Allowed Software:
You are only allowed to use the Dev-C++ IDE for writing your .cpp file.
Objective
The objective of this assignment is
o To make you familiarize with the binary search tree.
For any query about the assignment, contact at [email protected]
GOOD LUCK
Marks: 20
In the previous assignment, you developed a program that efficiently handled packing activities. Now, after the
packing process, we need to store the packets in a manner that facilitates efficient searching. Each packet is
labeled with a specific integer, and a strategic approach has been established for their storage on the shelves.
There are three types of shelves: Main Shelf, Left Shelf, and Right Shelf. The storage strategy is as follows:
1. The first packet is placed on the Main Shelf.
2. For each subsequent packets, its number is compared to the first packet's number. If the new packet's
number is less than the first, it is stored on the Left Shelf. If it is greater, it is placed on the Right Shelf.
This procedure is consistently applied to all packets, ensuring an organized and efficient storage system.
Now, you are required to write a C++ program that efficiently implements this storage strategy.
Your program consists of the following class:
BinarySearchTree
The BinarySerachTree must have the following attributes:
One private variable of integer type (label)
Two private pointer variables of BinarySearchTree type (left, right)
The BinarySearchTree must have the following functions:
BinarySearchTree(), default constructor which sets all the data members values as NULL.
BinarySearchTree(int label), one parameterize constructor to initialize the BinarySearchTree label attribute.
void setLabel(int label), this function is used to set the value of label attribute of the TreeNode class.
void setLeft(BinarySearchTree * left), this function is used to set the value of left attribute of TreeNode
class.
void setRight(BinarySearchTree * rigth), this function is used to set the value of right attribute of TreeNode
class.
int getLabel(), returns the value of label.
BinarySearchTree* getLeft(), returns the value of left.
BinarySearchTree* getRight(), returns the value of right.
int isLeaf(), which return true, if it is a leaf node, otherwise return false.
void insert(BinarySearchTree*root, int label) , this function should be used to store the node in the binary
search tree by implementing the binary search tree algorithm. Also apply the logic that zero digits and
duplicated digits should not be inserted in the binary search tree.
void display(), which display all the nodes in in-order traversal.
In the main() function:
You need to create a pointer to an object of the BinarySearchTree class, and an integer variable (Supposed numId).
Now take your VU Student id and ignore its alphabetic portion and merge the first two digits and last two digits of
your VU student id.
For example, if your student id is BC123467891, so you have to initialize the integer variable (numId) with the
value 1291. Please note down, that assigning value of “numId” is based on your own VU Student id digits. If
student does not provide his/her own VU ID digits, then zero marks will be awarded to such assignments.
Then display the value of “numId” on the screen. Then divide the “numId” value into its digits and insert these
digits individually into binary search tree by calling the insert() function.
At the end call the display() function, which display the tree elements in the in-order traversal fashion.
Different Sample Outputs are given:
If student id is 1291:
If student id is 2401:
If student id is 0001:
Lectures Covered: This assignment covers Lecture # 12 to 15.
Deadline: Your assignment must be uploaded/submitted on or before, November 21, 2024.
