Binary Search Tree is a data structure that holds a list of items with a tree st
ID: 3695142 • Letter: B
Question
Binary Search Tree is a data structure that holds a list of items with a tree structure, which has the following feature: the left child is always smaller than the parent; while the right child is greater than or equal to the parent. In this homework, you need to implement all functions in the defined Binary Search Tree (BSTree) class (prototype is provided by the instructor). Please download the header file (BSTree.h) from ecourses, read the comments and complete them using C++. You need to implement all of the BSTree ADT functions in BSTree.cpp file, and test them in main.cpp.
#ifndef BSTREE_H
#define BSTREE_H
template <typename DataType>
class TreeNode
{
public:
TreeNode(DataType newData, TreeNode<DataType>* LEFT, TreeNode<DataType>* RIGHT);
DataType info;
TreeNode<DataType>* left;
TreeNode<DataType>* right;
};
template <typename DataType>
class BSTree
{
public:
BSTree();
~BSTree();
bool isEmpty() const;
bool isFull() const;
int NumofNodes() const;
void makeEmpty();
void clearHelper(TreeNode<DataType>* node);
void insertItem(DataType newItem);
void insertHelper(TreeNode<DataType> *&node, DataType& newItem);
bool deleteItem(DataType& item);
bool deleteHelper(TreeNode<DataType> *&node, DataType& item);
TreeNode<DataType>* retrieveItem(DataType& item);
TreeNode<DataType>* retrieveHelper(TreeNode<DataType> *node, DataType& newItem);
void print() const;
void print_inorder(TreeNode<DataType>* node) const;
void print_preorder(TreeNode<DataType>* node) const;
void print_postorder(TreeNode<DataType>* node) const;
void showStructure () const;
void showHelper( TreeNode<DataType> *p, int level ) const;
int getHeight () const;
int getHeightHelper ( TreeNode<DataType> *p ) const;
private:
TreeNode<DataType>* root;
int numofNodes;
};
#endif
Explanation / Answer
Program:
#include<iostream>
#include<conio.h>
#include<stdlib.h>
#define BSTREE_H
using namespace std;
# define max 10
typedef struct list
{
int data;
struct list *next;
} node_type;
node_type *ptr[max],*root[max],*temp[max];
class BSTree
{
public:
int index;
Dictionary();
void insert(int);
void search(int);
void delete_ele(int);
};
BSTree::BSTree()
{
index=-1;
for(int i=0; i<max; i++)
{
root[i]=NULL;
ptr[i]=NULL;
temp[i]=NULL;
}
}
void BSTree::insert(int key)
{
index=int(key%max);
ptr[index]=(node_type*)malloc(sizeof(node_type));
ptr[index]->data=key;
if(root[index]==NULL)
{
root[index]=ptr[index];
root[index]->next=NULL;
temp[index]=ptr[index];
}
else
{
temp[index]=root[index];
while(temp[index]->next!=NULL)
temp[index]=temp[index]->next;
temp[index]->next=ptr[index];
}
}
void BSTree::search(int key)
{
int flag=0;
index=int(key%max);
temp[index]=root[index];
while(temp[index]!=NULL)
{
if(temp[index]->data==key)
{
cout<<" Search key is found!!";
flag=1;
break;
}
else temp[index]=temp[index]->next;
}
if (flag==0)
cout<<" search key not found.......";
}
void BSTree::delete_ele(int key)
{
index=int(key%max);
temp[index]=root[index];
while(temp[index]->data!=key && temp[index]!=NULL)
{
ptr[index]=temp[index];
temp[index]=temp[index]->next;
}
ptr[index]->next=temp[index]->next;
cout<<" "<<temp[index]->data<<" has been deleted.";
temp[index]->data=-1;
temp[index]=NULL;
free(temp[index]);
}
main()
{
int val,ch,n,num;
char c;
BSTree b;
do
{
cout<<" MENU: 1.Create";
cout<<" 2.Search for a value 3.Delete an value";
cout<<" Enter your choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<" Enter the number of elements to be inserted:";
cin>>n;
cout<<" Enter the elements to be inserted:";
for(int i=0; i<n; i++)
{
cin>>num;
b.insert(num);
}
break;
case 2:
cout<<" Enter the element to be searched:";
cin>>n;
b.search(n);
case 3:
cout<<" Enter the element to be deleted:";
cin>>n;
b.delete_ele(n);
break;
default:
cout<<" Invalid Choice.";
}
cout<<" Enter y to Continue:";
cin>>c;
}
while(c=='y');
getch();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.