BST.rar_binary search tree_tree

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<malloc.h> #define MAX_PATH_SIZE 100 #define MAX_FILEDIR_NAME_SIZE 10 #define MAX_BLOCKS 20 #define BLOCK_SIZE 1024 typedef struct file_descriptor { int is_dir; int fd_id; int size; char file_name[MAX_FILEDIR_NAME_SIZE]; char path[MAX_PATH_SIZE]; int blocks[MAX_BLOCKS]; }fd; //N-ary tree node typedef struct tree_node { fd *data; int is_deleted; struct tree_node *left_child; struct tree_node *right_siblings; struct tree_node *parent; }t_node; //binary search tree node typedef struct bst_node { struct bst_node *parent; struct bst_node *left; struct bst_node *right; char full_path[MAX_PATH_SIZE+MAX_FILEDIR_NAME_SIZE]; fd *file_desc; }b_node; b_node *bst_create() { b_node* root=NULL; return root; } int bst_insert(b_node **bst_root_ptr,fd *data) { char fullpath[110]; strcpy(fullpath,data->path); strcat(fullpath,"/"); strcat(fullpath,data->file_name); if(*bst_root_ptr==NULL) { b_node* b1=(b_node*)malloc(sizeof(b_node)); b1->file_desc=data; strcpy(b1->full_path,fullpath); b1->left=NULL; b1->right=NULL; b1->parent=NULL; *bst_root_ptr=b1; return 0; } else { b_node* b1=(b_node*)malloc(sizeof(b_node)); b1->file_desc=data; strcpy(b1->full_path,fullpath); b1->left=NULL; b1->right=NULL; b1->parent=NULL; b_node *curr,*par; curr=*bst_root_ptr; while(curr!=NULL) { par=curr; if((strcmp(fullpath,curr->full_path))<0) { curr=curr->left; } else if((strcmp(fullpath,curr->full_path))>0) { curr=curr->right; } else if((strcmp(fullpath,curr->full_path))==0) { printf("file already present\n"); return 1; } } if((strcmp(fullpath,par->full_path))<0) { par->left=b1; b1->parent=par; return 0; } else if((strcmp(fullpath,par->full_path))>0) { par->right=b1; b1->parent=par; return 0; } } } b_node *bst_search(b_node *bst_root,char *fullpath) { b_node* temp=bst_root; if(bst_root==NULL) { return NULL; } else { while(temp!=NULL) { if((strcmp(temp->full_path,fullpath))==0) { return temp; } else if((strcmp(temp->full_path,fullpath))>0) { temp=temp->left; } else if((strcmp(temp->full_path,fullpath))<0) { temp=temp->right; } } return NULL; } } int bst_delete(b_node **bst_root_ptr,char *fullpath) { int isfound=0; if(*bst_root_ptr==NULL) { printf("tree is empty\n"); return 1; } b_node* root=*bst_root_ptr; b_node* location; location=bst_search(root,fullpath); if(location==NULL) { return 1; } //if location has no child else if(location->left==NULL && location->right==NULL) { if(location->parent->left==location) { location->parent->left=NULL; } else if(location->parent->right==location) { location->parent->right=NULL; } return 0; } //if location has only right child else if(location->left==NULL && location->right!=NULL) { if(location->parent->left==location) { location->parent->left=location->right; } else if(location->parent->right==location) { location->parent->right=location->right; } return 0; } //if location has only left child else if(location->left!=NULL && location->right==NULL) { if(location->parent->left==location) { location->parent->left=location->left; } else if(location->parent->right==location) { location->parent->right=location->left; } return 0; } //if location has both child else if(location->left!=NULL && location->right!=NULL) { b_node* parent,*x; parent=location; x=location; while(x->left!=NULL) { parent=x; x=x->left; } location->file_desc=x->file_desc; strcpy(location->full_path,x->full_path); x->parent->left=NULL; return 0; } return 1; } int main() { b_node *root; root=bst_create(); fd* dir1 = (fd*)malloc(sizeof(fd)); dir1->is_dir=1; dir1->fd_id=1; dir1->size=10; strcpy(dir1->file_name,"BIN.txt"); strcpy(dir1->path,"/bin/"); dir1->blocks[0]=12; fd* dir4 = (fd*)malloc(sizeof(fd)); dir4->is_dir=1; dir4->fd_id=1; dir4->size=10; strcpy(dir4->file_name,"CIN.txt"); strcpy(dir4->path,"/bin/"); dir4->blocks[0]=12; fd* dir5 = (fd*)malloc(sizeof(fd)); dir5->is_dir=1; dir5->fd_id=1; dir5->size=10; strcpy(dir5->file_name,"YFS.txt"); strcpy(dir5->path,"/usr/"); dir5->blocks[0]=12; int return_insert=bst_insert ( &root,dir1); return_insert=bst_insert ( &root,dir4); return_insert=bst_insert ( &root,dir5); b_node *found =bst_search( root,"/usr/ADB.txt"); if(found != NULL) printf("\nFilname :%s\n", found->full_path); int return_delete=bst_delete(&root,"/usr/VFS.txt"); printf("\nReturn Value %d\n", return_delete); }