Perform Tree Operations – insert, traversal, preorder,post order and in order


Levels of difficulty: / perform operation:


C Program

#include<stdio.h>
#include<alloc.h>
#include<conio.h>
#include<stdio.h>
struct tree {
	int info;
	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);
struct tree *search(struct tree *);
int main(void) {
	struct tree *root;
	int choice, item,item_no;
	root = NULL;
	clrscr();
	/* rear  = 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. Search and replace ");
			printf("\n\t 7. 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->info);
			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;
			case 6:
				  printf("\n Search and replace operation in binary tree ");
			root=search(root);
			break;
			default:
				   printf("\n End of program ");
		}
		/* end of switch */
	}
	while(choice !=7);
	return(0);
}
struct tree *insert(struct tree *root, int x) {
	if(!root) {
		root=(struct tree*)malloc(sizeof(struct tree));
		root->info = x;
		root->left = NULL;
		root->right = NULL;
		return(root);
	}
	if(root->info > x)
	     root->left = insert(root->left,x); else {
		if(root->info < x)
			root->right = insert(root->right,x);
	}
	return(root);
}
void inorder(struct tree *root) {
	if(root != NULL) {
		inorder(root->left);
		printf(" %d",root->info);
		inorder(root->right);
	}
	return;
}
void postorder(struct tree *root) {
	if(root != NULL) {
		postorder(root->left);
		postorder(root->right);
		printf(" %d",root->info);
	}
	return;
}
void preorder(struct tree *root) {
	if(root != NULL) {
		printf(" %d",root->info);
		preorder(root->left);
		preorder(root->right);
	}
	return;
}
/* FUNCTION TO DELETE A NODE FROM A BINARY TREE */
struct tree *delet(struct tree *ptr,int x) {
	struct tree *p1,*p2;
	if(!ptr) {
		printf("\n Node not found ");
		return(ptr);
	} else {
		if(ptr->info < x) {
			ptr->right = delet(ptr->right,x);
			/*return(ptr);*/
		} else if (ptr->info >x) {
			ptr->left=delet(ptr->left,x);
			return ptr;
		} else                     
		/* no. 2 else */ {
			if(ptr->info == x)    
			/* no. 2 if */ {
				if(ptr->left == ptr->right) 
				/*i.e., a leaf node*/ {
					free(ptr);
					return(NULL);
				} else if(ptr->left==NULL)  
				/* a right subtree */ {
					p1=ptr->right;
					free(ptr);
					return p1;
				} else if(ptr->right==NULL)   
				/* a left subtree */ {
					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;
				}
			}
			/*end of no. 2 if */
		}
		/* end of no. 2 else */
		/* check which path to search for a given no. */
	}
	return(ptr);
}
/* function to search and replace an element in the binary tree */
struct tree *search(struct tree *root) {
	int no,i,ino;
	struct tree *ptr;
	ptr=root;
	printf("\n Enter the element to be searched :");
	scanf(" %d",&no);
	fflush(stdin);
	while(ptr) {
		if(no>ptr->info)
		     ptr=ptr->right; else if(no<ptr->info)
		     ptr=ptr->left; else
		     break;
	}
	if(ptr) {
		printf("\n Element %d which was searched is found and is = %d",no,ptr->info);
		printf("\n Do you want replace it, press 1 for yes : ");
		scanf(" %d",&i);
		if(i==1) {
			printf("\n Enter new element :");
			scanf(" %d",&ino);
			ptr->info=ino;
		} else
		    printf("\n\t It's okay");
	} else
	   printf("\n Element %d does not exist in the binary tree",no);
	return(root);
}





Quantitative Aptitude
Reasoning
Programming
Interview