Showing posts with label binary search tree. Show all posts
Showing posts with label binary search tree. Show all posts

Friday 30 September 2016

Binary Search Tree: Deleting node

Binary Search Tree: Deleting node


#include<stdio.h>
#include<stdlib.h>
struct BST
{
            int data;
            struct BST *lchild,  *rchild;
};
typedef struct BST * NODE;

NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode)
{
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}
void inorder(NODE root)
{
            if(root != NULL)
            {
                        inorder(root->lchild);
                        printf("%d ", root->data);
                        inorder(root->rchild);
            }
}

NODE delete_item(NODE root, int item)
{
            NODE cur, parent, succ, psucc, child;
            if(root == NULL)
            {
                        printf("\nTree is empty. Nothing to delete");
                        return NULL;
            }
           
                /*Obtain the node to be deleted and its parent*/
            parent = NULL;
            cur = root;
            while(cur!=NULL)
            {
                        if(item == cur->data)
                                                break;
                        parent = cur;
                        if(item < cur->data)
                                                cur = cur->lchild;
                        else if(item > cur->data)
                                                cur = cur->rchild;
            }
            if(cur == NULL)
            {
                        printf("\nItem not found");
                        return root;
            }
            /*If item is found then delete it: node to be deleted is cur*/
            if(cur->lchild ==NULL)             /*if cur node's left subtree is empty , obtain non empty right subtree */
                        child = cur->rchild;
            else  if(cur->rchild ==NULL)     /*if cur node's left subtree is empty , obtain non empty right subtree */
                        child = cur->lchild;
            else
            {
                        /*Find the inorder successor and its parent*/
                        psucc = cur;
                        succ = cur->rchild;

                                /*Find the minimum node (inorder successor) in the right subtree of cur node*/
                        while(succ->lchild != NULL)                 
                        {
                                                psucc = succ;
                                                succ = succ->lchild;
                        }
                        if(cur == psucc)
                                    succ->lchild  = cur->lchild;
                        else
                        {
                                    succ->lchild = cur->lchild;       /* attach left of node to be deleted(cur) to the left of successor */
                                    psucc->lchild = succ->rchild;     /* attach right of successor to the left of parent of successor*/
                                    succ->rchild = cur->rchild;    /*attach right of node to be deleted(cur) to the right of successor*/
                        }
                        child = succ;
                        printf("\nsuccessor data = %d", child->data);
            }          
            if(parent == NULL)              /*if parent does not exist return child as root*/
                        return child;

            if(parent->lchild  == cur)
                         parent->lchild = child;
             else
                        parent->rchild = child;
            free(cur);
            return root;
}

void main()
{
            int val, i,n, item;
            NODE root = NULL, newnode, del;
            printf("\nEnter the number of elements: ");
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }

             printf("\nInorder display before deletion: ");
            inorder(root);
            printf("\nEnter the Item to be deleted: ");
            scanf("%d", &item);
            del = delete_item(root, item);
            printf("\nInorder display after deletion: ");
            inorder(del);
}
Output1:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39    45        54        55        56        61        78        80
Enter the Item to be deleted: 78
Inorder display after deletion: 39       45        54        55        56        61        80

Output2:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39    45        54        55        56        61        78        80
Enter the Item to be deleted: 54
Inorder display after deletion: 39       45        55        56        61        78        80

Output3:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39    45        54        55        56        61        78        80
Enter the Item to be deleted: 45
Inorder display after deletion: 39       54        55        56        61        78        80


Output4:
Enter the number of elements: 9
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 65
Enter The node value: 80

Inorder display before deletion: 39    45        54        55        56        61        65        78        80
Enter the Item to be deleted: 56
successor data = 61

Inorder display after deletion: 39       45        54        55        61        65        78        80

Binary Search Tree: Count number of Leaf nodes

Count number of leaf nodes in Binary Search Tree



#include<stdio.h>
#include<stdlib.h>
struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;
int leaf=0;

NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode)
{
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}

int leaf_nodes(NODE root)
{
            if(root == NULL)
                        return 0;
            if(root->lchild == NULL && root->rchild==NULL)
                        leaf++;
            leaf_nodes(root->lchild);
            leaf_nodes(root->rchild);
            return leaf;
}

void main()
{
            int val, i,n, ln;
            NODE root = NULL, newnode;
            printf("\nEnter the number of elements: ");
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }

            ln = leaf_nodes(root);
            printf("\nTotal number of leaf nodes is: %d", ln);
}

Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
Total number of leaf nodes is: 4

Binary Search Tree: Count number of nodes

Count number of nodes in Binary Search Tree


#include<stdio.h>
#include<stdlib.h>
struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;
int count = 0;

NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode)
{
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}

int count_nodes(NODE root)
{
            if(root == NULL)
                        return 0;
            count++;
            count_nodes(root->lchild);
            count_nodes(root->rchild);
            return count;
}

void main()
{
            int val, i,n, cn, ln;
            NODE root = NULL, newnode;
            printf("\nEnter the number of elements: ");
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }
            cn = count_nodes(root);
            printf("\nTotal number of nodes in the tree is: %d", cn);
}

Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
 Total number of nodes in the tree is: 9