C++- Need to take this code and implement an AVL Tree using the existing code an
ID: 3916135 • Letter: C
Question
C++- Need to take this code and implement an AVL Tree using the existing code and
Also include a LevelOrder output function so that you can demonstrate that the AVL property is being maintained.
Thanks! the code is below:
#include <iostream>
#include <stack>
#include <ctime>
using namespace std;
template <class T>
class BST;
template <class T>
class BSTNode{
BSTNode<T>* left;
BSTNode<T>* right;
BSTNode<T>* parent;
T data;
public:
BSTNode(T newdata = T(), BSTNode<T>* newparent = nullptr, BSTNode<T>* newleft = nullptr, BSTNode<T>* newright = nullptr){
data = newdata; parent = newparent; left = newleft; right = newright;
}
friend class BST < T > ;
};
template <class T>
class BST{
BSTNode<T>* root;
int countOfNodes;
BSTNode<T>* recursiveCopy(const BSTNode<T>* rhs);
void printInOrder(BSTNode<T>* ptr);
public:
BST() :root(nullptr){}
BST(const BST<T>& rhs) :root(nullptr){ *this = rhs; }
~BST(){ clear(); }
bool isEmpty(){ return root == nullptr; }
void remove(const T& val){ remove(find(val)); }
bool findInTree(const T& val){ return find(val) != nullptr; }
void clear(){ while (!isEmpty()) remove(root); }
int size(){ return countOfNodes; }
BST<T>& operator=(const BST<T>& rhs);
void insert(const T&);
void remove(BSTNode<T>* ptr);
BSTNode<T>* find(const T&);
void printInOrder(){ if (root!=nullptr) printInOrder(root); }
};
template<class T>
void BST<T>::printInOrder(BSTNode<T>* ptr){
if (ptr->left != nullptr)
printInOrder(ptr->left);
cout << ptr->data<<endl;
if (ptr->right != nullptr)
printInOrder(ptr->right);
}
template <class T>
BSTNode<T>* BST<T>::find(const T& val){
BSTNode<T>* temp = root;
while (temp != nullptr && temp->data != val){
if (val < temp->data)
temp = temp->left;
else
temp = temp->right;
}
return temp;
}
template <class T>
void BST<T>::remove(BSTNode<T>* ptr){
if (ptr == nullptr) //someone asked me to remove a value that isnt in the tree... okay, done!
return;
if (countOfNodes == 1 && ptr == root){ //this is the last node
countOfNodes--;
delete root;
root = nullptr;
}
else if (ptr->left == nullptr && ptr->right == nullptr){ //no children, delete and update parent
BSTNode<T>* parent = ptr->parent;
if (parent != nullptr){ //update the parent's child pointer
if (ptr == parent->left)
parent->left = nullptr;
else
parent->right = nullptr;
}
delete ptr;
countOfNodes--;
}
else if (ptr->left == nullptr) { //node has a right child
BSTNode<T>* temp = ptr->right;
BSTNode<T>* parent = ptr->parent;
if (parent != nullptr){
if (ptr == parent->left)
parent->left = temp;
else
parent->right = temp;
}
else
root = temp;
temp->parent = parent;
delete ptr;
countOfNodes--;
}
else if (ptr->right == nullptr) { //node has a left child
BSTNode<T>* temp = ptr->left;
BSTNode<T>* parent = ptr->parent;
if (parent != nullptr){
if (ptr == parent->right)
parent->right = temp;
else
parent->left = temp;
}
else
root = temp;
temp->parent = parent;
delete ptr;
countOfNodes--;
}
else{ //the node has two children!!! - Bad
//Replace the data with the min of the right subtree
BSTNode<T>* temp = ptr->right;
while (temp->left != nullptr)
temp = temp->left;
ptr->data = temp->data;
remove(temp); //Recursion at its finest....ahhh!
}
}
template <class T>
void BST<T>::insert(const T& val){
countOfNodes++;
if (root == nullptr){//New node is the first on the tree
root = new BSTNode<T>(val);
return;
}
else{
BSTNode<T>* prev=root;
BSTNode<T>* temp=root;
while (temp != nullptr){
prev = temp;
if (val < temp->data)
temp = temp->left;
else
temp = temp->right;
}
//prev is a pointer to the node on which we will insert
if (val < prev->data){ //val will be a left child of prev
prev->left = new BSTNode<T>(val, prev);
}
else
prev->right = new BSTNode<T>(val, prev);
}
}
template <class T>
BSTNode<T>* BST<T>::recursiveCopy(const BSTNode<T>* rhs){
if (rhs == nullptr)
return nullptr;
BSTNode<T>* temp = new BSTNode<T>(rhs->data);
temp->left = recursiveCopy(rhs->left);
temp->right = recursiveCopy(rhs->right);
if (temp->left!=nullptr)
temp->left->parent = temp;
if (temp->right)
temp->right->parent = temp;
return temp;
}
template <class T>
BST<T>& BST<T>::operator=(const BST<T>& rhs){
if (this == &rhs)
return *this;
clear();
root = recursiveCopy(rhs.root);
countOfNodes = rhs.countOfNodes;
return *this;
}
int main(){
BST < int > t1;
srand(time(NULL));
for (int i = 0; i < 100; i++)
t1.insert(rand() % 1000);
BST<int> t2 = t1;
for (int i = 0; i < 10; i++)
t2.remove(rand() % 1000);
t2.printInOrder();
}
int stackDemo(){
stack<char> s;
string input = "int main(){cout<<"this is a test"; int x[5]; myfunc(x[0]);}";
for (int i=0; i < input.length(); i++){
char c = input[i];
if (c == '{' || c == '(' || c == '"' || c == '['){
if (c == '"' && s.top() == '"')
s.pop();
else
s.push(c);
}
else if (c == '}' || c == ')' || c == ']'){
if (c == '}' && s.top() == '{')
s.pop();
else if (c == ')' && s.top() == '(')
s.pop();
else if (c == ']' && s.top() == '[')
s.pop();
else{
cout << "ERROR! Found " << c << " but the top is " << s.top() << endl;
return 1;
}
}
}
if (!s.empty())
cout << "ERROR the stack is not empty but the string is done!" << endl;
else{
cout << "The code is balanced." << endl;
}
return 0;
}
Explanation / Answer
# include <iostream.h>
# include <stdlib.h>
# include <conio.h>
struct node
{
int element;
node *left;
node *right;
int height;
};
typedef struct node *nodeptr;
class bstree
{
public:
void insert(int,nodeptr &);
void del(int, nodeptr &);
int deletemin(nodeptr &);
void find(int,nodeptr &);
nodeptr findmin(nodeptr);
nodeptr findmax(nodeptr);
void copy(nodeptr &,nodeptr &);
void makeempty(nodeptr &);
nodeptr nodecopy(nodeptr &);
void preorder(nodeptr);
void inorder(nodeptr);
void postorder(nodeptr);
int bsheight(nodeptr);
nodeptr srl(nodeptr &);
nodeptr drl(nodeptr &);
nodeptr srr(nodeptr &);
nodeptr drr(nodeptr &);
int max(int,int);
int nonodes(nodeptr);
};
// Inserting a node
void bstree::insert(int x,nodeptr &p)
{
if (p == NULL)
{
p = new node;
p->element = x;
p->left=NULL;
p->right = NULL;
p->height=0;
if (p==NULL)
cout<<"Out of Space";
}
else
{
if (x<p->element)
{
insert(x,p->left);
if ((bsheight(p->left) - bsheight(p->right))==2)
{
if (x < p->left->element)
p=srl(p);
else
p = drl(p);
}
}
else if (x>p->element)
{
insert(x,p->right);
if ((bsheight(p->right) - bsheight(p->left))==2)
{
if (x > p->right->element)
p=srr(p);
else
p = drr(p);
}
}
else
cout<<"Element Exists";
}
int m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}
// Finding the Smallest
nodeptr bstree::findmin(nodeptr p)
{
if (p==NULL)
{
cout<<"
Empty Tree
";
return p;
}
else
{
while(p->left !=NULL)
p=p->left;
return p;
}
}
// Finding the Largest
nodeptr bstree::findmax(nodeptr p)
{
if (p==NULL)
{
cout<<"
Empty Tree
";
return p;
}
else
{
while(p->right !=NULL)
p=p->right;
return p;
}
}
// Finding an element
void bstree::find(int x,nodeptr &p)
{
if (p==NULL)
cout<<"
Element not found
";
else
if (x < p->element)
find(x,p->left);
else
if (x>p->element)
find(x,p->right);
else
cout<<"
Element found !
";
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1)
{
makeempty(p1);
p1 = nodecopy(p);
}
// Make a tree empty
void bstree::makeempty(nodeptr &p)
{
nodeptr d;
if (p != NULL)
{
makeempty(p->left);
makeempty(p->right);
d=p;
free(d);
p=NULL;
}
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p)
{
nodeptr temp;
if (p==NULL)
return p;
else
{
temp = new node;
temp->element = p->element;
temp->left = nodecopy(p->left);
temp->right = nodecopy(p->right);
return temp;
}
}
// Deleting a node
void bstree::del(int x,nodeptr &p)
{
nodeptr d;
if (p==NULL)
cout<<"Element not found
";
else if ( x < p->element)
del(x,p->left);
else if (x > p->element)
del(x,p->right);
else if ((p->left == NULL) && (p->right == NULL))
{
d=p;
free(d);
p=NULL;
cout<<"
Element deleted !
";
}
else if (p->left == NULL)
{
d=p;
free(d);
p=p->right;
cout<<"
Element deleted !
";
}
else if (p->right == NULL)
{
d=p;
p=p->left;
free(d);
cout<<"
Element deleted !
";
}
else
p->element = deletemin(p->right);
}
int bstree::deletemin(nodeptr &p)
{
int c;
cout<<"inside deltemin
";
if (p->left == NULL)
{
c=p->element;
p=p->right;
return c;
}
else
{
c=deletemin(p->left);
return c;
}
}
void bstree::preorder(nodeptr p)
{
if (p!=NULL)
{
cout<<p->element<<"-->";
preorder(p->left);
preorder(p->right);
}
}
// Inorder Printing
void bstree::inorder(nodeptr p)
{
if (p!=NULL)
{
inorder(p->left);
cout<<p->element<<"-->";
inorder(p->right);
}
}
// PostOrder Printing
void bstree::postorder(nodeptr p)
{
if (p!=NULL)
{
postorder(p->left);
postorder(p->right);
cout<<p->element<<"-->";
}
}
int bstree::max(int value1, int value2)
{
return ((value1 > value2) ? value1 : value2);
}
int bstree::bsheight(nodeptr p)
{
int t;
if (p == NULL)
return -1;
else
{
t = p->height;
return t;
}
}
nodeptr bstree:: srl(nodeptr &p1)
{
nodeptr p2;
p2 = p1->left;
p1->left = p2->right;
p2->right = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(bsheight(p2->left),p1->height) + 1;
return p2;
}
nodeptr bstree:: srr(nodeptr &p1)
{
nodeptr p2;
p2 = p1->right;
p1->right = p2->left;
p2->left = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(p1->height,bsheight(p2->right)) + 1;
return p2;
}
nodeptr bstree:: drl(nodeptr &p1)
{
p1->left=srr(p1->left);
return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1)
{
p1->right = srl(p1->right);
return srr(p1);
}
int bstree::nonodes(nodeptr p)
{
int count=0;
if (p!=NULL)
{
nonodes(p->left);
nonodes(p->right);
count++;
}
return count;
}
int main()
{
clrscr();
nodeptr root,root1,min,max;//,flag;
int a,choice,findele,delele,leftele,rightele,flag;
char ch='y';
bstree bst;
//system("clear");
root = NULL;
root1=NULL;
cout<<"
AVL Tree
";
cout<<" ========
";
do
{
cout<<"
1.Insertion
2.FindMin
";
cout<<"3.FindMax
4.Find
5.Copy
";
cout<<"6.Delete
7.Preorder
8.Inorder
";
cout<<" 9.Postorder
10.height
";
cout<<"
Enter the choice:
";
cin>>choice;
switch(choice)
{
case 1:
cout<<"
New node's value ?
";
cin>>a;
bst.insert(a,root);
break;
case 2:
if (root !=NULL)
{
min=bst.findmin(root);
cout<<"
Min element : "<<min->element;
}
break;
case 3:
if (root !=NULL)
{
max=bst.findmax(root);
cout<<"
Max element : "<<max->element;
}
break;
case 4:
cout<<"
Search node :
";
cin>>findele;
if (root != NULL)
bst.find(findele,root);
break;
case 5:
bst.copy(root,root1);
bst.inorder(root1);
break;
case 6:
cout<<"Delete Node ?
";
cin>>delele;
bst.del(delele,root);
bst.inorder(root);
break;
case 7:
cout<<"
Preorder Printing... :
";
bst.preorder(root);
break;
case 8:
cout<<"
Inorder Printing.... :
";
bst.inorder(root);
break;
case 9:
cout<<"
Postorder Printing... :
";
bst.postorder(root);
break;
case 10:
cout<<"
Height and Depth is
";
cout<<bst.bsheight(root);
cout<<"No. of nodes:- "<<bst.nonodes(root);
break;
}
cout<<"
Do u want to continue (y/n) ?
";
cin>>ch;
}while(ch=='y');
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.