Binary Search Tree: Search for key element

Binary Search Tree:  Search for key element

#include<stdio.h>

#include<stdlib.h>

struct BST

{

            int data;

            struct BST *lchild;

            struct BST *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 search(NODE root, int key)

{

            NODE cur;

            if(root == NULL)

            {

                        printf("\nBST is empty.");

                        return;

            }

            cur = root;

            while (cur != NULL)

            {

                        if (cur->data == key)

                        {

                                    printf("\nKey element %d is present in BST", cur->data);

                                    return;

                        }

                        if (key < cur->data)

                                    cur = cur->lchild;

                        else

                                    cur = cur->rchild;

            }

            printf("\nKey element %d is not found in the BST", key);

}

void main()

{

            int val, i, n, key;

            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);

            }

           

             /*Search for a given key in BST*/

            printf("\nEnter Element to be searched: ");

            scanf("%d", &key);

            search(root, key);

}

Case 1:

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

Enter Element to be searched: 66

Key element 66 is not found in the BST

Case 2:

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

Enter Element to be searched: 5

Key element 5 is present in BST

Circular Linked List with Header Node: Delete from End

Circular Linked List with Header Node: Delete from end

#include<stdio.h>

#include<stdlib.h>

struct node

{

            int data;

            struct node *link;

};

typedef struct node* NODE;

int count = 0;              /* To count no of nodes in the list and put it into header node */

NODE getnode()

{

            NODE x;

            x = (NODE)malloc(sizeof(struct node));

            return x;

}

NODE insert_at_end(NODE head, int item)

{

            NODE temp, cur;

            temp = getnode();

            temp->data = item;

            cur = head->link;

            while(cur->link!=head)

            {

                        cur = cur->link;

            }

            cur->link = temp;

            temp->link = head;

            head->data = ++count;

            return head;

}

NODE delete_at_end(NODE head)

{

            NODE prev, cur;

            if(head->link == head)

            {

                        printf("\nCLL is empty");

                        return head;

            }

            prev = head;

            cur = head->link;

            while(cur->link!=head)

            {

                        prev = cur;

                        cur = cur->link;

            }

            prev->link = cur->link;

            printf("\nNode with item %d is deleted", cur->data);

            free(cur);

            head->data = --count;

            return head;

}

void display(NODE head)

{

            NODE temp;

            if(head->link == head)

            {

                        printf("\nList is empty.");

                        return;

            }

            printf("\nContents of the CLL:\n");

            printf("\nNo of nodes in the CLL is %d\n", head->data);

            temp = head->link;

            while(temp!=head)

            {

                        printf("|%d|%d| --> ",temp->data, temp->link);

                        temp = temp->link;

            }

}

void main()

{

            int ch, item;

            NODE head;

            head = getnode();

            head->data = 0;

            head->link = head;                  /*Empty header node*/

            while(1)

            {

                        printf("\n~~MENU~~");

                        printf("\n1:Insert at End \n2.Delete at End \n3:Display \n4:Exit \n");

                        printf("Enter the choice: ");

                        scanf("%d",&ch);

                        switch(ch)

                        {

                                    case 1: printf("\nEnter the item to be inserted : ");

                                                scanf("%d", &item);

                                                head = insert_at_end(head, item);

                                                break;

                                    case 2: head = delete_at_end(head);

                                                break;

                                    case 3: display(head);

                                                break;

                                    case 4: exit(0);

                        }

            }

}

Output:

~~MENU~~

1:Insert at End

2.Delete at End

3:Display

4:Exit

Enter the choice: 1

Enter the item to be inserted : 11

~~MENU~~

1:Insert at End

2.Delete at End

3:Display

4:Exit

Enter the choice: 1

Enter the item to be inserted : 12

~~MENU~~

1:Insert at End

2.Delete at End

3:Display

4:Exit

Enter the choice: 1

Enter the item to be inserted : 14

~~MENU~~

1:Insert at End

2.Delete at End

3:Display

4:Exit

Enter the choice: 3

Contents of the CLL:

No of nodes in the CLL is 3

|11|5256304| --> |12|5256320| --> |14|5248880| -->

~~MENU~~

1:Insert at End

2.Delete at End

3:Display

4:Exit

Enter the choice: 2

Node with item 14 is deleted

~~MENU~~

1:Insert at End

2.Delete at End

3:Display

4:Exit

Enter the choice: 3

Contents of the CLL:

No of nodes in the CLL is 2

|11|5256304| --> |12|5248880| -->

~~MENU~~

1:Insert at End

2.Delete at End

3:Display

4:Exit

Enter the choice: 4

Circular Linked List with Header Node: Insert at End

Circular Linked List with Header Node: Insert at end

#include<stdio.h>

#include<stdlib.h>

struct node

{

            int data;

            struct node *link;

};

typedef struct node* NODE;

int count = 0;         /* To count no of nodes in the list and put it into header node */

NODE getnode()

{

            NODE x;

            x = (NODE)malloc(sizeof(struct node));

            return x;

}

NODE insert_at_end(NODE head, int item)

{

            NODE temp, cur;

            temp = getnode();

            temp->data = item;

            cur = head->link;

            while(cur->link!=head)

            {

                        cur = cur->link;

            }

            cur->link = temp;

            temp->link = head;

            head->data = ++count;

            return head;

}

void display(NODE head)

{

            NODE temp;

            if(head->link == head)

            {

                        printf("\nList is empty.");

                        return;

            }

            printf("\nContents of the CLL:\n");

            printf("\nNo of nodes in the CLL is %d\n", head->data);

            temp = head->link;

            while(temp!=head)

            {

                        printf("|%d|%d| --> ",temp->data,temp->link);

                        temp = temp->link;

            }

}

void main()

{

            int ch, item;

            NODE head;

            head = getnode();

            head->data = 0;

            head->link = head;      /*Empty header node*/

            while(1)

            {

                        printf("\n~~MENU~~");

                        printf("\n1:Insert At End \n2:Display \n3:Exit \n");

                        printf("Enter the choice: ");

                        scanf("%d", &ch);

                        switch(ch)

                        {

                                    case 1: printf("\nEnter the item to be inserted : ");

                                                scanf("%d", &item);

                                                head = insert_at_end(head, item);

                                                break;

                                    case 2: display(head);

                                                break;

                                    case 3: exit(0);

                        }

            }

}

Output:

~~MENU~~

1:Insert At End

2:Display

3:Exit

Enter the choice: 1

Enter the item to be inserted : 11

~~MENU~~

1:Insert At End

2:Display

3:Exit

Enter the choice: 1

Enter the item to be inserted : 12

~~MENU~~

1:Insert At End

2:Display

3:Exit

Enter the choice: 1

Enter the item to be inserted : 14

~~MENU~~

1:Insert At End

2:Display

3:Exit

Enter the choice: 2

Contents of the CLL:

No of nodes in the CLL is 3

|11|4863088| --> |12|4863104| --> |14|4855664| -->