Thread: Binary Search Tree project

  1. #1
    Registered User
    Join Date
    May 2019
    Posts
    1

    Binary Search Tree project

    So i have this university project and one of my tasks is to make a Binary Search Tree that does some operations !

    Write a program in C that will process data for student IT graduates. The data should be loaded from a text file containing the following information for each student: Student Identity, Student Name, Surname, Grade in the Data Structure course.
    The application initially reads the file and creates a BST in which each node maintains a record of the file. The BST is arranged in terms of student identity and implemented with dynamic memory management. After the BST has been created, the application displays a menu with the following options


    1) Imaging the BST with in-order intersection
    2) Search the student based on his / her identity
    3) Modification of the student's registered data based on his / her identity
    4) Delete a student record based on his / her identity
    5) Exit the application


    Specifically from what you see in my code I have trouble importing the data in BST correctly, I can not find a way to create a function that will process the data as well as I can not find a function that will delete a record from BST . Finally, the program crashes when I ask her to search for a student on the basis of his identity.


    Here is the code :


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <conio.h>
    #define MAXLEN 20
    
    struct record
    {
        char id[10];
        char firstName[20];
        char lastName[20];
        char score[10];
    };
    
    struct node
    {
        char *value;
        struct node *leftptr;
        struct node *rightptr;
    };
    
    typedef int (*Compare)(const char *, const char *);
    
    
    void insert(char* key, struct node** leaf, Compare cmp)
    {
        int res;
        if( *leaf == NULL )
        {
            *leaf = (struct node*) malloc( sizeof( struct node ) );
            (*leaf)->value = malloc( strlen (key) +1 );
            strcpy ((*leaf)->value, key);
            (*leaf)->leftptr = NULL;
            (*leaf)->rightptr = NULL;
        }
        else
        {
            res = cmp (key, (*leaf)->value);
            if( res < 0)
            {
                insert( key, &(*leaf)->leftptr, cmp);
            }
            else if( res > 0)
            {
                insert( key, &(*leaf)->rightptr, cmp);
            }
            else
            {
                printf ("Key '%s' already in tree\n", key);
    
            }
        }
    }
    
    
    int CmpStr(const char *a, const char *b)
    {
        return (strcmp (a, b));
    }
    
    void in_order(struct node *root)
    {
        if( root != NULL )
        {
            in_order(root->leftptr);
            printf("   %s\n", root->value);
            in_order(root->rightptr);
        }
    }
    
    void search(char* key, struct node* leaf, Compare cmp)
    {
        int res;
        if( leaf != NULL )
        {
            res = cmp(key, leaf->value);
            if( res < 0)
            {
                search( key, leaf->leftptr, cmp);
            }
            else if( res > 0)
            {
                search( key, leaf->rightptr, cmp);
    
            }
            else
            {
                printf("\n'%s' found!\n", key);
    
            }
        }
        else
        {
            printf("\nNot in tree\n");
        }
        return;
    }
    
    char *input()
    {
        static char line[MAXLEN+1];
        printf("Please enter a string : ");
        fgets(line, sizeof line, stdin);
        return (strtok(line, "\n" ));
    }
    
    void menu()
    {
        printf("Please select one of the following options : a) Display students in order\tb) Search a student via it's id\tc)Edit students info\td)Delete a student\td)EXIT\n");
    }
    
    int main()
    {
        FILE *fileptr;
        struct node *p_root=NULL;
    
        int i=0,idx=0;
    
    
        fileptr=fopen("students.txt","r");
        struct record *pinakas;
        pinakas=(struct record *)malloc(17*sizeof(struct record));
    
        if(fileptr)
        {
            while(!feof(fileptr))
            {
                fscanf(fileptr,"%[^ ] %[^ ] %[^ ] %[^ \n]\n", pinakas[idx].id, pinakas[idx].firstName, pinakas[idx].lastName, pinakas[idx].score);
                insert(pinakas[idx].id, &p_root, (Compare)CmpStr);
                idx++;
            }
        }
    
    
        char *searchID;
        char option;
        option='x';
    
        while(option!='e')
        {
            menu();
    
            option=getch();
    
            if(option=='a')
            {
                in_order(p_root);
            }
            else if(option=='b')
            {
                searchID=input();
                search(searchID, &p_root, (Compare)CmpStr);
            }
            else if(option=='c')
            {
                printf("Edit student info\n");
            }
            else if(option=='d')
            {
                printf("Delete student from archives\n");
            }
            else if(option=='e')
            {
                exit(1);
            }
        }
    
        fclose(fileptr);
        free(pinakas);
    
        return 0;
    }
    The .txt file is like this:

    AB123456 ANNA SMITH 10.0
    AB234567 BILL WHITE 3.0
    AB345678 GEORGE REDD 7.0
    ...
    Last edited by Vasillis13; 05-10-2019 at 07:58 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,253
    Code:
    struct node
    {
        char *value;
    Why char *value, and not struct record *value?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,836
    Read this
    or this
    You shouldn't use feof to control your while loop

  4. #4
    Registered User
    Join Date
    May 2019
    Posts
    1
    a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys less than the node's key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree-search method help?
    By shocklightning in forum C++ Programming
    Replies: 5
    Last Post: 03-25-2012, 10:57 PM
  2. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  4. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  5. binary search tree
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 04-22-2002, 07:50 AM

Tags for this Thread