This C++ Program demonstrates the implementation of Weight Balanced Tree.
Here is source code of the C++ Program to demonstrate the implementation of Weight Balanced Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C++ Program to Implement Weight Balanced Tree
*/
#include <iostream>
#include <cstdlib>
#define MAX_VALUE 65536
using namespace std;
/* Class WBTNode */
class WBTNode
{
public:
WBTNode *left;
WBTNode *right;
int weight, element;
/* Constructor */
WBTNode(int theElement, int wt, WBTNode *lt, WBTNode *rt)
{
element = theElement;
left = lt;
right = rt;
weight = wt;
}
/* Constructor */
WBTNode(int theElement, int wt)
{
WBTNode(theElement, wt, NULL, NULL);
}
};
WBTNode *nullNode;
/* Class WeightBalancedTree */
class WeightBalancedTree
{
private:
WBTNode *root;
public:
/* Constructor */
WeightBalancedTree()
{
root = nullNode;
}
/* Function to check if tree is empty */
bool isEmpty()
{
return root == nullNode;
}
/* Make the tree logically empty */
void makeEmpty()
{
root = nullNode;
}
/* Functions to insert data */
void insert(int x, int wt)
{
root = insert(x, wt, root);
}
WBTNode *insert(int x, int wt, WBTNode *t)
{
if (t == nullNode)
t = new WBTNode(x, wt, nullNode, nullNode);
else if (x < t->element)
{
t->left = insert (x, wt, t->left);
if (t->left->weight < t->weight)
t = rotateWithLeftChild (t);
}
else if (x > t->element)
{
t->right = insert (x, wt, t->right);
if (t->right->weight < t->weight)
t = rotateWithRightChild (t);
}
return t;
}
/* Functions to delete data */
void remove(int x)
{
if (isEmpty())
cout<<"Tree Empty"<<endl;
else if (search(x) == false)
cout<<x <<" is not present"<<endl;
else
{
root = remove (x, root);
cout<<x <<" deleted from the tree"<<endl;
}
}
WBTNode *remove(int x, WBTNode *t)
{
if (t != nullNode)
{
if (x < t->element)
t->left = remove (x, t->left);
else if (x > t->element)
t->right = remove (x, t->right);
else
{
if (t->left->weight == 0)
t->left->weight = MAX_VALUE;
if (t->right->weight == 0)
t->right->weight = MAX_VALUE;
if (t->left->weight < t->right->weight)
{
t = rotateWithLeftChild(t);
}
else
{
t = rotateWithRightChild(t);
}
if (t != nullNode)
t = remove( x, t );
else
t->left = nullNode;
}
}
return t;
}
/* Rotate tree node with left child */
WBTNode *rotateWithLeftChild (WBTNode *k2)
{
WBTNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
return k1;
}
/* Rotate tree node with right child */
WBTNode *rotateWithRightChild (WBTNode *k1)
{
WBTNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
return k2;
}
/* Functions to count number of nodes */
int countNodes()
{
return countNodes(root);
}
int countNodes(WBTNode *r)
{
if (r == nullNode)
return 0;
else
{
int l = 1;
l += countNodes(r->left);
l += countNodes(r->right);
return l;
}
}
/* Functions to search for an element */
bool search(int val)
{
return search(root, val);
}
bool search(WBTNode *r, int val)
{
bool found = false;
while ((r != nullNode) && !found)
{
int rval = r->element;
if (val < rval)
r = r->left;
else if (val > rval)
r = r->right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function for inorder traversal */
void inorder()
{
inorder(root);
}
void inorder(WBTNode *r)
{
if (r != nullNode)
{
inorder(r->left);
cout<<r->element<<" ";
inorder(r->right);
}
}
/* Function for preorder traversal */
void preorder()
{
preorder(root);
}
void preorder(WBTNode *r)
{
if (r != nullNode)
{
cout<<r->element<<" ";
preorder(r->left);
preorder(r->right);
}
}
/* Function for postorder traversal */
void postorder()
{
postorder(root);
}
void postorder(WBTNode *r)
{
if (r != nullNode)
{
postorder(r->left);
postorder(r->right);
cout<<r->element<<" ";
}
}
};
/* Main Contains Menu */
int main()
{
nullNode = new WBTNode(0, MAX_VALUE);
nullNode->left = nullNode->right = nullNode;
WeightBalancedTree wbt;
cout<<"Weight Balanced Tree Test\n";
int choice, val, wt;
char ch;
/* Perform tree operations */
do
{
cout<<"\nWeight Balanced Tree Operations\n";
cout<<"1. Insert "<<endl;
cout<<"2. Delete"<<endl;
cout<<"3. Search"<<endl;
cout<<"4. Count nodes"<<endl;
cout<<"5. Check empty"<<endl;
cout<<"6. Clear"<<endl;
cout<<"Enter Your Choice: ";
cin>>choice;
switch (choice)
{
case 1 :
cout<<"Enter integer element to insert: ";
cin>>val;
cout<<"Enter weight of the element in int: ";
cin>>wt;
wbt.insert(val, wt);
break;
case 2 :
cout<<"Enter integer element to delete: ";
cin>>val;
wbt.remove(val);
break;
case 3 :
cout<<"Enter integer element to search: ";
cin>>val;
if (wbt.search(val) == true)
cout<<"Element "<<val<<" found in the tree"<<endl;
else
cout<<"Element "<<val<<" not found in the tree"<<endl;
break;
case 4 :
cout<<"Nodes = "<< wbt.countNodes();
break;
case 5 :
if (wbt.isEmpty() == true)
cout<<"Tree is empty"<<endl;
else
cout<<"Tree is non-empty"<<endl;
break;
case 6 :
cout<<"\nTree Cleared";
wbt.makeEmpty();
break;
default :
cout<<"Wrong Entry \n ";
break;
}
/* Display tree */
cout<<"\nPost order : ";
wbt.postorder();
cout<<"\nPre order : ";
wbt.preorder();
cout<<"\nIn order : ";
wbt.inorder();
cout<<"\nDo you want to continue (Type y or n) \n";
cin>>ch;
}
while (ch == 'Y'|| ch == 'y');
return 0;
}
$ g++ weight_balanced_tree.cpp $ a.out Weight Balanced Tree Test Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 1 Enter integer element to insert: 24 Enter weight of the element in int: 28 Post order : 24 Pre order : 24 In order : 24 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 1 Enter integer element to insert: 5 Enter weight of the element in int: 6 Post order : 24 5 Pre order : 5 24 In order : 5 24 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 1 Enter integer element to insert: 63 Enter weight of the element in int: 94 Post order : 63 24 5 Pre order : 5 24 63 In order : 5 24 63 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 1 Enter integer element to insert: 14 Enter weight of the element in int: 6 Post order : 63 24 14 5 Pre order : 5 14 24 63 In order : 5 14 24 63 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 1 Enter integer element to insert: 1 Enter weight of the element in int: 17 Post order : 1 63 24 14 5 Pre order : 5 1 14 24 63 In order : 1 5 14 24 63 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 1 Enter integer element to insert: 70 Enter weight of the element in int: 91 Post order : 1 63 70 24 14 5 Pre order : 5 1 14 24 70 63 In order : 1 5 14 24 63 70 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 2 Enter integer element to delete: 24 24 deleted from the tree Post order : 1 63 70 14 5 Pre order : 5 1 14 70 63 In order : 1 5 14 63 70 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 3 Enter integer element to search: 1 Element 1 found in the tree Post order : 1 63 70 14 5 Pre order : 5 1 14 70 63 In order : 1 5 14 63 70 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 4 Nodes = 5 Post order : 1 63 70 14 5 Pre order : 5 1 14 70 63 In order : 1 5 14 63 70 Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 6 Tree Cleared Post order : Pre order : In order : Do you want to continue (Type y or n) y Weight Balanced Tree Operations 1. Insert 2. Delete 3. Search 4. Count nodes 5. Check empty 6. Clear Enter Your Choice: 5 Tree is empty Post order : Pre order : In order : Do you want to continue (Type y or n) n ------------------ (program exited with code: 1) Press return to continue
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
If you find any mistake above, kindly email to [email protected]Related Posts:
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Programming Books
- Practice Design & Analysis of Algorithms MCQ
- Practice Programming MCQs