Add the following methods to the class BinaryTree shown below: public T get(int
ID: 3568250 • Letter: A
Question
Add the following methods to the class BinaryTree shown below: public T get(int i) public void add(int i, T element) public T remove(int i) All these methods use the inorder traversal of the tree. Feel free to use helper methods and/or extra fields. Here are the description of what the methods do. --------------------------------------------------------------------------------- get(i) returns the element of the i-th node of the inorder traversal of the tree. If i is outside the range it throws a NOSuchElementException. For example if the inorder traversal of the tree t is a, b, c, d, e, f, g, h, i, j, k t.get(4) returns e. ---------------------------------------------------------------------------------- public void add(int i, T element) inserts element in the tree such that it is the i-th item in the inorder traversal. Throw an index out of bounds exception if i is out of bounds and increase size if the insertion is successful. For example if the inorder traversal of the tree t is a, b, c, d, e, f, g, h, i, j, k after the call t.add(5, x); the inorder traversal of t is a, b, c, d, e, x, f, g, h, i, j, k ----------------------------------------------------------------------------------- public T remove(int i) removes the i-th item of the tree. Throw a no such element exception if i is out of range. Don't forget to decrease the size if the remove is successful. For example if the inorder traversal of the tree t is a, b, c, d, e, f, g, h, i, j, k the call t.remove(5); returns f and the inorder traversal of t is a, b, c, d, e, g, h, i, j, k -------------------------------------------------------------------------------------- Here is the class BinaryTree.java import java.util.NoSuchElementException; public class BinaryTree<T> { /** Creates an empty binary tree */ public BinaryTree() { root = null; } // create a binary tree with a given root value public BinaryTree( T rootItem) { root = new BinaryNode( rootItem, null, null); size = 1; } // @return the root of the tree public BinaryNode<T> getRoot() { return root; } // @return the size of the tree public int size() { return size; } // @return the the height of the tree public int height() { return BinaryNode.height(root); } // print the tree in preorder public void printPreOrder() { if (root != null) root.printPreOrder(); } // print the tree in postorder public void printPostOrder() { if (root != null) root.printPostOrder(); } // print the tree in inorder public void printInOrder() { if (root != null) root.printInOrder(); } // empty the tree public void makeEmpty() { root = null; size = 0; } // check if the tree is empty public boolean isEmpty() { return root == null; } // forms a new tree from rootItem t1 and t2 // does not allow t1 and t2 to be the same public void merge(T rootItem, BinaryTree<T> t1, BinaryTree<T> t2) { if (t1.root == t2.root && t1.root != null) throw new IllegalArgumentException(); // allocate new node root = new BinaryNode<T>(rootItem, t1.root, t2.root); size = t1.size() + t2.size() + 1; // ensures that every node is in one tree if (this != t1) t1.root = null; if ( this != t2) t2.root = null; } private BinaryNode<T> root; private int size = 0; }
Explanation / Answer
#include<iostream.h>
#include<conio.h>
class BSTNode
{
int data;
BSTNode *p,*lc,*rc;
public :
BSTNode()
{
data=0;
p=NULL;
lc=NULL;
rc=NULL;
}
BSTNode(int k)
{
data=k;
p=NULL;
lc=NULL;
rc=NULL;
}
void setData(int k){data=k;}
int getData(){return data;}
void setP(BSTNode *n){p=n;}
BSTNode* getP(){return p;}
void setLc(BSTNode *n){lc=n;}
BSTNode* getLc(){return lc;}
void setRc(BSTNode *n){rc=n;}
BSTNode* getRc(){return rc;}
};
class BST
{
BSTNode *root;
public :
BST();
BSTNode* getRoot();
void addNode(BSTNode *n);
void preorder(BSTNode *ptr);
void inorder(BSTNode *ptr);
void postorder(BSTNode *ptr);
BSTNode* search(int data);
BSTNode* treeMin(BSTNode *ptr);
BSTNode* treeMax(BSTNode *ptr);
BSTNode* sucessor(BSTNode *ptr);
BSTNode* deleteNode(BSTNode *z);
};
BSTNode* BST :: deleteNode(BSTNode *z)
{
BSTNode *y,*x;
if(z->getLc()==NULL || z->getRc()==NULL)
y=z;
else
y=sucessor(z);
if(y->getLc()!=NULL)
x=y->getLc();
else
x=y->getRc();
if(x!=NULL)
x->setP(y);
if(y==root)
root=x;
else
{
x->setP(y->getP());
if(y==y->getP()->getLc())
y->getP()->setLc(x);
else
y->getP()->setRc(x);
}
if(y!=z)
z->setData(y->getData());
return y;
}
BST :: BST()
{
root=NULL;
}
BSTNode* BST :: getRoot()
{
return root;
}
void BST :: addNode(BSTNode *n)
{
int data;
cout<<" Enter the data : ";
cin>>data;
n->setData(data);
BSTNode *ptr=root;
BSTNode *parent;
if(ptr==NULL)
{
root=n;
}
else
{
while(ptr!=NULL)
{
parent=ptr;
if(n->getData()<ptr->getData())
ptr=ptr->getLc();
else
ptr=ptr->getRc();
}
n->setP(parent);
if(parent->getData()>n->getData())
parent->setLc(n);
else
parent->setRc(n);
}
}
BSTNode* BST :: treeMin(BSTNode *ptr)
{
while(ptr->getLc()!=NULL)
ptr=ptr->getLc();
return ptr;
}
BSTNode* BST :: treeMax(BSTNode *ptr)
{
while(ptr->getRc()!=NULL)
ptr=ptr->getRc();
return ptr;
}
void BST :: preorder(BSTNode *ptr)
{
if(ptr!=NULL)
{
cout<<ptr->getData()<<" ";
preorder(ptr->getLc());
preorder(ptr->getRc());
}
}
void BST :: inorder (BSTNode *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->getLc());
cout<<ptr->getData()<<" ";
inorder(ptr->getRc());
}
}
void BST :: postorder(BSTNode *ptr)
{
if(ptr!=NULL)
{
postorder(ptr->getLc());
postorder(ptr->getRc());
cout<<ptr->getData()<<" ";
}
}
BSTNode* BST :: search(int data)
{
BSTNode *ptr=root;
while(ptr!=NULL && ptr->getData()!=data)
{
if(data<ptr->getData())
ptr=ptr->getLc();
else
ptr=ptr->getRc();
}
return ptr;
}
BSTNode* BST :: sucessor(BSTNode *ptr)
{
if(ptr!=NULL && ptr->getRc()!=NULL)
return treeMin(ptr->getRc());
BSTNode *parent=ptr->getP();
while(parent!=NULL && parent->getRc()==ptr)
{
ptr=parent;
parent=parent->getP();
}
return parent;
}
void main()
{
int choice;
BST b;
clrscr();
do
{
clrscr();
cout<<" 1 ---Enter the node";
cout<<" 2 ---PreOrder 3 ---InOrder 4 ---PostOrder";
cout<<" 5 ---Search";
cout<<" 6 ---Tree min 7 ---Tree max";
cout<<" 8 ---sucessor";
cout<<" 10---Delete a node";
cout<<" 11---Exit";
cout<<" Enter the choice : ";
cin>>choice;
if(choice==1)
{
BSTNode *node=new BSTNode();
b.addNode(node);
}
if(choice==2)
{
cout<<" PreOrder of Graph : ";
b.preorder(b.getRoot());
getch();
}
if(choice==3)
{
cout<<" InOrder of Graph : ";
b.inorder(b.getRoot());
getch();
}
if(choice==4)
{
cout<<" PostOrder of Graph : ";
b.postorder(b.getRoot());
getch();
}
if(choice==5)
{
int data;
BSTNode *search;
cout<<" Enter the searching element : ";
cin>>data;
search=b.search(data);
if(search->getData()==data)
cout<<" Data found";
else
cout<<" Data not found";
getch();
}
if(choice==6)
{
cout<<" Tree Minimum : "<<b.treeMin(b.getRoot())->getData();
getch();
}
if(choice==7)
{
cout<<" Tree Maximum : "<<b.treeMax(b.getRoot())->getData();
getch();
}
if(choice==8)
{
int data;
BSTNode *search;
BSTNode *suc;
cout<<" Enter the data : ";
cin>>data;
search=b.search(data);
if(search->getData()==data)
{
suc=b.sucessor(search);
cout<<" Sucessor of "<<data <<" : " <<suc->getData();
}
else
{
cout<<" Data not found";
}
getch();
}
if(choice==10)
{
int data;
cout<<"Enter the deleting node : ";
cin>>data;
BSTNode *search=b.search(data);
if(search->getData()!=data)
cout<<" Data not found ";
else
{
BSTNode *del=b.deleteNode(search);
cout<<"Node "<<del->getData()<<" is deleated.";
}
getch();
}
}while(choice!=11);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.