C++ You will implement a binary search tree data structure in C++, and turn in a

Question

C++

You will implement a binary search tree data structure in C++, and turn in a program evaluating the data structure. Implement a templated Binary Search Tree data structure, implementing the following functionality: Add(value to insert) Delete (delete given node, restructure sub-tree) Maximum(Find Maximum Key) To evaluate this data structure, write your program to read from an array of unsorted integers. You could also read from a data file (with the filename passed as a command line parameter) and populates the data structure. Rigorous testing is expected! Be sure to include tests for attempting to remove a node from an empty BST, attempting to insert a duplicate node, removing a node with no children, removing a node with one child, and removing a node with two children. Be sure to verify the BST organization and structure are correct.

Explanation / Answer

Answer:

code:

BST.h
=====
#ifndef BST_H
#define BST_H

struct TreeNode
{
int item;
TreeNode* Lchild;
TreeNode* Rchild;
};

class BST
{
public:
BST(); //default constructor
bool add(int i);
bool remove(int i);
void inorder();
int max();

private:
TreeNode *root;
void inorder(TreeNode *);
bool remove(TreeNode *n, TreeNode *parent);
};
#endif

BST.cpp
=======
#include "BST.h"
#include <iostream>
using namespace std;
BST::BST() //default constructor
{
root = NULL;
}
bool BST::add(int i)
{
TreeNode *n = new TreeNode();
n->item = i;
if(root == NULL)
{
root = n;
return true;
}
else
{
TreeNode *p = root;
while(p!=NULL)
{
if(i == p->item) //duplicate
return false;
else if(i < p->item) //if value to be inserted is less than current nodes value
{
if(p->Lchild == NULL) //go to left subtree
{
p->Lchild = n;
return true;
}
else
p = p->Lchild;
}
else
{
if(p->Rchild == NULL) //go to right subtree
{
p->Rchild = n;
return true;
}
else
p = p->Rchild;
}
}
}
return false;
}

bool BST::remove(TreeNode *n, TreeNode *parent)
{
if(n->Lchild == NULL && n->Rchild == NULL) //delteing leaf node
{
if(parent != NULL) //not deleting root
{
if(parent->Lchild == n)
parent->Lchild = NULL;
else
parent->Rchild = NULL;
}
else //deleteing root which is the only node in tree
root = NULL;

delete n;
}
else if(n->Lchild != NULL && n->Rchild ==NULL) //node to be deltedd has only left child
{
if(parent!=NULL)
{
if(parent->Lchild == n)
{
parent->Lchild = n->Lchild;
}
else
{
parent->Rchild = n->Lchild;
}
}
else //dleeting root with left child
root = n->Lchild; //update root

delete n;
}

else if(n->Rchild != NULL && n->Lchild ==NULL) //node to be deltedd has only right child
{
if(parent!=NULL) //not deleing root
{
if(parent->Lchild == n)
{
parent->Lchild = n->Rchild;
}
else
{
parent->Rchild = n->Rchild;
}
}
else //delting root with right child
root = n->Rchild; //update root

delete n;
}
else //node to be deleted has both the children
{
//find the rightmost node in left subtree i.e predecessor of n
TreeNode *q=n->Lchild,*qparent=n;
while(q->Rchild!=NULL)
{
qparent = q;
q = q->Rchild;
}
n->item = q->item;
return remove(q,qparent);
}

return true;
}
bool BST::remove(int i)
{

TreeNode *p = root, *parent =NULL;
while(p!=NULL)
{
if( p->item == i)
return remove(p, parent);

parent = p;
if(i < p->item)
{
p = p->Lchild;
}
else
{
p = p->Rchild;
}
}
return false;
}
void BST::inorder(TreeNode *n)
{
if(n == NULL )
return;

inorder(n->Lchild);
cout<<n->item<<" ";
inorder(n->Rchild);

}
void BST::inorder()
{
inorder(root);
cout<<endl;
}

int BST::max()
{
if(root == NULL)
return 0;
else
{
TreeNode* p = root;
while(p->Rchild != NULL)
p = p->Rchild;
return p->item;
}
}

BSTTest.cpp
==========
#include "BST.h"
#include <iostream>
using namespace std;
int main()
{
int arr[10] = { 15, 20 , 12, 60, 45, 33, 66, 89, 10, 3};
BST bst;
  
for(int i = 0 ; i < 10; i++)
{
cout << "Inserting " << arr[i] << endl;
bst.add(arr[i]);
}
  
  
int n;
string choice ="";
while(choice != "Q" && choice != "q")
{
cout << "Inorder traversal ";
bst.inorder();
  
cout << "Tree max: " << bst.max() << endl << endl;
  
  
cout << "(I)nsert (D)elete (Q)uit" << endl;
cout << "Enter your choice: ";
cin >> choice;
  
if(choice != "Q")
{
if(choice == "I" || choice == "i")
{
cout << "Enter a number to insert: ";
cin >> n;
if(bst.add(n))
cout << "Added " << n << " to BST " << endl;
else
cout << n << "is a duplicate" << endl;
  
}
else if(choice == "D" || choice == "d")
{
cout << "Enter number to delete from BST: ";
cin >> n;
if(bst.remove(n))
cout << "Removed " << n << " from BST " << endl;
else
cout << n << " not found in tree" << endl;

}
}
}
}

output:

Inserting 15
Inserting 20
Inserting 12
Inserting 60
Inserting 45
Inserting 33
Inserting 66
Inserting 89
Inserting 10
Inserting 3
Inorder traversal 3 10 12 15 20 33 45 60 66 89
Tree max: 89

(I)nsert (D)elete (Q)uit
Enter your choice: i
Enter a number to insert: 5
Added 5 to BST
Inorder traversal 3 5 10 12 15 20 33 45 60 66 89
Tree max: 89

(I)nsert (D)elete (Q)uit
Enter your choice: i
Enter a number to insert: 100
Added 100 to BST
Inorder traversal 3 5 10 12 15 20 33 45 60 66 89 100
Tree max: 100

(I)nsert (D)elete (Q)uit
Enter your choice: d
Enter number to delete from BST: 20
Removed 20 from BST
Inorder traversal 3 5 10 12 15 33 45 60 66 89 100
Tree max: 100

(I)nsert (D)elete (Q)uit
Enter your choice: d
Enter number to delete from BST: 66
Removed 66 from BST
Inorder traversal 3 5 10 12 15 33 45 60 89 100
Tree max: 100

(I)nsert (D)elete (Q)uit
Enter your choice: q

Please provide your valuable feedback.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.