Week 10 programs based on operations on Tree

Source Code

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

struct tree {
  int data;
  struct tree * left;
  struct tree * right;
};
struct tree * insert(struct tree * , int);
void inorder(struct tree * );
void postorder(struct tree * );
void preorder(struct tree * );
struct tree * delet(struct tree * , int);
int main(void) {
  struct tree * root;
  int choice, item, item_no;
  root = NULL;
  do {
    do {
      printf("\\n \\t 1. Insert in Binary Tree ");
      printf("\\n\\t 2. Delete from Binary Tree ");
      printf("\\n\\t 3. Inorder traversal of Binary tree");
      printf("\\n\\t 4. Postorder traversal of Binary tree");
      printf("\\n\\t 5. Preorder traversal of Binary tree");
      printf("\\n\\t 6. Exit ");
      printf("\\n\\t Enter choice : ");
      scanf(" %d", & choice);
      if (choice < 1 || choice > 7)
        printf("\\n Invalid choice - try again");
    }
    while (choice < 1 || choice > 7);
    switch (choice) {
    case 1:
      printf("\\n Enter new element: ");
      scanf("%d", & item);
      root = insert(root, item);
      printf("\\n root is %d", root -> data);
      printf("\\n Inorder traversal of binary tree is : ");
      inorder(root);
      break;
    case 2:
      printf("\\n Enter the element to be deleted : ");
      scanf(" %d", & item_no);
      root = delet(root, item_no);
      inorder(root);
      break;
    case 3:
      printf("\\n Inorder traversal of binary tree is : ");
      inorder(root);
      break;
    case 4:
      printf("\\n Postorder traversal of binary tree is : ");
      postorder(root);
      break;
    case 5:
      printf("\\n Preorder traversal of binary tree is : ");
      preorder(root);
      break;
    default:
      printf("\\n End of program ");
    }

  }
  while (choice != 7);
  return (0);
}
struct tree * insert(struct tree * root, int x) {
  if (!root) {
    root = (struct tree * ) malloc(sizeof(struct tree));
    root -> data = x;
    root -> left = NULL;
    root -> right = NULL;
    return (root);
  }
  if (root -> data > x)
    root -> left = insert(root -> left, x);
  else {
    if (root -> data < x)
      root -> right = insert(root -> right, x);
  }
  return (root);
}
void inorder(struct tree * root) {
  if (root != NULL) {
    inorder(root -> left);
    printf(" %d", root -> data);
    inorder(root -> right);
  }
  return;
}
void postorder(struct tree * root) {
  if (root != NULL) {
    postorder(root -> left);
    postorder(root -> right);
    printf(" %d", root -> data);
  }
  return;
}
void preorder(struct tree * root) {
  if (root != NULL) {
    printf(" %d", root -> data);
    preorder(root -> left);
    preorder(root -> right);
  }
  return;
}
struct tree * delet(struct tree * ptr, int x) {
  struct tree * p1, * p2;
  if (!ptr) {
    printf("\\n Node not found ");
    return (ptr);
  } else {
    if (ptr -> data <
      x) {
      ptr -> right = delet(ptr -> right,
        x);

    } else if (ptr -> data >
      x) {
      ptr -> left = delet(ptr -> left,
        x);
      return ptr;
    } else {
      if (ptr -> data ==
        x) {
        if (ptr -> left == ptr -> right) {
          free
            (ptr);
          return (NULL);
        } else if (ptr -> left == NULL) {
          p1
            = ptr -> right;
          free
            (ptr);
          return p1;
        } else if (ptr -> right == NULL) {
          p1
            = ptr -> left;
          free
            (ptr);
          return p1;
        } else {
          p1
            = ptr -> right;
          p2
            = ptr -> right;
          while (p1 -> left != NULL)
            p1 = p1 -> left;
          p1 -> left = ptr -> left;
          free
            (ptr);
          return p2;

        }

      }

    }

  }
  return (ptr);
}