Binary Search Tree in c++ In this assignment you will implement a Binary Search
ID: 3779039 • Letter: B
Question
Binary Search Tree in c++
In this assignment you will implement a Binary Search Tree ADT, using recursion, and then use it. For help in writing retrieve, insert, and print functions, see the Word document “How to write Recursive Functions.doc” and “Recursion and Pointer.doc”. For the delete functions, see “Deleting in a Binary Search Tree.doc”. All three are posted under Class documents.
Part I.
You are given below the contents of two files (TreeNode.h and BinarySearchTree.h) that you can copy. What you need to do is to implement all the member functions including the helper functions for making the list empty, for retrieving, inserting, and deleting, and for printing out the Tree.
Write your test program and follow the test plan given below.
Please turn in the BinarySearchTree.h with your implementations of the functions, the test program and its output.
Test plan (can use int to instantiate the template):
Initialize the empty tree
Start with an empty tree.
Print the tree
Check isEmpty
Test Insert, Print
Insert numbers to create a reasonably large tree with left and right subtrees (Example: insert in this order: 20, 10, 30, 8, 15, 12, 24, 38, 26), print after each insert
Check isFull
Test Retrieve
Retrieve numbers that are at a leaf, in the left subtree, in the right subtree and at the root. (example. 8, 15, 20, 24)
Try retrieving numbers not in the tree. (Example1, 17, 23)
Test Delete
Delete at least three numbers, choosing them so as to delete a leaf, a node with one child, an node with 2 children.(Using example above: delete 38, 24, 20) Print the tree after each delete.
Test delete of numbers not in the tree (Example: delete 1, 20 (should no longer be there), 25)
Check isEmpty
Test MakeEmpty
Make the tree empty.
Print the tree.
Test delete of number not in tree (Example: 5)
Check isFull
Test the tree after being made empty
Repeat the Test Insert, Print and the Test Delete.
// Content of TreeNode.h
// Original source attribution available. Modified by Molodowitch
// TreeNode template definition: each TreeNode object contains data, left pointer, and right pointer.
#ifndef TREENODE_H
#define TREENODE_H
template<class ItemType >class Tree; // forward declarations
template<class ItemType>
class TreeNode {
friendclass Tree< ItemType >; // make Tree a friend
public:
TreeNode( ItemType ); // constructor
TreeNode(); // constructor with data uninitialized
ItemType getData() const; // return data in the node
private:
ItemType data;
TreeNode< ItemType > *leftPtr;
TreeNode< ItemType > *rightPtr;
};
// Constructor
template<class ItemType>
TreeNode< ItemType >::TreeNode( ItemType newItem )
{
data = newItem;
leftPtr = NULL;
rightPtr = NULL;
}
template<class ItemType>
TreeNode< ItemType >::TreeNode( )
{
leftPtr = NULL;
rightPtr = NULL;
}
// Return a copy of the data in the node
template<class ItemType >
ItemType TreeNode< ItemType >::getData() const
{
return data;
}
#endif
// Content of BinarySearchTree.h
#include<iostream>
#include"TreeNode.h"
usingnamespace std;
//The following enumerated type declaration should be included.
enum TraversalOrderType {preorder, inorder, postorder};
template<class ItemType >
class Tree {
public:
// Constructor used before any operations are done on the list. // Initializes the list to empty.
//Preconditions: None.
//Postconditions: Tree is an empty Tree.
Tree();
//Destructor
//Precondition: Tree exists, but may be empty.
//Postcondition: makeEmpty is called to ensure the tree is empty // when the destructor is called.
~Tree();
//Returns True if the tree is empty, otherwise returns false
//Postcondition: Tree is unchanged.
bool isEmpty() const;
//Makes the tree empty if it is not empty already.
//Preconditions: The tree exists.
//Postconditions: Tree is now empty. Any dynamically allocated // memory which is no longer used is returned to the system.
void makeEmpty();
// Inserts a copy of newItem in the tree.
//Precondition: The tree exists, but may be empty. It has binary // search property. ItemType has comparison operators defined.
//Postcondition: if the tree already has an item where item == // newItem, the function returns false and the tree is unchanged. // Otherwise, the newItem is inserted in the tree preserving and the // binary search property is maintained.
bool insert( ItemType newItem);
// Given a searchItem, it tries to retrieve as foundItem, an item // in the tree where the item == searchItem.
// Precondition:The tree exists and has the binary search property. // It may be empty. ItemType has comparison operators defined.
// Postcondition: If the tree already has an item where item ==
// searchItem, foundItem is set to that item, and the function
// returns true.If the tree has no such item, the function returns // false and foundItem remains unchanged. The tree is unchanged.
bool retrieve( ItemType searchItem, ItemType & foundItem );
// Given a deleteItem, it deletes from the tree any item where item // == deleteItem.
// Precondition: Tree exists and has binary search property.
// ItemType has comparison operators defined.
// Postcondition: If the tree has an item where item == deleteItem, // that item is removed from the tree, and the function returns
// true, andthe binary search property is maintained. If the tree // has no such item, the function returns false and the tree
// remains unchanged.
bool deleteItem (ItemType deleteItem);
//Prints the information about all the items in the Tree in order
// to an ostream objectOutstream. The function should print nothing // (No messages!) if the Tree is empty. The particular order
// (preorder, inorder, or postorder) is given by order, a variable of // TraversalOrderType.
//Preconditions: Outstream has been assigned and opened forwriting // to. The insertion operator (<<) has been defined for objects of // class ItemType.
// Postconditions: Tree is unchanged. The information for all // items has been written out to Outstream in the order specified // by order.
void print(ostream & Outstream, TraversalOrderType order );
private:
TreeNode< ItemType > * rootPtr; // pointer to the root
//utility functions
void printHelper( TreeNode< ItemType > *, ostream &, TraversalOrderType);
bool insertHelper( TreeNode< ItemType > * & , ItemType );
bool deleteHelper( TreeNode< ItemType > * & , ItemType );
void deleteNode( TreeNode<ItemType > * & );
bool retrieveHelper( ItemType, TreeNode< ItemType > * & , ItemType& );
void makeEmptyHelper (TreeNode< ItemType > * &);
};
//Implement all functions in the template
Part II.
In the Data Structures Assignment, you should have used a binary search tree for keeing patient records. Replace the templates you used with the one you just wrote. You may need to add the part about writing to a binary file. Run and make sure it all still works.
Explanation / Answer
Note:
Given code used and required code added in the given method
Part-I.
// TreeNode.h
#ifndef TREENODE_H
#define TREENODE_H
template<class ItemType >class Tree; // forward declarations
template<class ItemType>
class TreeNode {
friendclass Tree< ItemType >; // make Tree a friend
public:
TreeNode( ItemType ); // constructor
TreeNode(); // constructor with data uninitialized
ItemType getData() const; // return data in the node
private:
ItemType data;
TreeNode< ItemType > *leftPtr;
TreeNode< ItemType > *rightPtr;
};
// Constructor
template<class ItemType>
TreeNode< ItemType >::TreeNode( ItemType newItem )
{
data = newItem;
leftPtr = NULL;
rightPtr = NULL;
}
template<class ItemType> TreeNode< ItemType >::TreeNode( )
{
leftPtr = NULL;
rightPtr = NULL;
}
// Return a copy of the data in the node
template<class ItemType > ItemType TreeNode< ItemType >::getData() const
{
return data;
}
#endif
// BinarySearchTree.h
#include<iostream>
#include"TreeNode.h"
usingnamespace std;
//The following enumerated type declaration should be included.
enum TraversalOrderType {preorder, inorder, postorder};
template<class ItemType >
class Tree {
public:
// Constructor used before any operations are done on the list. // Initializes the list to empty.
//Preconditions: None.
//Postconditions: Tree is an empty Tree.
Tree();
//Destructor
//Precondition: Tree exists, but may be empty.
//Postcondition: makeEmpty is called to ensure the tree is empty // when the destructor is called.
~Tree();
//Returns True if the tree is empty, otherwise returns false
//Postcondition: Tree is unchanged.
bool isEmpty() const;
//Makes the tree empty if it is not empty already.
//Preconditions: The tree exists.
//Postconditions: Tree is now empty. Any dynamically allocated // memory which is no longer used is returned to the system.
void makeEmpty();
// Inserts a copy of newItem in the tree.
//Precondition: The tree exists, but may be empty. It has binary // search property. ItemType has comparison operators defined.
//Postcondition: if the tree already has an item where item == // newItem, the function returns false and the tree is unchanged.
// Otherwise, the newItem is inserted in the tree preserving and the // binary search property is maintained.
bool insert( ItemType newItem);
// Given a searchItem, it tries to retrieve as foundItem, an item // in the tree where the item == searchItem.
// Precondition:The tree exists and has the binary search property. // It may be empty. ItemType has comparison operators defined.
// Postcondition: If the tree already has an item where item ==
// searchItem, foundItem is set to that item, and the function
// returns true.If the tree has no such item, the function returns // false and foundItem remains unchanged. The tree is unchanged.
bool retrieve( ItemType searchItem, ItemType & foundItem );
// Given a deleteItem, it deletes from the tree any item where item // == deleteItem.
// Precondition: Tree exists and has binary search property.
// ItemType has comparison operators defined.
// Postcondition: If the tree has an item where item == deleteItem, // that item is removed from the tree, and the function returns
// true, andthe binary search property is maintained. If the tree // has no such item, the function returns false and the tree
// remains unchanged.
bool deleteItem (ItemType deleteItem);
//Prints the information about all the items in the Tree in order
// to an ostream objectOutstream. The function should print nothing // (No messages!) if the Tree is empty. The particular order
// (preorder, inorder, or postorder) is given by order, a variable of // TraversalOrderType.
//Preconditions: Outstream has been assigned and opened forwriting // to. The insertion operator (<<) has been defined for objects of // class ItemType.
// Postconditions: Tree is unchanged. The information for all // items has been written out to Outstream in the order specified // by order.
void print(ostream & Outstream, TraversalOrderType order );
private:
TreeNode< ItemType > * rootPtr; // pointer to the root
//utility functions
void printHelper( TreeNode< ItemType > *, ostream &, TraversalOrderType);
bool insertHelper( TreeNode< ItemType > * & , ItemType );
bool deleteHelper( TreeNode< ItemType > * & , ItemType );
void deleteNode( TreeNode<ItemType > * & );
bool retrieveHelper( ItemType, TreeNode< ItemType > * & , ItemType& );
void makeEmptyHelper (TreeNode< ItemType > * &);
};
template<class ItemType> Tree<ItemType>::Tree()
{
rootPtr = NULL;
}
template<class ItemType> Tree<ItemType>::~Tree()
{
makeEmpty();
}
template<class ItemType> bool Tree<ItemType>::isEmpty() const
{
if(rootPtr == NULL)
{
return true;
}
else
{
return false;
}
}
template<class ItemType> void Tree<ItemType>::makeEmpty()
{
makeEmptyHelper(rootPtr);
}
template<class ItemType> bool Tree<ItemType>::insert( ItemType newItem)
{
if(rootPtr == NULL)
{
rootPtr->data = newItem;
return true;
}
else
{
return insertHelper(rootPtr, newItem);
}
}
template<class ItemType> bool insertHelper( TreeNode< ItemType > * & Insnode, ItemType ITitem)
{
if( ITitem < Insnode->data)//left
{
if(Insnode->leftPtr == NULL)
{
Insnode->leftPtr = new TreeNode<ItemType>(ITitem);
return true;
}
else
{
return insertHelper(Insnode->leftPtr,ITitem);
}
}
else if(Insnode->data < ITitem)//right
{
if(Insnode->righChild == NULL)
{
Insnode->rightPtr = new TreeNode<ItemType>(ITitem);
return true;
}
else
{
return insertHelper(Insnode->rightPtr,ITitem);
}
}
else// same value
{
return false;
}
}
template<class ItemType> bool Tree<ItemType>::retrieve( ItemType searchItem, ItemType & foundItem )
{
retrieveHelper ( searchitem, rootPtr, foundItem ) ;
}
template<class ItemType> bool Tree<ItemType>::deleteItem (ItemType deleteItem)
{
deleteHelper(rootPtr, deleteItem);
}
template<class ItemType> void Tree<ItemType>::print(ostream & Outstream, TraversalOrderType order)
{
printHelper(rootPtr,Outstream, order)
}
template<class ItemType> void printHelper( TreeNode< ItemType > *TNptr, ostream &os, TraversalOrderType Torder);
{
if (TNptr != NULL)
{
switch(Torder)
{
case preorder:
cout << TNptr->data;
printHelper(TNptr->leftPtr, Torder);
printHelper(TNptr->rightPtr, Torder);
break;
case inorder:
printHelper(TNptr->leftPtr, Torder);
cout << TNptr->data;
printHelper(TNptr->rightPtr, Torder);
break;
case postorder:
printHelper(TNptr->leftPtr, Torder);
printHelper(TNptr->rightPtr, Torder);
cout << TNptr->data;
}
}
}
template<class ItemType> bool deleteHelper( TreeNode< ItemType > * &TNptr , ItemType ITitem )
{
if ( ITitem < TNptr->info )
deleteHelper( TNptr->left , ITitem ) ;
else if ( ITitem > TNptr->info )
deleteHelper( TNptr->right , ITitem ) ;
else
{
deleteNode(TNptr);
}
}
template<class ItemType> void deleteNode( TreeNode<ItemType > * &TNtree )
{
ItemType TNitm;
TreeNode< ItemType>* tempITPtr;
tempITPtr = TNtree;
if ( TNtree->left == NULL ) {
TNtree = TNtree->right;
delete tempITPtr;
} else if (TNtree->right == NULL ) {
TNtree = TNtree->left;
delete tempITPtr;
} else {
while (TNtree->right != NULL)
TNtree = TNtree->right;
TNtree->info = TNtree->right;
deleteHelper(TNtree->left, TNtree->info);
}
}
template<class ItemType> bool retrieveHelper( ItemType ITitem, TreeNode< ItemType > * &ITptr , ItemType & ITfound)
{
if ( ITptr == NULL )
ITfound = false ;
else if ( ITitem < ITptr->info )
retrieveHelper( ITptr->left , ITitem, ITfound ) ;
else if ( ITitem > ITptr->info )
retrieveHelper( ITptr->right , ITitem, ITfound ) ;
else
{
ITfound = true ;
}
}
template<class ItemType> void makeEmptyHelper (TreeNode< ItemType > * &ITptr)
{
if (ITptr == nullptr)
{
return;
}
else
makeEmptyHelper(ITptr->leftPtr);
makeEmptyHelper(ITptr->rightPtr);
delete ITptr;
ITptr = nullptr;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.