Programmieraufagbe Queue
-
Hallo zusammen,
Ich bruche dringend eure Hilfe bei diesen zwei Aufgaben ich komme da einfach nicht weiter ich kann damit echt nichts anfangen nichtmal ansatzweise, bitte helft mir.Danke im Vorraus
Gegeben seinen die folgenden Java-Codefragmente:
class Knoten {
Object inhalt;
Knoten links;
Knoten rechts;
Knoten (Object e1) {
this.inhalt = e1;
}
}
class BinaerBaum{
private Knoten wurzel;
private Knoten cursor;
boolean isEmpty() {
return wurzel == null;
}
}
Weiterhin sei eine Implementierung der Klasse Queue mit folgenden Methoden gegeben:
class Queue () {
/** isEmpty testet, ob diese Queue leer ist. **/
boolean isEmpty() {...}
/** peek gibt das erste Element der Queue zurück, ohne es
aus der Queue zu entfernen **/
Knoten peek() {...}
/** poll gibt das erste Element der Queue zurück, und entfernt es
aus der Queue. Gibt null zurück, falls die Queue leer ist. **/
Knoten poll() {...}
/** offer fügt ein Element in die Queue ein. **/
void put (Knoten knoten) {...}
}
Bei den folgenden Aufgaben reicht es, die neu hinzukommenden Codeabschnitte zu
notieren; der bereits gegebene Code muss nicht wiederholt werden.a) Durch das folgende Interface ist eine Methode breitensuche(Knoten knoten)
definiert, die einen Binärbaum unter Verwendung der Breitensuche nach einem gegebenen
Knoten durchsucht und diesen als Ergebnis zurückgibt.
public interface Searchable {
public Knoten breitensuche(Knoten knoten)
throws NoSuchElementException
}
Notieren Sie für die Klasse BinaerBaum den Code, der nötig ist, um das Interface
Searchable unter Verwendung der Klasse Queue zu implementieren!
-
Breitensuche ist doch relativ klar.
Du hast einen Startpunkt und von dem aus besuchst du alle Kinder. Wenn du alle Kinder besucht hast besuchst du alle Kindeskinder etc. - bis du das Ziel gefunden hast.Besuchen heißt hier wohl die Queue zu verwenden. Du fügst den Startknoten in die Queue ein. Ab dann holst du dir immer ein Element aus der Queue, entfernst es und fügst alle Kinder in die Queue ein. Das machst du bis das entfernte Element das gesuchte war - dann terminiert dein Algorithmus. Wenn die Queue leer ist und du kein Element mehr entfernen kannst dann terminiert der Algorithmus auch - denn dann ist das gesuchte Objekt nicht im Baum enthalten.
-
Dieser Aufbau Hallo -> brauche Hilfe -> Aufgabenstellung, "ich kann damit echt nichts anfangen nichtmal ansatzweise" und die Interessenlosigkeit von Forumauswahl und Textformatierung lässt mich vermuten, dass du eine Komplettlösung erwartest. Ohne es dir direkt vorzuwerfen, möchte ich dennoch darauf hinweisen, dass hier nicht kostenlos Hausaufgaben gemacht werden, solltest du allerdings nach bereits eigener Recherche Schwierigkeiten im Weiterkommen haben, kannst du auf Hilfe hoffen.
Wo liegt denn genau das Problem?