Löschen eines Knotens bilden einen binären Suchbaum in C

Ich bin versucht zu schreiben, eine Funktion zum löschen von Knoten(jeder Knoten) aus einem binären Suchbaum. Für einige Grund, die löschen-Funktion löscht mehrere Knoten. Es ist eine rekursive Funktion und ich bin etwas verwirrt, wenn es um resursion. unten ist mein code, kann jemand mir helfen herauszufinden, was falsch gelaufen ist.
Vielen Dank im Voraus

#include<stdio.h>
#include<stdlib.h>
#include<string.h>


typedef struct node *nodeP;
typedef struct StudentRoster *StudentRosterP;

struct node
{
    nodeP left;
    char name[30];
    int ID;
    nodeP right;            
};

struct StudentRoster
{
    nodeP root;
    int size;
};

//create a new student roster
StudentRosterP newStudentRoster()
{
    StudentRosterP new;
    new = NULL;
    new = malloc(sizeof(struct StudentRoster));
    if (new == NULL)
        {
            fprintf(stderr, "Error: Memory allocation for Student Roster failed\n");
            return NULL;
        }
    else
        {
            new->root = NULL;
            new->size = 0;
            return new;
        }   
}

//creates a new node to store student information
nodeP newNode(char *name, int ID)
{
    nodeP new;
    new = NULL;
    new = malloc(sizeof(struct node));
    if(new == NULL)
    {
        fprintf(stderr, "Memory allocation for the node failed.\n");
        return NULL;
    }
    else
    {
        new->left = NULL;
        new->right = NULL;
        new->ID = ID;
        strcpy(new->name, name);
        return new;
    }
}
//function to insert student. this is a helper function, recursive call

void insert(nodeP root, int ID, char * name)
{

     if (ID == root->ID)
     {
         printf("Duplicate IDs not allowed\n");
         return;
     }
     else {
           if(ID < root->ID)
            {
               if(root->left == NULL)
               {
                   root->left = newNode(name, ID);
               }
               else
               {
                root = root->left;
                insert(root, ID, name); 
               }
            }
            else 
            {
               if(root->right == NULL)
               {
                   root->right = newNode(name, ID);
               }
               else
               {
                    root = root->right;
                    insert(root, ID, name);
               }
            }
     }
}

//to insert new student
void insertStudentRoster(StudentRosterP roster, char * name, int ID)
{

     nodeP root = roster->root;     
        if(roster->root == NULL)     //its empty 
        {
             roster->root = newNode(name, ID);         
        }

        else {                
            if (ID == roster->root->ID)
            {
                printf("Duplicate IDs not allowed\n");
                return;
            }
            else
            {
                insert(roster->root, ID, name);
            }            
        }     
}

/*
 * Helper function for removeStudentRoster
 * finds a node to be deleted and returns its pointer
 */
nodeP findMin(nodeP node)
{
    while(node->left != NULL)
    {
        node = node->left;
    }
    return node;         
}

//removes the node to be deleted
//returns null pointer to the parent function
//This is where I am having problem

nodeP delete(nodeP root, int ID)
{
    if(root == NULL)
    {
        return root;
    }

    else if(ID < root->ID)
    {
        root->left = delete(root->left, ID);
    }
    else if(ID > root->ID)
    {
        root->right = delete(root->right, ID);
    }
    else
    {
        if (root->left == NULL && root->right == NULL)
        {

           free(root);
           root = NULL;
        }

        else if(root->left == NULL)
        {
            nodeP temp = root;
            root = root->right;
            free(temp);
        }
        else if(root->right == NULL)
        {
            nodeP temp = root;
            root = root->left;
            free(temp);
        }
        else
        {
            nodeP temp = findMin(root->right);
            root->ID = temp->ID;
            strcpy(root->name, temp->name);
            root->right = delete(root->right, temp->ID);

        }
        return root;
    }
}

/*
 * Removes the node containing the matching names
 * Parameters: StudentRoster, id
 */
void removeStudentRoster(StudentRosterP roster, int ID)
{
    if(roster == NULL)
    {
        printf("The Student roster does not exist\n");
        return;
    }
    else if(roster->root == NULL)
    {
        printf("The Student roster is empty\n");
        return;
    }
    else{
         //find the node to be deleted
        roster->root = delete(roster->root, ID);        
    }    
}

//for printing in ordered

void inOrder(nodeP node)
{
    if (node == NULL)
        return;
    inOrder(node->left);
    printf("ID #: %i, Name: %s \n", node->ID, node->name);
    inOrder(node->right);

}
/*
 * Displays all the entries in the Phone book in order
 * Display one person per line, ID followed by first name
 */

void displayStudentRoster(StudentRosterP roster)
{
   if (roster->root == NULL)    {
        printf("The Roster is empty");
        return;
    }
   else
    {
        inOrder(roster->root);
        return;        
    }    
}

int main()
{

    StudentRosterP newRoster;
    newRoster = newStudentRoster();
    insertStudentRoster(newRoster, "Alice", 10);
    insertStudentRoster(newRoster, "Jake", 8);

    insertStudentRoster(newRoster, "josh", 12);
    insertStudentRoster(newRoster, "Alen", 9);
    insertStudentRoster(newRoster, "Joe", 11);    


    removeStudentRoster(newRoster, 11);      //it removes the whole roster when removing a node  that has no childrens
//when removing the root, it also removes the right child

    displayStudentRoster(newRoster);



    return (EXIT_SUCCESS);
}

InformationsquelleAutor pdhimal1 | 2014-11-21

Schreibe einen Kommentar