You are to create a class named BinaryTree. This will simulate a balanced and or
ID: 3910626 • Letter: Y
Question
You are to create a class named BinaryTree. This will simulate a balanced and ordered binary tree. You also need to create a TreeNode class, which defines the data contained in each node of the tree. In this case, it is an integer. Remember that the node also needs a way to track back to its parent, as well as its left and right children. For the purpose of this assignment, each node should also contain an indication of its level within the tree. For the TreeNode, the constructor only needs to obtain the integer value held in the node. The class should have modifiers to allow its placement on the tree; in other words, the ability to connect it to its parent and connect child nodes. Also have a modifier to change the level. The BinaryTree class constructor will not receive any input. The class will have three methods: add, remove, and find: ? Add(int) receives an integer value, creates the new TreeNode, and adds it to the appropriate location on the tree, keeping it balanced. Use the algorithm available in the Web Links for assistance. ? Remove(int) locates the desired value and removes it from the tree, balancing it afterwards. If the node does not exist, it does nothing. Use the algorithm available in the Web Links for assistance. ? Find(int) receives the integer value desired, and returns the TreeNode of that item. It returns NULL if the item is not located. Note you may need some other Private methods (like rotate()) in order to keep the tree in balance.
Explanation / Answer
#include<iostream.h>
using namespace std;
class node{
public:
int data;
btree left,right,p;
node(int d){
data=d;
}
};
class btree{
public:
node insert(node b);
int height(node b);
int diff(node t);
void find(int ,node);
void deletemin(node n);
void delet(int x,node b);
};
int btree::height(node *temp)
{
int h = 0;
if (temp != NULL)
{
int lheight = height (temp->left);
int rheight = height (temp->right);
int max_height = max (lheight, rheight);
h = max_height + 1;
}
return h;
}
int btree::diff(node *temp)
{
int lheight = height (temp->left);
int rheight = height (temp->right);
int b_factor= lheight - rheight;
return b_factor;
}
node *btree::rr_rotation(node *parent)
{
node *temp;
temp = parent->right;
parent->right = temp->left;
temp->left = parent;
return temp;
}
node *btree::ll_rotation(node *parent)
{
node *temp;
temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp;
}
node *btree::lr_rotation(node *parent)
{
node *temp;
temp = parent->left;
parent->left = rr_rotation (temp);
return ll_rotation (parent);
}
void btree::find(int x,node p1)
{
if (p1==NULL)
cout<<"
Element not found
";
else
if (x < p1->element)
find(x,p1->left);
else
if (x>p1->element)
find(x,p1->right);
else
cout<<"
Element found !
";
}
node *btree::rl_rotation(node *parent)
{
node *temp;
temp = parent->right;
parent->right = ll_rotation (temp);
return rr_rotation (parent);
}
node *btree::balance(node *temp)
{
int bal_factor = diff (temp);
if (bal_factor > 1)
{
if (diff (temp->left) > 0)
temp = ll_rotation (temp);
else
temp = lr_rotation (temp);
}
else if (bal_factor < -1)
{
if (diff (temp->right) > 0)
temp = rl_rotation (temp);
else
temp = rr_rotation (temp);
}
return temp;
}
void btree::delet(int x,node p)
{
node d;
if (p1==NULL)
cout<<"Element not found
";
else if ( x < p1->element)
del(x,p1->left);
else if (x > p1->element)
del(x,p->right);
else if ((p1->left == NULL) && (p1->right == NULL))
{
d=p1;
free(d);
p1=NULL;
cout<<"
Element deleted !
";
}
else if (p1->left == NULL)
{
d=p1;
free(d);
p1=p1->right;
cout<<"
Element deleted !
";
}
else if (p1->right == NULL)
{
d=p1;
p1=p1->left;
free(d);
cout<<"
Element deleted !
";
}
else
p1->element = deletemin(p1->right);
}
int btree::deletemin(node p1)
{
int c;
cout<<"inside deltemin
";
if (p1->left == NULL)
{
c=p1->element;
p1=p1->right;
return c;
}
else
{
c=deletemin(p1->left);
return c;
}
}
node *btree::insert(node *root, int value)
{
if (root == NULL)
{
root = new node;
root->data = value;
root->left = NULL;
root->right = NULL;
return root;
}
else if (value < root->data)
{
root->left = insert(root->left, value);
root = balance (root);
}
else if (value >= root->data)
{
root->right = insert(root->right, value);
root = balance (root);
}
return root;
}
int main(){
node n(3);
btree b;
b.insert(n);
b.delet(n);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.