Lösche Knoten aus dem binären Suchbaum, ohne Eltern in der Struktur gespeichert zu haben

Question

als eine Übung arbeite ich an einem binären Suchbaum. Ich habe es geschafft, den Binärbaum zu durchsuchen und Knoten hinzuzufügen, aber jetzt, wo ich versuche, einen Weg zu finden, zu löschen, scheint ich bei wie fest, wer der Elternteil eines Knotens ist, die gelöscht werden soll.

So beginnen mit i dieser Struktur

struct BST_node { 
    struct double_linked_list *data; 
    struct BST_node *left; 
    struct BST_node *right; 
}; 

und ich habe auch einen Zeiger für diese Struktur haben, die Fußpunkte ..

struct BST_node *BST_email_root = 0; 

ich diese Funktion für einen Knoten suchen

struct BST_node *BST_find_customer(struct BST_node *root, char *email) { 
if (root==NULL) 
    return NULL; 
if (strcmp(email,root->data->data->email)==0) 
    return root; 
else 
    { 
    if (strcmp(email,root->data->data->email)==-1) 
    return BST_find_customer(root->left,email); 
    else 
     return BST_find_customer(root->right,email); 
    } 

, die ich innerhalb anderer Funktionen aufrufen, durch Verwendung von

b = BST_find_customer(BST_email_root, email); 

und ich versuche, um die Funktion zu erstellen löschen nodes..What i dies ist haben: auch

struct BST_node *BST_delete(struct BST_node *root, char *email) 
    { 
    struct BST_node *temp; 
    if (root==NULL) 
     return root; 
    else if(strcmp(root->data->data->email,email)>0) 
     root->left = BST_delete(root->left, email); 
    else if(strcmp(root->data->data->email,email)<0) 
     root->right = BST_delete(root->right, email); 
    else 
     { 
     if(root->left == NULL && root->right == NULL) 
      { 
      free(root); 
      root = NULL; 
      } 
     else if(root->right == NULL) 
      { 
      temp = root; 
      root = root->left; 
      free(temp); 
      } 
     else if(root->left == NULL) 
      { 
      temp = root; 
      root = root->right; 
      free(temp); 
      } 
     else 
      { 
      struct BST_node *maxNode = findMaxNode(root->left);//finding the maximum in LEFT sub-tree 
      root->data = maxNode->data; //Overwriting the root node with MAX-LEFT 
      root->left = BST_delete(root->left, maxNode->data);//deleted the MAX-LEFT node 
      } 

     return root; 
     } 

    } 

Mit dieser Funktion

struct BST_node *findMaxNode(struct BST_node *root) 
      { 
       if(root->right == NULL) return root; 
       findMaxNode(root->right); 
      } 

jedoch diese nicht funktioniert auch und ich bekomme Fehler

Answer 1

Hier ist eine Lösung, obwohl es nicht rekursiv ist .....

Um einen Knoten N von einem BST zu löschen, müssen Sie die drei Fälle betrachten:

1. Wenn N ein Blatt, dann ist kein Problem, es nur
2. löschen Wenn N nur einen Sohn hat, nur ersetzen N von seinem Sohn; du brauchst den Zeiger auf den Vater von N, um das zu tun

3. Wenn N zwei Söhne hat, dann kannst du N durch den zweitletzten Sohn seines rechten Sohnes ersetzen, oder durch den riviltesten Sohn seines linken Sohnes Bestelleigenschaften.

   void *BST_delete(struct BST_node *root, char *email){ 
   
   if (root==NULL) 
       return; 
   
   struct BST_node * father = NULL; 
   char which_son; //will help us in remembering if root is the right or left son of his father 
   
   while (strcmp(email,root->data->data->email)!=0){ //first, finding root and remembering who's root father 
       if(root==NULL) { 
        return ; 
       } else if (strcmp(email,root->data->data->email) < 0){ 
        father = root; 
        root = root->left; 
        which_son = 'l'; 
       } else { 
        father = root; 
        root = root->right; 
        which_son = 'r'; 
       } 
   } 
       // now you have both the root node, and its father 
   if ((root->right == NULL) && (root->left == NULL)){ //case 1, if it's a leaf 
       free(root); 
       return; 
   } else if (root->left == NULL) { //case 2 
       if (which_son == 'l') { 
        father->left = root->right; 
       } else { 
        father->right = root->right; 
       } 
   
   } else { //case 3 : here i get the "rightest" son of root's left son 
       struct BSD_node * replacing_node = root->left; 
   
       while (replacing_node->right != NULL) { 
        replacing_node = replacing_node->right; 
       } //now replacing_node is a leaf, and can replace root 
       if (which_son == 'l') { 
        father->left = replacing_node; 
        replacing_node->left = root->left; 
        replacing_node->right = root->right; 
       } else { 
        father->right = replacing_node; 
        replacing_node->left = root->left; 
        replacing_node->right = root->right; 
       } 
   } 
   free (root); 
   } 
   

Ich änderte den Rückgabewert Ihrer Funktion void, da es keinen Rückgabewert benötigen.

Es kann einfacher implementiert werden, indem einfach das "Daten" -Feld eines Knotens durch einen anderen ersetzt wird, aber ich habe es bewusst so implementiert, dass der zu löschende Knoten durch einen seiner Nachfolger ersetzt wird .

Wenn es Ihnen nicht offensichtlich erscheint, dass der zu unterdrückende Knoten durch den rechtesten (linken) Sohn seines linken (rechten) Sohnes ersetzt werden soll, dann prüfen Sie, dass dies die einzigen 2 Knoten sind, die den Knoten nicht darstellen Risiko, die Reihenfolge Ihres BSD zu brechen.

Auch diese Funktion leidet viel daran, monolithisch zu sein, würde es genießen, umgestaltet zu werden.