C++ Program to Implement Weight Balanced Tree

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.

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]

« Prev - C++ Program to Implement Threaded Binary Tree

» Next - C++ Program to Implement Pagoda

Related Posts:

Practice Computer Science MCQs
Apply for Computer Science Internship
Check Programming Books
Practice Design & Analysis of Algorithms MCQ
Practice Programming MCQs

Recommended Articles: