Binary Search Trees Implementation using C program

Data Structures using C Language / Binary Search Trees Implementation using C program

Program

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

struct node {
  int data; 
  struct node *rightchild; 
  struct node *leftchild; 
};

struct node* newnode(int x) {
  struct node *temp;
  temp = malloc(sizeof(struct node));
  temp -> data = x;
  temp -> leftchild = NULL;
  temp -> rightchild = NULL;
  return temp;
}

struct node* search(struct node * root, int x) {
  if (root == NULL || root -> data == x) 
    return root;
  else if (x > root -> data) 
    return search(root -> rightchild, x);
  else 
    return search(root -> leftchild, x);
}

struct node* insert(struct node * root, int x) {
  if (root == NULL)
    return newnode(x);
  else if (x > root -> data) 
    root -> rightchild = insert(root -> rightchild, x);
  else 
    root -> leftchild = insert(root -> leftchild, x);
  return root;
}

struct node* findminimum(struct node * root) {
  if (root == NULL)
    return NULL;
  else if (root -> leftchild != NULL) 
    return findminimum(root -> leftchild); 
  return root;
}

struct node* delete(struct node * root, int x) {
  if (root == NULL)
    return NULL;
  if (x > root -> data)
    root -> rightchild = delete(root -> rightchild, x);
  else if (x < root -> data)
    root -> leftchild = delete(root -> leftchild, x);
  else {
    if (root -> leftchild == NULL && root -> rightchild == NULL) {
      free(root);
      return NULL;
    }

else if (root -> leftchild == NULL || root -> rightchild == NULL) {
      struct node *temp;
      if (root -> leftchild == NULL)
        temp = root -> rightchild;
      else
        temp = root -> leftchild;
      free(root);
      return temp;
    }

else {
      struct node *temp = findminimum(root -> rightchild);
      root -> data = temp -> data;
      root -> rightchild = delete(root -> rightchild, temp -> data);
    }
  }
  return root;
}

void inorder(struct node *root) {
  if (root != NULL)
  {
    inorder(root -> leftchild); 
    printf(" %d ", root -> data); 
    inorder(root -> rightchild); 
  }
}

int main() {
  struct node *root;
  root = newnode(20);
  insert(root, 5);
  insert(root, 1);
  insert(root, 15);
  insert(root, 9);
  insert(root, 7);
  insert(root, 12);
  insert(root, 30);
  insert(root, 25);
  insert(root, 40);
  insert(root, 45);
  insert(root, 42);

inorder(root);
  printf("\n");

root = delete(root, 1);
  root = delete(root, 40);
  root = delete(root, 45);
  root = delete(root, 9);

inorder(root);
  printf("\n");
  return 0;
}

Output

1  5  7  9  12  15  20  25  30  40  42  45 
5  7  12  15  20  25  30  42

Home Back