Implement the class shown on the following slides. The class implements a binary
ID: 3751052 • Letter: I
Question
Implement the class shown on the following slides. The class implements a binary tree. At the top of the file include a comment that lists your name. Add a comment for each private method or private instance variable you add
You need to implement BinaryTree() , BinaryTree(String d) ,BinaryTree(BinaryTree b1, String d, BinaryTree b2) ,BinaryTree(String t, String open, String close, String empty) , InorderIterator implements Iterator, PostorderIterator implements Iterator, Iterator inorder(), Iterator postorder() , String toString()
Using Java, Not C or other programming languages.
public class BinaryTree {
//Implements a Binary Tree of Strings
private class Node {
private Node left;
private String data;
private Node right;
private Node parent; // reference to the parent node
// the parent is null for the root node
private Node(Node L, String d, Node r, Node p) {
left = L;
data = d;
right = r;
parent = p;
}
}
private Node root;
public BinaryTree() {
// create an empty tree
}
public BinaryTree(String d) {
// create a tree with a single node
}
public BinaryTree(BinaryTree b1, String d, BinaryTree b2) {
// merge the trees b1 AND b2 with a common root with data d
}
public BinaryTree(String t, String open, String close, String empty) {
/*
* create a binary tree from the in order format discussed in class. Assume t is
* a syntactically correct string representation of the tree. Open and close are
* the strings which represent the beginning and end markers of a tree. Empty
* represents an empty tree. The example in class used ( ) and ! for open, close
* and empty respectively. The data in the tree will not include strings
* matching open, close or empty. All tokens (data, open, close and empty) will
* be separated By white space Most of the work should be done in a private
* recursive method
*/
}
public class InorderIterator implements Iterator {
// An iterator that returns data in the tree in an in order pattern
// the implementation must use the parent pointer and must not use an
// additional data structure
public InorderIterator() {
}
public boolean hasNext() {
}
public String next() {
}
public void remove() {
// optional method not implemented
}
}
public class PostorderIterator implements Iterator {
// An iterator that returns data in the tree in a post order pattern
// This implementation must use a stack and must not use the parent pointer
// You must use Java’s stack class
public PostorderIterator() {
}
public boolean hasNext() {
}
public String next() {
}
public void remove() {
// optional method not implemented
}
}
public Iterator inorder() {
// return a new in order iterator object
}
public Iterator postorder() {
// return a new post order iterator object
}
public String toString() {
// returns the string representation of the tree using the in order format
// discussed in class. If the tree was created from a string use the
// the values of open, close and empty given to the constructor otherwise
// use (, ) and ! for open, close and empty respectively
// most of the work should be done in a recursive private method.
}
Stri open The tee wil beExplanation / Answer
# include <iostream>
# include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *L;
struct node *R;
}*roott;
/*
* Class Declaration
*/
class BST
{
public:
void find(int, node **, node **);
void insert(int);
void delte(int);
void caseA(node *,node *);
void caseB(node *,node *);
void caseC(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void view(node *, int);
BST()
{
roott = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
int ch, numbs;
BST B_SearchTree;
node *tempr;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on B_SearchTree"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Inorder Traversal"<<endl;
cout<<"4.Preorder Traversal"<<endl;
cout<<"5.Postorder Traversal"<<endl;
cout<<"6.view"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter your ch : ";
cin>>ch;
switch(ch)
{
case 1:
tempr = new node;
cout<<"Enter the number to be inserted : ";
cin>>tempr->info;
B_SearchTree.insert(roott, tempr);
case 2:
if (roott == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>numbs;
B_SearchTree.delte(numbs);
break;
case 3:
cout<<"Inorder Traversal of B_SearchTree:"<<endl;
B_SearchTree.inorder(roott);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal of B_SearchTree:"<<endl;
B_SearchTree.preorder(roott);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of B_SearchTree:"<<endl;
B_SearchTree.postorder(roott);
cout<<endl;
break;
case 6:
cout<<"view B_SearchTree:"<<endl;
B_SearchTree.view(roott,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong ch"<<endl;
}
}
}
/*
* Find Element in the Tree
*/
void B_SearchTree::find(int items, node **par, node **locl)
{
node *pointrr, *ptrsave;
if (roott == NULL)
{
*locl = NULL;
*par = NULL;
return;
}
if (items == roott->info)
{
*locl = roott;
*par = NULL;
return;
}
if (items < roott->info)
pointrr = roott->L;
else
pointrr = roott->R;
ptrsave = roott;
while (pointrr != NULL)
{
if (items == pointrr->info)
{
*locl = pointrr;
*par = ptrsave;
return;
}
ptrsave = pointrr;
if (items < pointrr->info)
pointrr = pointrr->L;
else
pointrr = pointrr->R;
}
*locl = NULL;
*par = ptrsave;
}
/*
* Inserting Element into the Tree
*/
void B_SearchTree::insert(node *tree, node *newnode)
{
if (roott == NULL)
{
roott = new node;
roott->info = newnode->info;
roott->L = NULL;
roott->R = NULL;
cout<<"roott Node is Added"<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->L != NULL)
{
insert(tree->L, newnode);
}
else
{
tree->L = newnode;
(tree->L)->L = NULL;
(tree->L)->R = NULL;
cout<<"Node Added To L"<<endl;
return;
}
}
else
{
if (tree->R != NULL)
{
insert(tree->R, newnode);
}
else
{
tree->R = newnode;
(tree->R)->L = NULL;
(tree->R)->R = NULL;
cout<<"Node Added To R"<<endl;
return;
}
}
}
/*
* Delete Element from the tree
*/
void B_SearchTree::delte(int items)
{
node *parent, *location;
if (roott == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
find(items, &parent, &location);
if (location == NULL)
{
cout<<"items not present in tree"<<endl;
return;
}
if (location->L == NULL && location->R == NULL)
caseA(parent, location);
if (location->L != NULL && location->R == NULL)
caseB(parent, location);
if (location->L == NULL && location->R != NULL)
caseB(parent, location);
if (location->L != NULL && location->R != NULL)
caseC(parent, location);
free(location);
}
/*
* Case A
*/
void B_SearchTree::caseA(node *par, node *locl )
{
if (par == NULL)
{
roott = NULL;
}
else
{
if (locl == par->L)
par->L = NULL;
else
par->R = NULL;
}
}
/*
* Case B
*/
void B_SearchTree::caseB(node *par, node *locl)
{
node *child;
if (locl->L != NULL)
child = locl->L;
else
child = locl->R;
if (par == NULL)
{
roott = child;
}
else
{
if (locl == par->L)
par->L = child;
else
par->R = child;
}
}
/*
* Case C
*/
void B_SearchTree::caseC(node *par, node *locl)
{
node *pointrr, *ptrsave, *suc, *parsuc;
ptrsave = locl;
pointrr = locl->R;
while (pointrr->L != NULL)
{
ptrsave = pointrr;
pointrr = pointrr->L;
}
suc = pointrr;
parsuc = ptrsave;
if (suc->L == NULL && suc->R == NULL)
caseA(parsuc, suc);
else
caseB(parsuc, suc);
if (par == NULL)
{
roott = suc;
}
else
{
if (locl == par->L)
par->L = suc;
else
par->R = suc;
}
suc->L = locl->L;
suc->R = locl->R;
}
/*
* Pre Order Traversal
*/
void B_SearchTree::preorder(node *pointrr)
{
if (roott == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (pointrr != NULL)
{
cout<<pointrr->info<<" ";
preorder(pointrr->L);
preorder(pointrr->R);
}
}
/*
* In Order Traversal
*/
void B_SearchTree::inorder(node *pointrr)
{
if (roott == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (pointrr != NULL)
{
inorder(pointrr->L);
cout<<pointrr->info<<" ";
inorder(pointrr->R);
}
}
/*
* Postorder Traversal
*/
void B_SearchTree::postorder(node *pointrr)
{
if (roott == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (pointrr != NULL)
{
postorder(pointrr->L);
postorder(pointrr->R);
cout<<pointrr->info<<" ";
}
}
void B_SearchTree::view(node *pointrr, int level)
{
int i;
if (pointrr != NULL)
{
view(pointrr->R, level+1);
cout<<endl;
if (pointrr == roott)
cout<<"roott->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<pointrr->info;
view(pointrr->L, level+1);
}
}