Description
Part 1:
You are required to design a BinSTree class that allows you to declare objects of type BinSTree
. The class implements a binary search tree and provides the interface to a storage of items of
type T by hiding the details of the pointer operations.
The declaration and partial implementation of the BinSTree class is in ”bstree.h”, which
includes the Node class in the given ”treenode.h”.
Implement all member functions except for void BinSTree::Delete(const T&
item)declared according to the comments and the visual examples below. Some of the member
functions are implemented for you. Please check them carefully to see how to update the member
variables to maintain the state of the BinSTree object.
The comments for your implementations are meant to guide you. If you have a correctly working
implementation of your own it is also ok.
The Insert method takes the data of the node as argument, dynamically create the node using
GetTreeNode and insert the node in the binary search tree. Insertion is always as a leaf node.
The FindNode method returns the node address of the searched data item and a pointer to its
parent, and NULL otherwise. If there are multiple, it returns the address of the one found first.
Assume class T has all comparison operators defined.
All methods should maintain the state of the BinSTree object by correctly modifying the class
members.
You can reuse member functions of the class (such as CopyTree and DeleteTree) to implement
other member class member functions.
Please make sure that you make the necessary checks to prevent any undesired state of the
BinSTree objects.
Note that BinSTree is a class template. The examples below are for a BinSTree class.
Your code will be checked using other template parameters (i.e. for different Ts, not necessarily
primitive data types) as well.
Examples:
BinSTree MyTree;
TreeNode * TreeP1, * TreeP2;
MyTree.Insert(90);
MyTree.Insert(150);
MyTree.Insert(180);
MyTree.Insert(75);
MyTree.Insert(100);
MyTree.Insert(120);
MyTree.Insert(130);
MyTree.Insert(110);
MyTree.Insert(40);
TreeP1=MyTree.FindNode(120,TreeP2);
cout<data;
Output: 100
Part 2:
void BinSTree::Delete(const T& item)declared according to the comments and
the visual examples below.
MyTree.Delete(150);
First the item to delete (150) is found. Then the
item for replacement is found (The highest
value on the left branch if there is any, or the
lowest value on the right branch).
Then the replacement is performed. Please
note that this is not a simple value change
since these are not just values, they are objects
indeed. Thus, the old object must be deleted
and all the pointers regarding the old and the
new objects (parents, children) must be
updated.
The final structure of the tree.
Regulations:
1. Use Code::Blocks IDE and choose GNU GCC Compiler while creating your project. Name your
project as “e_HW3”. Send the whole project folder compressed in a rar or zip
file. You will not get full credit if you fail to submit your project folder as required.
2. The code you uploaded should be compilable and the built file should be executable. We
have to see some output to grade your homeworks. So please make sure that you have
uploaded a working version for your homework.
3. You should insert comments to your source code at appropriate places without including any
unnecessary detail. Comments will be graded (On the condition that you have managed to
send a working code). A code with insufficient/excessive comments is not a proper piece of
work.
4. The homework is to be prepared individually. It is not allowed to prepare the homework as a
group. METU honor code is essential. Do not share your code. Any kind of involvement in
cheating will result in a zero grade for all homeworks, for both givers and receivers.
5. You have to give the links to any website you have benefitted from. You can add them to
your code as comments in the beginning.
6. Late submissions are welcome, but penalized according to the following policy:
– 1 day late submission: HW will be evaluated out of 70.
– 2 days late submission: HW will be evaluated out of 50.
– 3 days late submission: HW will be evaluated out of 30.
– 4 or more days late submission: HW will not be evaluated.
Good Luck!
