Binary tree Implementation on C++ – Algorithm and Source Code

Algorithm for inserting a node in a binary tree

Loading...
1. Declare and initialize necessary variables
2. Read the data item to be inserted in the tree say x.
3. Create a new node with its left and right pointers to null.
4. Assign data x to info field of new node.
5. If (tree == NULL)
then tree = address of new node
else if (x < tree -> info)
if(tree->left == NULL)
then tree->left = new node
else
tree = tree->left
repeat step 5.
else if(x>tree->info)
if(tree->right == NULL)
then tree->right = new node
else
tree = tree->right
repeat step 5
else if(x == tree->info)
print “Duplicated data” and exit
6. For next insertion, goto step 5.

Deletion Algorithm

1. Declare and initialize the necessary variable
2. Read data to be deleted say x.
3. Find the enode where data exist.
if node is not found
print “node not found” and exit
4. If the node has no subtree
* then assign the father node’s pointer with null that points to the node
* delete the node that contains data item.
5. If the node has to be deleted has only one subtree
* move its son up, to take its place
* delete the node that contains data item
6. If the node has to be deleted has two subtrees
* set the information of node to be deleted by the information of leftmost node of rightmost subtree of the node to be deleted
7. For next deletion, goto step 2

Source Code for Insertion , Deletion, inorder, preorder and postorder tree traversal

The code is also available on GitHub.

#include <iostream>
#include <cstdlib>
using namespace std;
struct tree {
    int info;
    tree *Left, *Right;
};
tree* root;
class Binary_tree {
public:
    Binary_tree();
    void insert1(int);
    tree* insert2(tree*, tree*);
    void Delete(int);
    void pretrav(tree*);
    void intrav(tree*);
    void posttrav(tree*);
};
Binary_tree::Binary_tree()
{
    root = NULL;
}
tree* Binary_tree::insert2(tree* temp, tree* newnode)
{
    if (temp == NULL) {
        temp = newnode;
    }
    else if (temp->info < newnode->info) {
        insert2(temp->Right, newnode);
        if (temp->Right == NULL)
            temp->Right = newnode;
    }
    else {
        insert2(temp->Left, newnode);
        if (temp->Left == NULL)
            temp->Left = newnode;
    }
    return temp;
}
void Binary_tree::insert1(int n)
{
    tree *temp = root, *newnode;
    newnode = new tree;
    newnode->Left = NULL;
    newnode->Right = NULL;
    newnode->info = n;
    root = insert2(temp, newnode);
}
void Binary_tree::pretrav(tree* t = root)
{
    if (root == NULL) {
        cout << "Nothing to display";
    }
    else if (t != NULL) {
        cout << t->info << " ";
        pretrav(t->Left);
        pretrav(t->Right);
    }
}
void Binary_tree::intrav(tree* t = root)
{
    if (root == NULL) {
        cout << "Nothing to display";
    }
    else if (t != NULL) {
        intrav(t->Left);
        cout << t->info << " ";
        intrav(t->Right);
    }
}
void Binary_tree::posttrav(tree* t = root)
{
    if (root == NULL) {
        cout << "Nothing to display";
    }
    else if (t != NULL) {
        posttrav(t->Left);
        posttrav(t->Right);
        cout << t->info << " ";
    }
}
void Binary_tree::Delete(int key)
{
    tree *temp = root, *parent = root, *marker;
    if (temp == NULL)
        cout << "The tree is empty" << endl;
    else {
        while (temp != NULL && temp->info != key) {
            parent = temp;
            if (temp->info < key) {
                temp = temp->Right;
            }
            else {
                temp = temp->Left;
            }
        }
    }
    marker = temp;
    if (temp == NULL)
        cout << "No node present";
    else if (temp == root) {
        if (temp->Right == NULL && temp->Left == NULL) {
            root = NULL;
        }
        else if (temp->Left == NULL) {
            root = temp->Right;
        }
        else if (temp->Right == NULL) {
            root = temp->Left;
        }
        else {
            tree* temp1;
            temp1 = temp->Right;
            while (temp1->Left != NULL) {
                temp = temp1;
                temp1 = temp1->Left;
            }
            if (temp1 != temp->Right) {
                temp->Left = temp1->Right;
                temp1->Right = root->Right;
            }
            temp1->Left = root->Left;
            root = temp1;
        }
    }
    else {
        if (temp->Right == NULL && temp->Left == NULL) {
            if (parent->Right == temp)
                parent->Right = NULL;
            else
                parent->Left = NULL;
        }
        else if (temp->Left == NULL) {
            if (parent->Right == temp)
                parent->Right = temp->Right;
            else
                parent->Left = temp->Right;
        }
        else if (temp->Right == NULL) {
            if (parent->Right == temp)
                parent->Right = temp->Left;
            else
                parent->Left = temp->Left;
        }
        else {
            tree* temp1;
            parent = temp;
            temp1 = temp->Right;
            while (temp1->Left != NULL) {
                parent = temp1;
                temp1 = temp1->Left;
            }
            if (temp1 != temp->Right) {
                temp->Left = temp1->Right;
                temp1->Right = parent->Right;
            }
            temp1->Left = parent->Left;
            parent = temp1;
        }
    }
    delete marker;
}
int main()
{
    Binary_tree bt;
    int choice, n, key;
    while (1) {
        cout << "\n\t1. Insert\n\t2. Delete\n\t3. Preorder Traversal\n\t4. Inorder Treversal\n\t5. Postorder Traversal\n\t6. Exit" << endl;
        cout << "Enter your choice: ";
        cin >> choice;
        switch (choice) {
        case 1:
            cout << "Enter item: ";
            cin >> n;
            bt.insert1(n);
            break;
        case 2:
            cout << "Enter element to delete: ";
            cin >> key;
            bt.Delete(key);
            break;
        case 3:
            cout << endl;
            bt.pretrav();
            break;
        case 4:
            cout << endl;
            bt.intrav();
            break;
        case 5:
            cout << endl;
            bt.posttrav();
            break;
        case 6:
            exit(0);
        }
    }
    return 0;
}

For the updated and more detailed explanation of the Binary Search Tree click here.

Loading...
SHARE Binary tree Implementation on C++ – Algorithm and Source Code

You may also like...

4 Responses

  1. Napster says:

    the program given here is not working ????
    anybody help me…..

  2. Napster says:

    the program given here is not working?????????
    plz anybody give some guidlines

  3. Unknown says:

    the pgm is length but useful one sir….ur great

Leave a Reply

Your email address will not be published. Required fields are marked *

Share