Code:
#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"<
else if (search(x) == false)
cout<
else
{
root = remove (x, root);
cout<
}
}
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<
inorder(r->right);
}
}
/* Function for preorder traversal */
void preorder()
{
preorder(root);
}
void preorder(WBTNode *r)
{
if (r != nullNode)
{
cout<
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<
}
}
};
/* 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 "<
cout<<"2. Delete"<
cout<<"3. Search"<
cout<<"4. Count nodes"<
cout<<"5. Check empty"<
cout<<"6. Clear"<
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 "<
else
cout<<"Element "<
break;
case 4 :
cout<<"Nodes = "<< wbt.countNodes();
break;
case 5 :
if (wbt.isEmpty() == true)
cout<<"Tree is empty"<
else
cout<<"Tree is non-empty"<
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;
}
Output:
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
More C++ Programs:
