Binärer Suchbaum Löschmethodenfehler

Question

Ich versuche eine Methode zu schreiben, die rekursiv einen Knoten aus einem binären Suchbaum löscht. Ich verstehe den Algorithmus, aber mein Code gibt gerade einen Fehler zurück. Wenn ich versuche, einen Blattknoten zu löschen, d. H. Einen Knoten, der keine Kinder hat, löscht er diesen Knoten, aber auch den obersten Knoten des Baums.

Ich habe bereits Methoden, die den Kopf eines Knotens finden, getValue(), sowie das Finden der linken und rechten Teilbäume, getLeft() und getRight(). Ich habe auch die Methode isEmpty(), die überprüft, ob ein Baum leer ist.

Dies ist mein Code zur Zeit, wo x wird der Knoten gelöscht werden und eine ist ein binärer Suchbaum:

public static Tree delete(int x, Tree a) { 
     if (a.isEmpty()) { 
      return new Tree(); 
     } if (x>a.getValue()) { 
      return delete(x, a.getRight()); 
     } else if (x<a.getValue()) { 
      return delete(x, a.getLeft()); 
     } else { 
      if (a.getLeft().isEmpty()&&a.getRight().isEmpty()) { 
       return new Tree(); 
      } if (a.getRight().isEmpty()) { 
       return delete(x, a.getLeft()); 
      } if (a.getLeft().isEmpty()) { 
       return delete(x, a.getRight()); 
      } else { 
       return new Tree(); //not yet completed 
      } 
     } 
    } 

Kann mir jemand gibt keine Hinweise darauf, warum dies geschieht würde? Vielen Dank im Voraus

Edit: Hier ist der Code, die schließlich arbeiteten, wenn jemand über diese Frage

public static Tree delete(int x, Tree a) { 
     if (a.isEmpty()) { 
      return new Tree(); 
     } if (x>a.getValue()) { 
      return new Tree(a.getValue(), a.getLeft(), delete(x, a.getRight())); 
     } else if (x<a.getValue()) { 
      return new Tree(a.getValue(), delete(x, a.getLeft()), a.getRight()); 
     } else { 
      if (a.getLeft().isEmpty()&&a.getRight().isEmpty()) { 
       return new Tree(); 
      } if (a.getRight().isEmpty()) { 
       return new Tree(a.getLeft().getValue(), delete(a.getLeft().getValue(), a.getLeft()), a.getRight()); 
      } if (a.getLeft().isEmpty()) { 
       return new Tree(a.getRight().getValue(), a.getLeft(), delete(a.getRight().getValue(), a.getRight())); 
      } else { 
       return new Tree(max(a.getLeft()), delete(max(a.getLeft()), a.getLeft()), a.getRight()); 
      } 
     } 
    } 

Answer 1

Diese Methode gibt einen leeren Baum statt Einstellung links oder rechts als leer stolpern passiert. Aus diesem Grund denken Sie, dass der oberste Knoten gelöscht wird. Es sieht auch nicht so aus, als ob es den Knoten selbst löscht, sondern nur Kindknoten.

Answer 2

Sie löschen nie wirklich etwas. Es gibt zwei Möglichkeiten, dies zu tun.

1. eine structureal Kopie des Baums zu machen, bis der Knoten gelöscht werden und dann eines der Kinder nehmen und die andere auf das gewählte Kind das Ergebnis des Einsatzes Einsatz ist das Ergebnis des Baumes.

2. Ermitteln des übergeordneten Elements des Knotens, der gelöscht werden soll, und Ändern des Zugriffsmechanismus auf den Knoten als eines der untergeordneten Elemente und Hinzufügen des anderen untergeordneten Baums zum übergeordneten Baum. Grundsätzlich haben Sie hier eine Baumklasse, die Einfügung behandelt und die eine Wurzel hat. Das Löschen des Stamms ist ein Sonderfall, bei dem ein Knoten neu gebunden und nicht geändert wird.

Wenn Sie ein Backtracking-Algorithmus machen, wo auf einen früheren Baum zurück benötigt wird, # 1 ist die einzige Wahl, und es wird so viel Struktur mit der vorherigen Version des Baumes teilen. Wenn Sie eine Datenstruktur iterieren und aktualisieren möchten, um etwas widerzuspiegeln, das Sie nie brauchen, ist der vorherige Zustand # 2 die beste Wahl.