You are currently viewing Easy Mirror Image Construct of Binary Search Tree

Easy Mirror Image Construct of Binary Search Tree

Mirror Image Construct of Binary Search Tree

This code is for showing Mirror Image construct and Level Order Traversal of a Binary search tree. In this code first the tree is created as per the position of the nodes. As we all know in Binary Search Tree, Left child contain lesser value than parent and Right child contain greater value than parent.

In this code you have to create a Binary Search Tree. After that perform any traversal then perform the mirror image construct code. After performing Mirror Image construct again perform any traversal technique, you will see the mirroring affect of the initially created binary search tree.

For Such more codes click here and for video tutorial click here.

				
					#include<stdio.h>

#include<stdlib.h>


typedef struct BinarySearchTree {
  struct BinarySearchTree * left;
  struct BinarySearchTree * right;
  int val;
}
bst;

typedef struct Queue {
  bst * val;
  struct Queue * next;
}
qu;

void enqueu(qu ** , bst * );
bst * dequeu(qu ** );
int isempty(qu * );

bst * create(bst * , int);
void inorder(bst * );
void preorder(bst * );
void postorder(bst * );
void levelorder(bst * );
void mirimg(bst * );

int main() {
  bst * root = NULL;
  int g, ch;
  while (1) {
    printf("\n\n 1) Insert\n 2) Preorder traversal\n 3) Inorder traversal\n 4) Postorder traversal\n 5) Level Order Traversal\n 6) Construct Mirro Image of the tree\n 7) Exit");
    printf("\n\n Enter your choice : ");
    scanf("%d", & ch);
    switch (ch) {
    case 1:
      printf("\nInsert value for the tree: ");
      scanf("%d", & g);
      root = create(root, g);
      break;
    case 2:
      printf("\nValues in Preorder Traversal :");
      preorder(root);
      break;
    case 3:
      printf("\nValues in Inorder Traversal : ");
      inorder(root);
      break;
    case 4:
      printf("\nValues in Postorder Traversal :");
      postorder(root);
      break;
    case 5:
      printf("\nValues in Level order Traversal :");
      levelorder(root);
      break;
    case 6:
      printf("\nMirror Image of the tree constructed , perform any traversal to check the mirror image...... ");
      mirimg(root);
      break;
    case 7:
      exit(0);
    }
  }
}

bst * create(bst * root, int p) {
  bst * temp, * pre, * ptr;

  temp = (bst * ) malloc(sizeof(bst));
  temp -> val = p;
  temp -> right = temp -> left = NULL;
  if (root == NULL) {
    root = temp;
  } else {
    ptr = root;
    while (ptr != NULL) {
      pre = ptr;
      if (ptr -> val > p)
        ptr = ptr -> left;
      else
        ptr = ptr -> right;
    }
    if (pre -> val > p)
      pre -> left = temp;
    else
      pre -> right = temp;
  }
  return root;
}

void preorder(bst * root) {
  if (root != NULL) {
    printf("%d,", root -> val);
    preorder(root -> left);
    preorder(root -> right);
  }
}

void inorder(bst * root) {
  if (root != NULL) {
    inorder(root -> left);
    printf("%d,", root -> val);
    inorder(root -> right);
  }
}

void postorder(bst * root) {
  if (root != NULL) {
    postorder(root -> left);
    postorder(root -> right);
    printf("%d,", root -> val);
  }
}

void levelorder(bst * root) {
  qu * p = NULL;
  bst * ptr;
  enqueu( & p, root);
  while (!isempty(p)) {
    ptr = dequeu( & p);
    printf("%d,", ptr -> val);
    if (ptr -> left != NULL)
      enqueu( & p, ptr -> left);
    if (ptr -> right != NULL)
      enqueu( & p, ptr -> right);
  }
}

void mirimg(bst * root) {
  qu * p = NULL;
  bst * ptr, * temp;
  enqueu( & p, root);
  while (!isempty(p)) {
    ptr = dequeu( & p);
    if (ptr -> left != NULL)
      enqueu( & p, ptr -> left);
    if (ptr -> right != NULL)
      enqueu( & p, ptr -> right);
    temp = ptr -> right;
    ptr -> right = ptr -> left;
    ptr -> left = temp;
  }
}

void enqueu(qu ** p, bst * ptr1) {
  qu * temp, * ptr;
  temp = (qu * ) malloc(sizeof(qu));
  temp -> val = ptr1;
  temp -> next = NULL;
  if ( * p == NULL)
    *
    p = temp;
  else {
    ptr = * p;
    while (ptr -> next != NULL)
      ptr = ptr -> next;

    ptr -> next = temp;
  }
}

bst * dequeu(qu ** p) {
  bst * ptr;
  ptr = ( * p) -> val;
  * p = ( * p) -> next;
  return ptr;
}

int isempty(qu * p) {
  if (p == NULL)
    return 1;
  else
    return 0;
}
Run

Leave a Reply