Zusammenfassung Informatik: Die Datenstrukur Graph (Kennzeichen, Darstellung, Durchlauf) + Die Datenstruktur Baum (Löschen, Durchlauf) Q11 Gymnasium Bayern

Informatik Kurzarbeit:


Bäume:
• Löschen (Programmcode):
Es müssen drei Fälle berücksichtigt werden:
1. Knoten hat keinen Nachfolger → einfach entfernen
2. Knoten hat nur einen Nachfolger → Knoten durch Nachfolger ersetzen
3. Knoten hat 2 Nachfolger → Idee: Knoten durch kleinsten Knoten im rechten Teilbaum ersetzen.


o Entfernen in BINBAUM:
public void Entfernen(String wort)
{
WOERTERBUCHEINTRAG w = new WOERTERBUCHEINTRAG(wort,"");
wurzel = wurzel.Entfernen(w);
}

o Entfernen in KNOTEN:
public BAUMELEMENT Entfernen(DATENELEMENT d)
{
if(daten.InformationAusgeben().equals(d.InformationAusgeben() ) )
{
if(nachfolgerLinks.IstAbschluss() && nachfolgerRechts.IstAbschluss() )
{
return nachfolgerLinks; //alternativ: return new Abschluss();
}
else
{
if(nachfolgerLinks.IstAbschluss() && !nachfolgerRechts.IstAbschluss() )
{
return nachfolgerRechts;
}
else{
if(!nachfolgerLinks.IstAbschluss() && nachfolgerRechts.IstAbschluss() )
{
return nachfolgerLinks;
}
else
{
DATENELEMENT kleinstesElementRechts;
kleinstesElementRechts = nachfolgerRechts.KleinstesElement(null);
daten = kleinstesElementRechts;
nachfolgerRechts.Entfernen(kleinstesElementRechts);

, return this;
/* kompaktere Alternative:
* daten = nachfolgerRechts.KleinstesElement(null);
* nachfolgerRechts.Entfernen(kleinstesElementRechts);
* return this;
*/
}
}
}
}
else
{
if(daten.IstKleinerAls(d))
{
nachfolgerRechts = nachfolgerRechts.Entfernen(d);
}
else
{
nachfolgerLinks = nachfolgerLinks.Entfernen(d);
}
return this;
}
}
• Durchlaufen eines Baumes:


In-Order:
1. Ausgabe des linken Teilbaums
2. Ausgabe des Knoteninhalts
3. Ausgabe des rechten Teilbaums
(==>von links – über den Knoten - nach rechts)

2 4 5 7 8 9 11
Pre-Order: Post-Order:
1. Ausgabe des Knoteninhalts 1. Ausgabe des linken Teilbaums
2. Ausgabe des linken Teilbaums 2. Ausgabe des rechten Teilbaums
3. Ausgabe des rechten Teilbaums 3. Ausgabe des Knoteninhalts
(==>vom Knoten, nach links und dann rechts) (==>von links nach rechts, dann Knoten)

7 4 2 5 9 8 11 2 5 4 8 11 9 7