Embedded Files
Q. Write C language based code to create and operate on ADT : Binary Search Tree with unique positive integer values as Key Values:
Q. Write C language based code to create and operate on ADT : Binary Search Tree with unique positive integer values as Key Values:
(1). Create a BST with a single node as its Root Node
(2). Add a node with a given Key Value (give error message, if Key Value already exists, else add a node)
(3). Given a Key Value, delete a node if it exists; else give error message that the Key Value does not exist
(4). Perform search for a given Key Value; if it exists, output " Element Found", else output "Doesn't Exist in the tree"
(5). Perform In-order, Pre-order, Post-order traversal of a given BST and print Key Values in a row, separated by vertical bars
".C" file is available in downloadable format here :
".C" file is available in downloadable format here :
bst.c#include<stdio.h>#include<stdlib.h>typedef struct tree{int info;struct tree* left;struct tree* right;}node;node* create (node*); void insert (node*, node*);node* search (node*, int);node* del (node*, int);node* preorder (node*);node* inorder (node*);node* postorder (node*);node* create (node* root){int no,ele,i=0;node* n=NULL;node *key;printf("\nNumber of entries:\t");scanf("%d", &no);while (i<no){printf("\n----INSERT----");printf("\nEnter data:\t");scanf("%d", &ele);if (ele> 0){key= search(root, ele);if (key==NULL){n=(node*)malloc(sizeof(node));n->info = ele;n->left=NULL; n->right=NULL;if(root==NULL){printf("\nIt's the first element of the tree.");root=n;}else{insert(n, root);}i++;}else printf("The node data: %d already exists in the tree.",ele);}else printf("\nOnly Positive integers are allowed");}return root;}void insert (node* nw, node* root){node *p;node *q;p=root; q=root;while(q!=NULL){p=q;if(nw->info>q->info)q=q->right;elseq=q->left;}if(p->info > nw->info){p->left = nw;}else{p->right = nw;}}node* search(node* root, int ele){node *q;q=root;while((q!=NULL)&&(q->info!=ele)){if(q->info>ele)q=q->left;elseq=q->right;}return q;}node* del(node* root, int ele){node *temp, *r; if (root == NULL) return root; if (ele < root->info) root->left = del(root->left, ele); else if (ele > root->info) root->right = del(root->right, ele); else { if (root->left == NULL) { temp = root->right; free(root); return temp; } else if (root->right == NULL) { temp = root->left; free(root); return temp; } r=root->right; while(r->left!=NULL) r=r->left; temp = r; root->info = temp->info; root->right = del(root->right, temp->info); } return root;}node* preorder (node* q){if(q!=NULL){printf(" | %d | ", q->info);q->left = preorder(q->left);q->right = preorder(q->right);}return q;}node* inorder (node* q){if(q!=NULL){q->left=inorder(q->left);printf(" | %d | ", q->info);q->right=inorder(q->right);}return q;} node* postorder (node* q){if(q!=NULL){q->left=postorder(q->left);q->right=postorder(q->right);printf(" | %d | ", q->info);}return q;} void main(){node *root=NULL, *q, *exist_or_not;int choice, val, check=0, ele;while(1){printf("\n\n\n1. Create\n2. Search\n3. Delete a node.\n4. Preorder Traversal\n5. Inorder Traversal\n6. Postorder Traversal.\n7. Exit program.\n\nEnter your choice:\t");scanf("%d", &choice);switch(choice){case 1: root=create(root); check=1; printf("\n\nCREATED"); break;case 2: printf("Enter value to be searched:\t"); scanf("%d", &ele); q= search(root, ele); if(q==NULL) {printf("\n%d doesn't exist in the tree.", ele);}else {printf("\n%d found",q->info);} break;case 3: printf("Enter value to be deleted:\t"); scanf("%d", &val); exist_or_not= search(root, val); if(exist_or_not==NULL) printf("\nERROR: The value doesnot exist"); else root = del(root, val); break;case 4: if(check) { preorder(root);}else printf("\nNo data stored yet, first create the tree."); break;case 5: if(check) { inorder(root);} else printf("\nNo data stored yet, first create the tree."); break;case 6: if(check) { postorder(root); } else printf("\nNo data stored yet, first create the tree."); break; case 7: if(root==NULL) printf("\nExiting with empty tree\n\n"); else { root->right=NULL; root->left=NULL; free(root); printf("\nFREED ROOT\n\n"); } exit(0);default: printf("\n\nHey!! Choose an option from the choices mentioned!!\n And stop testing my program!!");}}}Google Sites
Report abuse