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

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 fashiorn 5) Print the contents of the tree in preorder fashiorn 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: TreeNode0; //default constructor TreeNode(int i, TreeNode* L 0; TreeNode* R-0); //explicit value constructor int getltem O const; // accessor function private: int item; TreeNode *Lchild; TreeNode *Rchild;

Explanation / Answer

RECENTLY I HAVE IMPLEMENTED AND ANSWERED THE SAME:

PLEASE USE OF BELOW CODE

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;

}
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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