| Der letzte Beitrag |
| Mag_123 |
Binärbäume
Hallo! 
Ich bräuchte da mal eure Hilfe!
Habe eine Aufgabe bekommen, die ich leider nicht lösen kann:
Aufgaben:Ergänzen Sie die Methoden "longestBranch()" und "count()".Optimieren Sie die Methode "search(int wert )" wie unten beschrieben.Bereiten Sie für die nächste Präsenzsitzung eine Analyse der Methode "delete(int zahl)" vor.
public OrdBinTree search(int wert){
// Sucht einen Wert in einem Baum. Der Algorithmus wurde schon im Ausblick
// auf allgemeine Binärbäume ohne Ordnungsrelation geschrieben, die ja unser nächstes Thema sind.
OrdBinTree erg=null;
if (! isEmpty()){
if (wert==zahlInfo) erg=this;
else { erg=left.search(wert);
if (erg==null) erg=right.search(wert);
}
}
return erg;
}
// Aufgabe: Implementieren Sie für die Suche einen im Falle eines// geordneten Binärbaumes effektiveren Algorithmus, der die Ordnung// des Baumes ausnutzt.
public int longestBranch(){
// ????????????
}
public int count(){
// ermittelt die Anzahl der Knoten im Baum
int anz;
}
/***************************
* ? *
* A C H T U N G ? *
* ! A U F G A B E ! ? *
* ? *
***************************/
public OrdBinTree delete(int zahl){
// Löscht den ersten gefundenen Knoten, welcher den übergebenen Inhalt hat.
// Da dies u. U. die Wurzel ist, muss die Methode als Funktion geschrieben
// werden. Aufruf: sortBaum=sortBaum.delete(123);
if (!isEmpty()){
if (zahlInfo==zahl)
{ if (left.isEmpty()) return right;
else if (right.isEmpty()) return left;
else { // groesstes Element im linken Unterbaum
OrdBinTree vorgaenger, aktuell;
vorgaenger=this; aktuell=left;
while (!aktuell.right.isEmpty()){
vorgaenger=aktuell;
aktuell=aktuell.right;
}
int ersatz = aktuell.zahlInfo;
if (vorgaenger==this) vorgaenger.left=aktuell.left;
else vorgaenger.right=aktuell.left;
this.zahlInfo=ersatz;
return this;
}
}
else { if (zahl<zahlInfo) left=left.delete(zahl);
else right=right.delete(zahl);
return this;
}
} else return this;
} |
|
|
