Finden von Höhe im binären Suchbaum nach Einfügen und Löschen

Question

Der folgende Code soll die endgültige Höhe eines binären Suchbaums nach einer Reihe von Einfügungen und Löschungen ausgeben.

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

struct Node{ 
    int data; 
    struct Node *left; 
    struct Node *right; 
}; 

struct Node* Insert(int data, struct Node *root){ 
    if(root == NULL){ 
     root = malloc(sizeof(struct Node)); 
     root -> data = data; 
     root -> left = root -> right = NULL; 
    } 
    else{ 
     if(data < root -> data) Insert(data, root -> left); 
     else if(data > root -> data) Insert(data, root -> left); 
    } 
    return root; 
} 

struct Node* Find(int data, struct Node *root){ 
    if(root == NULL || root -> data == data) return root; 
    if(data < root -> data) return Find(data, root -> left); 
    if(data > root -> data) return Find(data, root -> right); 
} 

int FindMin(struct Node *root){ 
    int min, l_min, r_min; 
    if(root == NULL) return INT_MIN; 
    min = root -> data; 
    l_min = FindMin(root -> left); 
    r_min = FindMin(root -> right); 
    if(l_min < min) min = l_min; 
    if(r_min < min ) min = r_min; 
    return min; 
} 

struct Node* Delete(int data, struct Node *root){ 
    struct Node *temp; 
    if(data < root -> data) root -> left = Delete(data, root -> left); 
    else if(data > root -> data) root -> right = Delete(data, root -> right); 
    else{ 
     if(root -> left != NULL && root -> right != NULL){ 
      root -> data = FindMin(root -> right); 
      root -> right = Delete(root -> data, root -> right); 
     } 
     else{ 
      temp = root; 
      if(root -> left == NULL) root = root -> right; 
      if(root -> right == NULL) root = root -> left; 
      free(temp); 
     } 
    } 
    return root; 
} 

int Height(struct Node *root){ 
    int l_height, r_height; 
    if(root == NULL) return 0; 
    else{ 
     l_height = Height(root -> left); 
     r_height = Height(root -> right); 
     if(l_height > r_height) return l_height + 1; 
     else return r_height + 1; 
    } 
} 

int main(){ 
    struct Node *root = NULL, *temp = NULL; 
    int n, a, b; 
    scanf("%i",&n); 
    while(n--){ 
     scanf("%i %i",&a,&b); 
     if(a == 1){ 
      temp = Find(b,root); 
      if(temp != NULL) continue; 
      root = Insert(b,root); 
     } 
     else if(a == 2){ 
      temp = Find(b,root); 
      if(temp == NULL) continue; 
      root = Delete(b,root); 
     } 
     else{ 
      continue; 
     } 
    } 
    printf("Height: %i\n",Height(root)); 
    return 0; 
} 

Die erste Eingabe ist die Nummer n, die die Anzahl der Zeilen angibt.

Alle folgenden Zeilen haben die ganzen Zahlen "a b". a == 1 bedeutet Einfügen und b == 2 bedeutet Löschen und b ist der Wert, der eingefügt oder gelöscht werden soll. Die Funktion "Find" testet, ob auf der BST ein Wert vorhanden ist, sodass ich keine bereits vorhandenen Objekte einfüge oder versuche, Objekte zu entfernen, die nicht in der BST vorhanden sind.

So zum Beispiel, ist dies ein gültiger Testfall, und es sollte 5 zurück:

10 
1 5 
1 8 
1 3 
1 4 
1 2 
1 1 
1 0 
1 7 
1 9 
2 3 

aber mein Code so zu tun versagt und einfach „1“ für jeden möglichen Testfall Rückkehr . Ich habe keine Ahnung, warum das passiert. Irgendwelche Ideen?

Lösung: Dank @coderredoc, hier ist jetzt eine voll funktionsfähige Version dieses Codes.

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


struct Node{ 
    int data; 
    struct Node *left; 
    struct Node *right; 
}; 

struct Node* Insert(int data, struct Node *root){ 
    if(root == NULL){ 
     root = malloc(sizeof(struct Node)); 
     root -> data = data; 
     root -> left = root -> right = NULL; 
    } 
    else{ 
     if(data < root -> data) root -> left = Insert(data, root -> left); 
     else if(data > root -> data) root -> right = Insert(data, root -> right); 
    } 
    return root; 
} 

struct Node* Find(int data, struct Node *root){ 
    if(root == NULL || root -> data == data) return root; 
    if(data < root -> data) return Find(data, root -> left); 
    if(data >= root -> data) return Find(data, root -> right); 
    return NULL; 
} 

struct Node* FindMin(struct Node *root){ 
    struct Node *temp = root; 
    while(temp -> left != NULL) temp = temp -> left; 
    return temp; 
} 

struct Node* Delete(int data, struct Node *root){ 
    struct Node *temp; 
    if(root == NULL) return NULL; 
    if(data < root -> data) root -> left = Delete(data, root -> left); 
    else if(data > root -> data) root -> right = Delete(data, root -> right); 
    else{ 
     if(root -> left == NULL){ 
      temp = root -> right; 
      free(root); 
      return temp; 
     } 
     else if(root -> right == NULL){ 
      temp = root -> left; 
      free(root); 
      return temp; 
     } 
     else{ 
      temp = FindMin(root -> right); 
      root -> data = temp -> data; 
      root -> right = Delete(temp -> data, root -> right); 
     } 
    } 
    return root; 
} 

int Height(struct Node *root){ 
    int l_height, r_height; 
    if(root == NULL) return 0; 
    else{ 
     l_height = Height(root -> left); 
     r_height = Height(root -> right); 
     if(l_height > r_height) return l_height + 1; 
     else return r_height + 1; 
    } 
} 

int main(){ 
    struct Node *root = NULL, *temp = NULL; 
    int n, a, b; 
    scanf("%i",&n); 
    while(n--){ 
     scanf("%i %i",&a,&b); 
     if(a == 1){ 
      temp = Find(b,root); 
      if(temp != NULL) continue; 
      root = Insert(b,root); 
     } 
     else if(a == 2){ 
      temp = Find(b,root); 
      if(temp == NULL) continue; 
      root = Delete(b,root); 
     } 
     else{ 
      continue; 
     } 
    } 
    printf("%i\n",Height(root)); 
    return 0; 
} 

Answer 1

Ja, weil Sie nie einen hinzugefügten Knoten verbunden haben.

if(data < root -> data) root->left= Insert(data, root -> left); 
else if(data >= root -> data) root->right = Insert(data, root -> right); 

Beachten Sie auch, dass sowohl in den Fällen, in Insert() Sie root->left benutzt hatte. Es sollte wie oben gezeigt sein.

Auch in der Find() Funktion

struct Node* Find(int data, struct Node *root){ 
    if(root == NULL || root -> data == data) return root; 
    if(data < root -> data) return Find(data, root -> left); 
    if(data >= root -> data) return Find(data, root -> right); 
    // ^ You need to make it >= 
    return NULL; //<----Add it 
} 

Auch die seg Fehler du hast ist wegen der falschen Löschlogik. Die richtige wäre wie

struct Node* Delete(int data, struct Node *root){ 
    struct Node *temp; 
    if(root == NULL) return NULL; 
    if(data < root -> data) root -> left = Delete(data, root -> left); 
    else if(data > root -> data) root -> right = Delete(data, root -> right); 
    else{ 
     if (root->left == NULL) 
     { 
      struct Node *temp = root->right; 
      free(root); 
      return temp; 
     } 
     else if (root->right == NULL) 
     { 
      struct Node *temp = root->left; 
      free(root); 
      return temp; 
     } 
     else 
     { 
      struct Node *temp = FindMin(root->right); 
      root->data = temp->data; 
      root->right = Delete(temp->data, root->right); 
     } 
    } 
    return root; 
} 

Auch Ihre Version von findMin gibt nur den Minimalwert aller Knotenwerte. Aber das ist nicht, was in Delete() Funktion benötigt wird. Deshalb diese Funktion.

struct Node*FindMin(struct Node* node) 
{ 
    struct Node *current = node; 
    while (current->left != NULL) 
      current = current->left; 
    return current; 
}