This program requires you to implement a Binary Search Tree with the following o

ID: 3833589 • Letter: T

Question

This program requires you to implement a Binary Search Tree with the following operations to be executed on the tree: 1) Insert a node in the tree 2) Delete a node from the tree 3) Search for an element in the tree 4) Traverse the tree in Preorder: Inorder and Postorder fashion 5) Print the contents of the tree in preorder fashion The program shall comprise of the following files: TreeNode.h BST.h BST.cpp Driver.cpp The file TreeNode.h shall consist of the class TreeNode. This class shall have BST as its friend class. In addition, this file should also contain the description of the class constructor and accessor functions (thus we avoid creating a TreeNode.cpp) The outline of this file is as follows: Class TreeNode {Friend class BST: Public: TreeNode(); //default constructor TreeNode(int i: TreeNode* L = 0; TreeNode* R = 0); //explicit value constructor int getltan () const; // accessor function private: int item; TreeNode *Lchild; TreeNode *Rchild;}: TreeNode::TreeNode() {Lchild = Rchild = NULL:} TreeNode::TreeNode(int I, TreeNode *L = 0: TreeNode *R = 0): item(i), Lchild(L): Rchild(R) {} int TreeNode::^getltem() const {return item;}

Explanation / Answer

Below are the list of files needed for the question. Sample output is also attached. Please don't forget to rate the answer if it helped. Thank you very much.

compile using g++ BST.cpp Driver.cpp

Tree.h

#ifndef TREENODE_H
#define TREENODE_H
#include <iostream>
class BST;
class TreeNode
{
friend class BST;
public:
TreeNode(); //default constructor
TreeNode(int i, TreeNode* L=0, TreeNode* R=0);//explicit value constructor
int getItem() const;
void setItem(int i);
private:
int item;
TreeNode *Lchild;
TreeNode *Rchild;
};

inline TreeNode::TreeNode()
{
item = 0;
Lchild = Rchild = NULL;
}

inline TreeNode::TreeNode(int i, TreeNode *L, TreeNode *R)
{
item = i;
Lchild = L;
Rchild = R;
}

inline void TreeNode::setItem(int i)
{
item = i;
}

inline int TreeNode::getItem() const
{
return item;
}

#endif

BST.h

#ifndef BST_H
#define BST_H
#include "TreeNode.h"
class BST
{
public:
BST(); //default constructor
void add(int i);
bool find(int i);
bool remove(int i);
void inorder();
void preorder();
void postorder();

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

BST.cpp

#include "BST.h"
#include <iostream>
using namespace std;
BST::BST() //default constructor
{
root = NULL;
}
void BST::add(int i)
{
TreeNode *n = new TreeNode(i);
if(root == NULL)
root = n;
else
{
TreeNode *p = root;
while(p!=NULL)
{
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;
}
else
p = p->Lchild;
}
else
{
if(p->Rchild == NULL) //go to right subtree
{
p->Rchild = n;
return;
}
else
p = p->Rchild;
}
}
}

}
bool BST::find(int i)
{

TreeNode *p = root;
while(p!=NULL)
{
if( p->item == i)
return true;
if(i < p->item)
{
p = p->Lchild;
}
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;
}

void BST::preorder(TreeNode *n)
{
if(n == NULL )
return;

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

}

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

void BST::postorder(TreeNode *n)
{
if(n == NULL )
return;

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

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

Driver.cpp

#include "BST.h"
#include <iostream>
using namespace std;

void mainMenu(BST &tree);

int main()
{
BST tree;
mainMenu(tree);
cout<<"program exiting...";
return 0;
}

void mainMenu(BST &tree)
{
int choice;
int n;
while(true)
{
cout<<" 1. Add"<<endl;
cout<<"2. Remove"<<endl;
cout<<"3. Search"<<endl;
cout<<"4. Inorder traversal"<<endl;
cout<<"5. Preorder traversal"<<endl;
cout<<"6. Postorder traversal"<<endl;
cout<<"7. Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the number to be added: ";
cin>>n;
tree.add(n);
cout<<n<<" added to tree"<<endl;
break;
case 2:
cout<<"Enter the number to be removed: ";
cin>>n;
if(tree.remove(n))
cout<<n<<" removed from tree"<<endl;
else
cout<<n <<" not found in tree"<<endl;
break;
case 3:
cout<<"Enter the number to be searched: ";
cin>>n;
if(tree.find(n))
cout<<n<<" found in tree"<<endl;
else
cout<<n <<" not found in tree"<<endl;
break;
case 4:
cout<<"Inorder traversal of tree is "<<endl;
tree.inorder();
break;
case 5:
cout<<"Preorder traversal of tree is "<<endl;
tree.preorder();
break;
case 6:
cout<<"Postorder traversal of tree is "<<endl;
tree.postorder();
break;
case 7:
return;
default:
cout<<"Invalid menu choice!"<<endl;

}
}
}

output

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 2
Enter the number to be removed: 4
4 not found in tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 1
Enter the number to be added: 4
4 added to tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 4
Inorder traversal of tree is
4

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 2
Enter the number to be removed: 4
4 removed from tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 4
Inorder traversal of tree is

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 1
Enter the number to be added: 5
5 added to tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 1
Enter the number to be added: 3
3 added to tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 4
Inorder traversal of tree is
3 5

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 2
Enter the number to be removed: 5
5 removed from tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 4
Inorder traversal of tree is
3

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 1
Enter the number to be added: 8
8 added to tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 1
Enter the number to be added: 7
7 added to tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 4
Inorder traversal of tree is
3 7 8

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 2
Enter the number to be removed: 7
7 removed from tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 4
Inorder traversal of tree is
3 8

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 1
Enter the number to be added: 7
7 added to tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 1
Enter the number to be added: 9
9 added to tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 1
Enter the number to be added: 10
10 added to tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 4
Inorder traversal of tree is
3 7 8 9 10

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 2
Enter the number to be removed: 8
8 removed from tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 4
Inorder traversal of tree is
3 7 9 10

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 3
Enter the number to be searched: 8
8 not found in tree

1. Add
2. Remove
3. Search
4. Inorder traversal
5. Preorder traversal
6. Postorder traversal
7. Exit
Enter your choice: 7
program exiting...

Navigate

This program requires you to implement a Binary Search Tree with the following o

This program requires you to use a loop as well as the switch statement. You wil

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

This program requires you to implement a Binary Search Tree with the following o

Question

Explanation / Answer

Related Questions

Navigate