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
Du musst angemeldet sein, um einen Kommentar abzugeben.
In Ihrem "delete" - Funktion, Ihre
return
fehl am Platze ist (nur dann erreicht, wennID
entsprichtroot->ID
). Sie müssen, um es zu bewegen Vergangenheit die nächste schließende geschweifte Klammer, um es zu platzieren, nach derelse
es in:Darüber hinaus die Logik scheint falsch für das löschen von Knoten bei
ID
übereinstimmt (in diesem letztenelse
). Was Sie tun müssen, ist, verschieben Sie den rechten Zweig der äußersten rechten Knoten in den linken Zweig, oder den linken Zweig für den linken Knoten des rechten Zweig... dann zurück, dass Zweig. So verwenden Sie IhrefindMin()
zu finden, die am weitesten Links stehende Teil des rechten Zweiges, die wir tun können:InformationsquelleAutor Dmitri