Showing posts with label Module 4. Show all posts
Showing posts with label Module 4. Show all posts

Friday 30 September 2016

Binary Search Tree Creation and Traversals

Binary Search Tree Creation and Level-order, Inorder, Preorder, Postorder Traversals


#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 inorder(NODE root)
{
            if(root != NULL)
            {
                        inorder(root->lchild);
                        printf("%d ", root->data);
                        inorder(root->rchild);
            }
}

void preorder(NODE root)
{
            if (root != NULL)
            {
                        printf("%d ", root->data);
                        preorder(root->lchild);
                        preorder(root->rchild);
            }
}

void postorder(NODE root)
{
            if (root != NULL)
            {
                        postorder(root->lchild);
                        postorder(root->rchild);
                        printf("%d ", root->data);
            }
}

void levelorder(NODE root)
{
            NODE q[40],cur;
            int front=0,rear=-1;
            q[++rear]=root;
            while(front<=rear)
            {
                        cur = q[front++];
                        printf("%d ",cur->data);
                        if(cur->lchild != NULL)
                                    q[++rear] = cur->lchild;
                        if(cur->rchild != NULL)
                                    q[++rear] = cur->rchild;
            }
}
void main()
{
            int val, i,n;
            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);
            }
            if (root == NULL)
                        printf("\nTree Is Not Created");
            else
            {
                        printf("\nThe Levelorder display : ");
                        levelorder(root);
                        printf("\nThe Inorder display : ");
                        inorder(root);
                        printf("\nThe Preorder display : ");
                        preorder(root);
                        printf("\nThe Postorder display : ");
                        postorder(root);
            }
}


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

The Levelorder display :        6          5          9          2          8          15        7          14        24
The Inorder display :             2          5          6          7          8          9          14        15        24
The Preorder display :           6          5          2          9          8          7          15        14        24
The Postorder display :         2          5          7          8          14        24        15        9          6
Posted by at No comments:
Labels: ,

Lab Program 10 Binary Search Tree 15CSL38 Data Structures in C Lab

Lab Program 10:

Design, Develop and Implement a menu driven Program in C for the following operations on Binary Search Tree (BST) of Integers
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate messaged.
d. Exit











#include<stdio.h>
#include<stdlib.h> 

struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;

NODE create()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            printf("\nEnter The value: ");
            scanf("%d", &temp->data);


            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode);
void inorder(NODE root);
void preorder(NODE root);
void postorder(NODE root);
void search(NODE root);

void insert(NODE root, NODE newnode)
{
    /*Note: if newnode->data ==  root->data it will be skipped. No duplicate nodes are allowed */
           
            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;
            }
            printf("\nEnter Element to be searched: ");
            scanf("%d", &key);
            cur = root;
            while (cur != NULL)
            {
                        if (cur->data == key)
                        {
                                    printf("\nKey element is present in BST");
                                    return;
                        }
                        if (key < cur->data)
                                    cur = cur->lchild;
                        else
                                    cur = cur->rchild;
            }
            printf("\nKey element is not found in the BST");
}

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

void preorder(NODE root)
{
            if (root != NULL)
            {
                        printf("%d ", root->data);
                        preorder(root->lchild);
                        preorder(root->rchild);
            }
}

void postorder(NODE root)
{
            if (root != NULL)
            {
                        postorder(root->lchild);
                        postorder(root->rchild);
                        printf("%d ", root->data);
            }
}


void main()
{
            int ch, key, val, i, n;
            NODE root = NULL, newnode;
            while(1)
            {
                        printf("\n~~~~BST MENU~~~~");
                        printf("\n1.Create a BST");
                        printf("\n2.Search");
                        printf("\n3.BST Traversals: ");
                        printf("\n4.Exit");
                        printf("\nEnter your choice: ");
                        scanf("%d", &ch);
                        switch(ch)
                        {
                                    case 1:             printf("\nEnter the number of elements: ");
                                                            scanf("%d", &n);
                                                            for(i=1;i<=n;i++)
                                                            {
                                                                        newnode = create();
                                                                        if (root == NULL)
                                                                                    root = newnode;
                                                                        else
                                                                                    insert(root, newnode);
                                                            }
                                                            break;
                                     case 2:             if (root == NULL)
                                                                       printf("\nTree Is Not Created");
                                                            else
                                                            {
                                                                        printf("\nThe Preorder display : ");
                                                                        preorder(root);
                                                                        printf("\nThe Inorder display : ");
                                                                        inorder(root);
                                                                        printf("\nThe Postorder display : ");
                                                                        postorder(root);
                                                            }

                                                            break;
                                     case 3:            search(root);
                                                            break;
                                     
                                    case 4:     exit(0);
                        }
            }
}

Output:
~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 1

Enter the number of elements: 12
Enter The value: 6
Enter The value: 9
Enter The value: 5
Enter The value: 2
Enter The value: 8
Enter The value: 15
Enter The value: 24
Enter The value: 14
Enter The value: 7
Enter The value: 8
Enter The value: 5
Enter The value: 2

~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 3

The Preorder display:           6          5          2          9          8          7          15        14        24
The Inorder display:             2          5          6          7          8          9          14        15        24
The Postorder display:         2          5          7          8          14        24        15        9          6

~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 2

Enter Element to be searched: 66
Key element is not found in the BST

~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 2

Enter Element to be searched: 14
Key element is present in BST

~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 4

Posted by at No comments:
Labels: , ,
Subscribe to: Posts (Atom)