Data Structures - 8

by

AIM: Write C Programs to implement Binary Search Tree.


Code:

#include <stdio.h >

#include <stdlib.h>

 

  struct node

  {

    int info;

    struct node * lchild;

    struct node * rchild;

  }*root;

 

void find(int item, struct node **par, struct node **loc)

{

  struct node *ptr, *ptrsave;

 

  if (root == NULL)

  {

    *loc = NULL;

    *par = NULL;

    return;

  }

 

  if (item == root->info)

  {

    *loc = root;

    *par = NULL;

    return;

  }

 

  if (item < root->info)

    ptr = root->lchild;

  else

    ptr = root->rchild;

  ptrsave = root;

 

  while (ptr != NULL)

  {

    if (item == ptr->info)

    {*loc = ptr;

      *par = ptrsave;

      return;

    }

 

    ptrsave = ptr;

    if (item < ptr->info)

      ptr = ptr->lchild;

    else

      ptr = ptr->rchild;

  }

 

  *loc = NULL;

  *par = ptrsave;

}

 

void insert(int item)

{

  struct node *tmp, *parent, *location;

  find(item, &parent, &location);

  if (location != NULL)

  {

    printf("Item already present");

    return;

  }

 

  tmp = (struct node *) malloc(sizeof(struct node));

  tmp->info = item;

  tmp->lchild = NULL;

  tmp->rchild = NULL;

 

  if (parent == NULL)

    root = tmp;

  else

  if (item < parent->info)

    parent->lchild = tmp;

  else

    parent->rchild = tmp;

}

 

void case_a(struct node *par, struct node *loc)

{

  if (par == NULL)

    root = NULL;

  else

  if (loc == par->lchild)

    par->lchild = NULL;

  else

    par->rchild = NULL;

}

 

void case_b(struct node *par, struct node *loc)

{

  struct node * child;

  if (loc->lchild != NULL)

    child = loc->lchild;

  else

    child = loc->rchild;

 

  if (par == NULL)

    root = child;

  else

  if (loc == par->lchild)

    par->lchild = child;

  else

    par->rchild = child;

}

 

void case_c(struct node *par, struct node *loc)

{

  struct node *ptr, *ptrsave, *suc, *parsuc;

 

  ptrsave = loc;

  ptr = loc->rchild;

  while (ptr->lchild != NULL)

  {

    ptrsave = ptr;

    ptr = ptr->lchild;

  }

 

  suc = ptr;

  parsuc = ptrsave;

 

  if (suc->lchild == NULL && suc->rchild == NULL)

    case_a(parsuc, suc);

  else

    case_b(parsuc, suc);

 

  if (par == NULL)

    root = suc;

  else

  if (loc == par->lchild)

    par->lchild = suc;

  else

    par->rchild = suc;

 

  suc->lchild = loc->lchild;

  suc->rchild = loc->rchild;

}

 

int del(int item)

{

  struct node *parent, *location;

  if (root == NULL)

  {

    printf("Tree empty");

    return 0;

  }

 

  find(item, &parent, &location);

  if (location == NULL)

  {

    printf("Item not present in tree");

    return 0;

  }

 

  if (location->lchild == NULL && location->rchild == NULL)

    case_a(parent, location);

  if (location->lchild != NULL && location->rchild == NULL)

    case_b(parent, location);

  if (location->lchild == NULL && location->rchild != NULL)

    case_b(parent, location);

  if (location->lchild != NULL && location->rchild != NULL)

    case_c(parent, location);

  free(location);

}

 

int preorder(struct node *ptr)

{

  if (root == NULL)

  {

    printf("Tree is empty");

    return 0;

  }

 

  if (ptr != NULL)

  {

    printf("%d  ", ptr->info);

    preorder(ptr->lchild);

    preorder(ptr->rchild);

  }

}

 

void inorder(struct node *ptr)

{

  if (root == NULL)

  {

    printf("Tree is empty");

    return;

  }

 

  if (ptr != NULL)

  {

    inorder(ptr->lchild);

    printf("%d  ", ptr->info);

    inorder(ptr->rchild);

  }

}

 

void postorder(struct node *ptr)

{

  if (root == NULL)

  {

    printf("Tree is empty");

    return;

  }

 

  if (ptr != NULL)

  {

    postorder(ptr->lchild);

    postorder(ptr->rchild);

    printf("%d  ", ptr->info);

  }

}

 

void display(struct node *ptr, int level)

{

  int i;

  if (ptr != NULL)

  {

    display(ptr->rchild, level + 1);

    printf("\n");

    for (i = 0; i < level; i++)

      printf("    ");

    printf("%d", ptr->info);

    display(ptr->lchild, level + 1);

  }

}

 

main()

{

  int choice, num;

  root = NULL;

  while (1)

  {

    printf("\n-------------------------------\n");

    printf("1.Insert\n");

    printf("2.Delete\n");

    printf("3.Inorder Traversal\n");

    printf("4.Preorder Traversal\n");

    printf("5.Postorder Traversal\n");

    printf("6.Display\n");

    printf("7.Quit\n");

    printf("Enter your choice : ");

    scanf("%d", &choice);

 

    switch (choice)

    {

      case 1:

        printf("Enter the number to be inserted : ");

        scanf("%d", &num);

        insert(num);

        break;

      case 2:

        printf("Enter the number to be deleted : ");

        scanf("%d", &num);

        del(num);

        break;

      case 3:

        inorder(root);

        break;

      case 4:

        preorder(root);

        break;

      case 5:

        postorder(root);

        break;

      case 6:

        display(root, 1);

        break;

      case 7:

        break;

      default:

        printf("Wrong choice\n");

    }

  }

}

Output

Comments

Post a Comment

Popular posts from this blog

Computer Architecture and Organization - 4

by
Image
Aim:  To implement various 4-bit arithmetic Micro-operations           using arithmetic unit.   Theory Arithmetic micro operation of the form L:   R A  ( R A + R B ) refers to two data items contained in R A and R B input to a parallel adder with the result being stored back in R A (Fig.). Loading      of the result in R A is subject to the availability   of the control   signal designated as L   (that   is   load control of R A ) . Note that adder being a combinational logic, the adder output is available after a delay of the associated combinational circuit. Input to adder may be also controlled by providing AND word gates on the data paths from R A and R B to the adder under the control signal C (Fig.). the control signals `C' and 2's complement are at logic `0' for add operation.   The subtract micro operation L:   R A  ( R A - R B ) in 2's comp...
Read more

Design and Analysis of Algorithms - 2

by
Image
Implement functions to print n th Fibonacci number using iteration and recursive method. Compare the performance of two methods by counting number of steps executed on various inputs. Also draw a comparative chart. Code:   #include<stdio.h>   int count_ite=0; int count_rec=0; void febo_ite(int ); int febo_rec(int );   int main() {     int n,ans;     printf("Enter position of number: ");     scanf("%d",&n);     febo_ite(n);     ans=febo_rec(n);     printf("Using Recursion: %d th number is = %d\n",n,ans);     printf("No of Steps= %d\n\n",count_rec); }   void febo_ite(int n) {     count_ite++;     int next,i, first=0,second=1;     count_ite++;     if(n==0)     {         count_ite++;  ...
Read more

Design and Analysis of Algorithms - 6

by
Image
Implement program for randomized version of quick sort and compare its performance with normal version of quick sort using steps count on various number of inputs.   Code: #include<stdio.h> #include<stdlib.h> #include<time.h>   int count=0; int r_count=0; void quick_sort(int a[],int start,int n) {     int i,j,pivot,temp;     count++;     if(start<n)         {             count++;             pivot=start;             count++;             i=start;             count++;             j=n;     ...
Read more

Design and Analysis of Algorithms - 1

by
Image
Implement a function for each of following problems and count the  number of steps executed/Time taken by each function on various  inputs and write complexity of each function. Also draw a  comparative chart. In each of the following function N will be passed  by user.                     1. To calculate sum of 1 to N number using loop.                     2. To calculate sum of 1 to N number using equation.                     3. To calculate sum of 1 to N numbers using recursion. Code:   #include <stdio.h> int count_loop=0; int count_rec=0; int count_eq=0;   int sum_loop(int n) {     int i,sum=0;     count_loop++;     for(i=1;i<=n;i++)     {         count_loop++; ...
Read more

Artificial Intelligence - 7

by
Image
  AIM: Write a program to build Multi-layer Perceptron to implement any Boolean functions as mentioned below without using any python packages. AND, OR, XOR, XNOR, NOR, NAND, NOT x1, NOT x2, NULL, IDENTITY, INHIBITION ( 𝑥 1 ∧ ¬ 𝑥 2), INHIBITION ( 𝑥 2 ∧ ¬ 𝑥 1), TRANSFER x1, TRANSFER x2, IMPLICATION ( 𝑥 1 ∨ ¬ 𝑥 2), IMPLICATION ( 𝑥 2 ∨ ¬ 𝑥 1)   Program: class  perceptronNeuron:      def   __init__ ( self ,  x ,  w ,  w0 ):         l = [ww  for  ww  in  x]         l.insert( 0 ,  1 )          self .x = l          self .y =  0         l = [ww  for  ww  in  w]         l.insert( 0 ,...
Read more