Löschen Datenknoten Suchbaum

[Wave]

Hallo,
ich probiere eine Aufgabe zum Löschen in einem geordneten Suchbaum.
Der Pseudocode war gegeben mit:
....
Wenn Datenknoten gefunden wird, ermittle Anzahl der Kindknoten.
Falls 0 ... Datenknoten durch Abschluss ersetzen
Falls 1 ...
Falls 2 ... Inhalt Datenknoten durch Inhalt des Minimums im rechten Teilbaum ersetzen ...



Ich habe folgendes probiert:

public class Abschluss extends Baumelement{
  
    public void naechsterLinksSetzen(Baumelement bel){
    }
    
    public void naechsterRechtsSetzen(Baumelement ber){
    }
    
    public Baumelement naechsterLinksGeben(){
        System.out.println("Kein linker Nachfolger bekannt!");
        return this;
    }
    
    public Baumelement naechsterRechtsGeben(){
        System.out.println("Kein rechter Nachfolger bekannt!");
        return this;
    }
    
    public Datenelement inhaltGeben(){
        return null;
    }
    
     public Datenelement inhaltSuchen(Datenelement suchinhalt){
        return null;
    }
    
     
    public Baumelement entfernen(Datenelement suchinhalt){
        System.out.println("Fehler: Das Mitglied wurde nicht gefunden.");
        return this;
    }
        
    public Datenknoten minimumGeben(Datenknoten vaterknoten){
        return vaterknoten;
    }
    
}

public class Datenknoten extends Baumelement{

    private Baumelement naechsterLinks, naechsterRechts;
    private Datenelement inhalt;
    
    public void naechsterLinksSetzen(Baumelement bel){
        naechsterLinks = bel;
    }
    
    public void naechsterRechtsSetzen(Baumelement ber){
        naechsterRechts = ber;
    }
    
    public Baumelement naechsterLinksGeben(){
        return naechsterLinks;
    }
    
    public Baumelement naechsterRechtsGeben(){
        return naechsterRechts;
    }
    
    public Datenelement inhaltGeben(){
        return inhalt;
    }
    
     public Datenelement inhaltSuchen(Datenelement suchinhalt){
        if(inhalt.istGleich(suchinhalt)){
            return inhalt;
        }
        else if(inhalt.istKleiner(suchinhalt)){
            return naechsterRechts.inhaltSuchen(suchinhalt);
        }
        else{
            return naechsterLinks.inhaltSuchen(suchinhalt);
        }
    }
    
    public Baumelement entfernen(Datenelement suchinhalt){
        if(inhalt.istGleich(suchinhalt)){
            if((naechsterLinks == null) && (naechsterRechts == null)){      // keine Kindknoten
                return null;     
            }
            else if(naechsterLinks == null){        // ein rechter Kindknoten
                return naechsterRechts = naechsterRechts.naechsterRechtsGeben();
            }
            else if(naechsterRechts == null){       // ein linker Kindknoten
                return naechsterLinks = naechsterLinks.naechsterLinksGeben();
            }
            else{       // zwei Kindknoten
               Datenknoten dk = minimumGeben(this);
               naechsterRechts.entfernen(dk.inhaltGeben());
            }    
        }
        else if(inhalt.istKleiner(suchinhalt)){
            naechsterRechts = naechsterRechts.entfernen(suchinhalt); 
        }
        else{
            naechsterLinks = naechsterLinks.entfernen(suchinhalt);
        }
        return this;
    } 
     
    public Datenknoten minimumGeben(Datenknoten vaterknoten){
        return naechsterLinks.minimumGeben(this);
    }
    
}

Wenn ich z.B. einen Knoten zum Löschen eingebe, der keine Kinder hat, kommt "Fehler! Mitglied nicht gefunden". Der Knoten wird irgendwie nicht gefunden.
Auch wenn zwei Kindknoten sind, funktioniert das noch nicht.

Kann mir einer einen Hinweis geben? Danke...

 

[SlaterB]

ja warum steht dennn in

    public Baumelement entfernen(Datenelement suchinhalt){
        System.out.println("Fehler: Das Mitglied wurde nicht gefunden.");
        return this;
    }

für einen Abschluss-Knoten immer die Fehlermeldung,
bzw. was ist Abschluss? steht der immer am Ende, hat aber nie Inhalt?
wie soll man je zu einem Ende ohne diese Fehlermeldung kommen?

du brauchst ein Konzept, bisher erklärst du nicht im Detail den Aufbau vom ersten Element an,
was jede Einzelheit zu bedeuten hat, da kann man von außen wenig erkennen und korrgieren

andersrum gilt immer: du hast die Information vorliegen, du kannst jeden einzelnen Schritt bei der Suche mit Log-Meldungen
verfolgen, wenn es vom gedachten Idealverfahren abweicht (sofern natürlich bekannt, vorher gehts nicht..), dann lockerleicht zu bemerken

 

[Wave]

Hallo, danke für die Antwort.
Also im Datail:
- In einem binäre Suchbaum soll ein Knoten gelöscht werden mit obigen Preudocode.
- Klasse BAUMELEMENT ist abstrakt
- Klassen ABSCHLUSS Und DATENKNOTEN sind Unterklassen von BAUMELEMENT.

Um einen Datenknoten zu löschen, brauche ich den Vaterknoten, um die Referenz auf seinen Nachfolger( der gelöscht werden soll) auf ein Objekt der Klasse ABSCHLUSS setzen zu können (wenn das ein Blatt war).
In den anderen Fällen brauche ich auch den Vaterknoten, um Referenzen zu ändern.

Bei der Methode vaterDatenknotenGeben(...) liefert meistens eine Null-Pointer-Ex aus. Ich habe mit System.out.println(...) Schritte gesetzt, um zu schauen, wo es hakt. Aber hier finde ich den Fehler bisher einfach nicht. Wahrscheinlich habe ich die Methode sowieso falsch/ kompliziert hier umgesetzt, oder was auch immer.


Außerdem: Wenn ein Datenknoten zwei Kinder hat, muss ich ja das Minimum aus dem rechten Teilbaum suchen. Wie kann ich da die Referenzen ändern und das Minimum an die Stelle des zu löschenden Datenknoten setzen?
Danke für Tipps und Anregungen.
Anbei der neuere Code.

public abstract class Baumelement{

    public abstract void naechsterLinksSetzen(Baumelement bel);
    public abstract void naechsterRechtsSetzen(Baumelement ber);
    public abstract Baumelement naechsterLinksGeben();
    public abstract Baumelement naechsterRechtsGeben();
    public abstract Datenelement inhaltGeben();
    public abstract Baumelement entfernen(Datenelement suchinhalt);
    public abstract Baumelement minimumGeben2(Baumelement vaterknoten);
    public abstract Datenknoten datenknotenGeben(Datenelement suchinhalt);
    public abstract int anzahlDatenknotenGeben();
    public abstract int anzahlNachfolgerGeben();
    public abstract Datenknoten vaterDatenknotenGeben(Datenelement suchinhalt);
    public abstract void datenInorderAusgeben();

}



public class Datenknoten extends Baumelement{

    private Baumelement naechsterLinks, naechsterRechts;
    private Datenelement inhalt;
    
    public Datenknoten(Baumelement bel, Baumelement ber, Datenelement de){
        naechsterLinks = bel;
        naechsterRechts = ber;
        inhalt = de;
    }
  
    public void naechsterLinksSetzen(Baumelement bel){
        naechsterLinks = bel;
    }
    
    public void naechsterRechtsSetzen(Baumelement ber){
        naechsterRechts = ber;
    }
    
    public Baumelement naechsterLinksGeben(){
        return naechsterLinks;
    }
    
    public Baumelement naechsterRechtsGeben(){
        return naechsterRechts;
    }
    
    public Datenelement inhaltGeben(){
        return inhalt;
    }
    
    public Baumelement entfernen(Datenelement suchinhalt){
        Baumelement result = datenknotenGeben(suchinhalt);
        Datenknoten vaterknoten = vaterDatenknotenGeben(suchinhalt);
        if(result == null){
            System.out.println("Fehler! Das Mitglied wurde nicht gefunden.");
            return null;
        }
        else if(result.naechsterLinksGeben().anzahlNachfolgerGeben() == 0 && result.naechsterRechtsGeben().anzahlNachfolgerGeben() == 0){   // keine Kindknoten
            if(vaterknoten.naechsterLinksGeben().inhaltGeben().istGleich(suchinhalt)){
                vaterknoten.naechsterLinksSetzen(new Abschluss());
                System.out.println("0links");
                }
            
            else{
                vaterknoten.naechsterRechtsSetzen(new Abschluss());
                System.out.println("0rechts");
            }   
        }
        
        
        else if(result.naechsterLinksGeben().anzahlNachfolgerGeben() == 0){      // linker Knoten hat keinen Nachfolger
            result = result.naechsterRechtsGeben();
            System.out.println("Links leer");
        }
        else if(result.naechsterRechtsGeben().anzahlNachfolgerGeben() == 0){      // rechter Knoten hat keinen Nachfolger
            result = result.naechsterLinksGeben();  
            System.out.println("Rechts leer");
        }
        else{
            Baumelement minRechterTeilbaum = result.naechsterRechtsGeben().minimumGeben2(result);
            result = minRechterTeilbaum;
            Baumelement wurzelRechterTeilbaum = result.naechsterRechtsGeben();
            wurzelRechterTeilbaum.naechsterLinksSetzen(result.naechsterRechtsGeben());
        }
        return this;
    }
         
    public Baumelement minimumGeben2(Baumelement vaterknoten){
        return naechsterLinks.minimumGeben2(this);
    }
 
    
    public Datenknoten datenknotenGeben(Datenelement suchinhalt){
        if(inhalt.istGleich(suchinhalt)){
            return this;
        }
        else if(inhalt.istKleiner(suchinhalt)){
            return naechsterRechts.datenknotenGeben(suchinhalt);
        }
        else{
            return naechsterLinks.datenknotenGeben(suchinhalt);
        }
    }
    
    public Datenknoten vaterDatenknotenGeben(Datenelement suchinhalt){
        
        if(naechsterLinks.inhaltGeben().istGleich(suchinhalt)){
            System.out.println("A");
            return this;
            
        }
        else if(naechsterRechts.inhaltGeben().istGleich(suchinhalt)){
            System.out.println("B");
            return this;
            
        }
        else if(inhaltGeben().istKleiner(suchinhalt)){
            System.out.println("C");
            return naechsterRechts.vaterDatenknotenGeben(suchinhalt);
            
        }
        
        else{
            System.out.println("D");
            return naechsterLinks.vaterDatenknotenGeben(suchinhalt);
            
        }
    }
    
    public int anzahlDatenknotenGeben(){
        return 1 + naechsterLinks.anzahlDatenknotenGeben() + naechsterRechts.anzahlDatenknotenGeben();
    }
    
    public int anzahlNachfolgerGeben(){
        return 1 + naechsterLinks.anzahlNachfolgerGeben() + naechsterRechts.anzahlNachfolgerGeben();
    }
    
    public void datenInorderAusgeben(){
        naechsterLinks.datenInorderAusgeben();
        inhalt.datenAusgeben();
        naechsterRechts.datenInorderAusgeben();  
    }
    
}

public class Abschluss extends Baumelement{
  
    public void naechsterLinksSetzen(Baumelement bel){
    }
    
    public void naechsterRechtsSetzen(Baumelement ber){
    }
    
    public Baumelement naechsterLinksGeben(){
        System.out.println("Kein linker Nachfolger bekannt!");
        return this;
    }
    
    public Baumelement naechsterRechtsGeben(){
        System.out.println("Kein rechter Nachfolger bekannt!");
        return this;
    }
    
    public Datenelement inhaltGeben(){
        return null;
    }
    
    public Datenknoten sortiertEinfuegen(Datenelement de){
        return new Datenknoten(this, new Abschluss(), de);
    }
    
    public Datenelement inhaltSuchen(Datenelement suchinhalt){
        return null;
    }
    
    public boolean inhaltIstVorhanden(Datenelement suchinhalt){
        return false;
    }
    
    public Baumelement entfernen(Datenelement suchinhalt){
        System.out.println("Fehler: Das Mitglied wurde nicht gefunden.");
        return this;
    }
    
    public Baumelement anfuegenRechts(Baumelement teil){
        return teil;
    }
    
    public int tiefeGeben(int aktuelleTiefe){
        return aktuelleTiefe - 1;
    }
    
    public int tiefeSchluesselwertGeben(Datenelement suchinhalt, int tiefe){
      return  -1;
    }
    
    public Datenelement minimumGeben(Datenelement vaterelement){ 
        return vaterelement;
    }
    
    public Datenelement maximumGeben(Datenelement vaterelement){ 
        return vaterelement;
    }
    
    
    public Baumelement minimumGeben2(Baumelement vaterknoten){
        return vaterknoten;
    }
    
    public Datenknoten datenknotenGeben(Datenelement suchinhalt){
        return null;
    }
    
    public Datenknoten vaterDatenknotenGeben(Datenelement suchinhalt){
        return null;
    }
  
    public int anzahlDatenknotenGeben(){
        return 0;
    }
    
    public int anzahlNachfolgerGeben(){
        return 0;
    }
    
    public void datenInorderAusgeben(){
    }
    
}


public abstract class Datenelement{
  
    public abstract boolean istGleich(Datenelement de);
    public abstract boolean istKleiner(Datenelement de);
    public abstract void datenAusgeben();
    public abstract int mnrGeben();     // Schluessel
    
}

public class Mitglied extends Datenelement{

    private String nname;
    private String vname;
    private int mnr;   // Schluesselattribut
  
    public Mitglied(String nn, String vn, int neueMnr){
        nname = nn;
        vname = vn;
        mnr = neueMnr;
    }
    
    public boolean istGleich(Datenelement de){
        return mnr == ((Mitglied) de).mnr;
    }
    
    public boolean istKleiner(Datenelement de){
        return mnr < ((Mitglied) de).mnr;
    }
  
    public int mnrGeben(){   // Rueckgabe des Schluesselattributwertes 
        return mnr;
    }
    
    public void datenAusgeben(){
        System.out.println("Nachname: " + nname + ", Vorname: " + vname + ", Mitgliedsnummer: " + mnr + ".");
    }
}

 

[SlaterB]

du brauchst eine main-Methode, die einen Baum zusammenbaut,
am Anfang mit einen Element, prüfe dort alle benötigten Methoden,
dann zwei Elemente usw.,
jede Logmeldung muss nachvollzogen werden, was ist der initiale Anlass, welche Suche läuft gerade usw.,
welches Element vom Baum ist gerade dran und alles weitere

solange irgendwas am Log unklar ist musst du allein danach suchen, das fachliche Problem ist egal,

allzu konkrete Fragen hast du nicht, wenn mit einem Beispiel-Baum und gewisses Log dazu, paar Erklärungen,
dann kann ich vielleicht mitmachen,
aber einfach so das ganze Programm selber verstehen und auch noch zu suchen,
was du vielleicht zusätzlich brauchst, das mag ich nicht

(die bisherigen Erklärungen zum Baum sind aber durchaus gut)

 

[JAVA!!!]

Ich habe glaube ich deinen Fehler gefunden:
Schau mal in deine Methode minimumGeben2

 public Baumelement minimumGeben2(Baumelement vaterknoten){
return vaterknoten;
}

Du gibst hier etwas zurück was angeblich ein Minimum des Teilbaums sein soll, das aber gar keins ist.
Antwort ist zwar was spät aber egal