Java-Übungsaufgaben - Lösungsvorschlag

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
n0rdi
Neuling
Neuling
Beiträge: 2
Registriert: 4. Sep 2016 12:21

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von n0rdi »

Wurde das gesuchte Element aus dem Baum entfernt? Es wird ja nur das aktuelle Element auf dem Stack betrachtet und der Verweis vom vorherigen Element auf das Gesuchte existiert ja noch.

jr29zyni
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2016 15:03

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von jr29zyni »

n0rdi hat geschrieben:Wurde das gesuchte Element aus dem Baum entfernt? Es wird ja nur das aktuelle Element auf dem Stack betrachtet und der Verweis vom vorherigen Element auf das Gesuchte existiert ja noch.
Ja, darüber bin ich gerade auch gestolpert. Der Code würde so wohl nicht funktionieren und leider ist es nicht trivial, das zu beheben.
Man muss sich einen Verweis auf den Knoten darüber erhalten und die Information, ob der gefundene Knoten links oder rechts von diesem ist.
Ich hab es ziemlich anders, aber sehr kompliziert / ineffizient gelöst.

jr29zyni
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2016 15:03

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von jr29zyni »

jr29zyni hat geschrieben:Ich hab es ziemlich anders, aber sehr kompliziert / ineffizient gelöst.
Das wäre mein Code (TN steht für TreeNode):

Code: Alles auswählen

boolean remove(TN<T> r, T x){
	if(r == null) return false;             // leerer Baum
	Stack<TN<T>> s = new Stack<>();
	TN<T> p = null; // Pointer
	boolean found = false;
	TN<T> foundL = null;    // Knoten, unter dem links ein Knoten mit key == x ist
	TN<T> foundR = null;    // Knoten, unter dem rechts ein Knoten mit key == x ist
	TN<T> blattL = null;	// Knoten, unter dem links ein Blatt ist
	TN<T> blattR = null;	// Knoten, unter dem rechts ein Blatt ist
	TN<T> foundEl = null;	// Das Element mit key == x
	if(r.key.equals(x)) found = true;
	s.push(r);
	while(!s.isEmpty()){
		p = s.pop();
		if(p.left != null){
			if(p.left.key.equals(x)){ // wenn Element links von p den Schlüssel x hat
				foundL = p;
				found = true;
			}
			if(p.left.left == null && p.left.right == null){ // Wenn links von p ein Blatt ist
				blattL = p;
				if(blattL.equals(foundL))
					break; // Wenn das Blatt links von p den Schlüssel x hat => aus der while-Schleife raus
					       // Denn: Das ist ein einfacher Fall, den wir nutzen wollen
			}
			s.push(p.left);
		}
		if(p.left != null){ ... analog ... }
	}
	if(!found) return false; // wenn kein x gefunden wurde
	// foundEl setzen
		if(foundR == null && foundL == null) // wenn Gefundenes keine Vorgänger hat => muss root sein
			foundEl = r;
		else if(foundL != null)	   // wenn links von irgendeinem Knoten ein x gefunden wurde (Überprüfung links vor rechts ist ab jetzt die feste Reihenfolge!)
			foundEl = foundL.left;
		else foundEl = foundR.right;
	if(foundEl.left == null && foundEl.right == null){ // x ist Blatt
		if(foundL != null) // x wurde links gefunden
			foundL.left = null;
		else if(foundR != null) // x wurde rechts gefunden
			foundR.right = null;
		// Der verbleibende else-Fall ist der, dass die Wurzel key == x hat und die Wurzel ein Blatt ist
		// => keine Ahnung, wie man sie dann entfernt => erstmal nichts machen
	} else if (blattL != null){ // Blatt wurde links gefunden
		if(foundEl.equals(r)){ // "x == r"
			// Mache Blatt zur Wurzel
				blattL.left.left = r.left;
				blattL.left.right = r.right;
			blatt.left = null; // entferne Blatt von eigentlicher Stelle
		} else { // x links oder rechts gefunden
			// Bereite Einfügen des Blattes vor
				blattL.left.left = foundEl.left;
				blattL.left.right = foundEl.right;
			if(foundL != null) // links gefunden
				foundL.left = blattL.left; // überschreibe gefundenes mit Blatt
			else // rechts gefunden
				foundR.right = blattL.left; // überschreibe gefundenes mit Blatt
		}
	} else { // Blatt wurde rechts gefunden
		... analog ...
	}
	return true;
}
Ich denke aber mal, dass es einfacher gehen sollte :roll:

H0m3r0t1k0
Neuling
Neuling
Beiträge: 1
Registriert: 11. Sep 2016 12:09

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von H0m3r0t1k0 »

Hallo,

Problem: Methode "isAscending" für Binary Tree.
Frage 1: Gibt es einen Datentypen der wie ein Stack funktioniert, ich aber zusätzlich noch einen integer Wert "seenChildren" mit Werten 0,1 oder 2 abspeichern kann?
Oder darf man in der Klausur die vorgegebenen Klassen manipulieren, sodass man in die Klasse TreeNode noch ein Attribut "seenChildren" einfügt?
Ganz allgemein: Was ist die sauberste Variante um einmal komplett durch einen Baum zu laufen ohne eine Hilfsmethode zu schreiben.

Frage 2: darf man in der Klausur Hilfsmethoden schreiben?

Vielen Dank im Voraus.

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

H0m3r0t1k0 hat geschrieben: Problem: Methode "isAscending" für Binary Tree.
Frage 1: Gibt es einen Datentypen der wie ein Stack funktioniert, ich aber zusätzlich noch einen integer Wert "seenChildren" mit Werten 0,1 oder 2 abspeichern kann?
Sicher: Stack<Pair<TreeNode,int>> 8)
H0m3r0t1k0 hat geschrieben: Oder darf man in der Klausur die vorgegebenen Klassen manipulieren, sodass man in die Klasse TreeNode noch ein Attribut "seenChildren" einfügt?
Selbstverständlich würde ich Sie ggf. in einer Klausuraufgabe nicht mit so etwas allein lassen, sondern entsprechende Hinweise geben.
H0m3r0t1k0 hat geschrieben: Ganz allgemein: Was ist die sauberste Variante um einmal komplett durch einen Baum zu laufen ohne eine Hilfsmethode zu schreiben.
Die Frage ist mir doch zu allgemein, so dass ich keine Antwort weiß.
H0m3r0t1k0 hat geschrieben: Frage 2: darf man in der Klausur Hilfsmethoden schreiben?
Sofern es nicht ausdrücklich in der Aufgabenstellung verboten ist: ja.

KW

marcblaa
Neuling
Neuling
Beiträge: 4
Registriert: 15. Sep 2016 03:24

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von marcblaa »

Code: Alles auswählen

public boolean isItemwiseLess(PartiallyUsedArray<T> array1, PartiallyUsedArray<T> array2,Comparator<T> comp) {
	boolean less = false;
	if (array1.numberOfUsedSlots > array2.numberOfUsedSlots)
		return false;
	else if (array1.numberOfUsedSlots < array2.numberOfUsedSlots)
		return true;
		
	for (int i = 0; i < array1.numberOfUsedSlots; i++)
		if (comp.compare(array1.theArray[i], array2.theArray[i]) > 0)
			return false;
		else if (comp.compare(array1.theArray[i], array2.theArray[i]) < 0)
			less = true;
	return less;
}
Muss nicht die Bedingung erfüllt sein dass Länge des ersten Arrays <= des 2. Arrays ist UND dass jedes Element kleiner gleich ist UND eins mindestens kleiner ist.
Bei deinem Code gebe ich true zurück auch wenn nicht jedes Element kleiner gleich ist oder sogar kleiner ist, obwohl alle drei Bedingungen erfüllt seien müssen und nicht nur eine.

Beispiel: Das erste Array besteht aus {1,3,3} und das zweite aus {1,2,3,4,5} dann wird true zurückgeben, obwohl nicht alle Elemente <= bzw. < sind.
Kann auch sein dass ich die Aufgabenstellungen missverstanden habe, aber es steht ausdrücklich und zwischen den Bedingungen.

Grüße

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Hallo ich habe eine Frage zur Aufgabe 1 zur Implementierung der Methode find auf einem Binärbaum. Wieso wird in dieser inoffiziellen Lösung ein Stack benutzt? Kann man nicht die Eigenschaften des binären Baumes nutzen und den Comparator verwenden?

Ich hätte es iterativ so gelöst:

Code: Alles auswählen

public boolean find (TreeNode<T> tn, <T> tofind, Comparator<T> cmp){
	
	while (tn != null){
		
		if (cmp.compare(tofind,tn.key) == 0){
			
			return true;
		}
		if (cmp.compare(tofind, tn.key) < 0){
			
			tn = tn.left;
		}
		else if (cmp.compare(tofind, tn.key) > 0){
			
			tn = tn.right;
		}		
	}
	return false;
}
Und rekursiv so:

Code: Alles auswählen

public boolean find (TreeNode<T> tn, <T> tofind, Comparator<T> cmp){
	

	if (tn == null){
		
		return false;
	}
	if (cmp.compare(tofind, tn.key) == 0){
		
		return true;
	}
	if (cmp.compare(tofind, tn.key) < 0){
		
		return find(tn.left,tofind,cmp);
	}
	if (cmp.comapre(tofind, tn.key) > 0){
		
		return find(tn.right, tofind, cmp);
	}
}
Kann man das so machen?

Vielen Dank!
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben:Hallo ich habe eine Frage zur Aufgabe 1 zur Implementierung der Methode find auf einem Binärbaum. Wieso wird in dieser inoffiziellen Lösung ein Stack benutzt? Kann man nicht die Eigenschaften des binären Baumes nutzen und den Comparator verwenden?
In Ihrer Lösung nutzen Sie die Suchbaumeigenschaft. Wenn der binäre Baum kein Suchbaum ist, insbesondere wenn die Schlüsselwerte beliebig regellos im Baum verstreut sein können, müssen Sie wohl mit der Stacklösung arbeiten.

KW

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Alles klar vielen Dank! Ich habe noch eine kleine Frage. Bei diesem Beispiel zur linearen Suche könnte man ja den Code so lassen oder man legt ein aktuelles Element (TreeNode) an, um die aktuellen Werte zu speichern und weiterzuverarbeiten. Kann man die erste Anweisung in der while-loop so stehen lassen oder ist es "besser/schöner" eine weitere Variable zu initialisieren? Für die Funktionalität der Methode sollte es ja keinen Unterschied machen.

Besten Dank vorab!

D'Angelo

Code: Alles auswählen

 
 public boolean find (TreeNode<T> wurzel, <T> tf){

	if (wurzel == null) return false;
	
	Stack stack = new Stack<TreeNode>();
	stack.push(wurzel);

	while(!stack.isEmpty()){
	
		wurzel = stack.pop();
		
		if (wurzel.key.equals(tf)) return true;
		
		if (wurzel.left != null){
		
			stack.push(wurzel.left);
		}
		if (wurzel.right != null){
		
			stack.push(wurzel.right);
		}
	}
	return false;
}
 
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben:Kann man die erste Anweisung in der while-loop so stehen lassen oder ist es "besser/schöner" eine weitere Variable zu initialisieren?
Für Klausur AuD u.ä. gilt: Sofern die Aufgabenstellungs keine Vorgaben zur "Schönheit" enthält, gibt es für Unschönheiten auch keinen Punktabzug (solange Ihr Code noch lesbar und verständlich bleibt, versteht sich).

In "echten" Softwareprojekten sollten Sie der Verständlichkeit wegen hingegen eine neue Variable mit passendem Namen einführen, zum Beispiel so etwas wie akuellerKnoten.

KW

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Alles klar! Vielen Dank für diese Auskunft! Ich schließe gleich meine nächste Frage anschliessen. Ist der folgende Code eine mögliche rekursive Implementierung von der Methode overwriteAll auf einem Ternärbaum? Ich habe eine abweichende Lösung zu der inoffiziellen Musterlösung. Auch kleine Testfälle gehen durch. Aber mehrere Augen sehen ja bekanntlich mehr als nur zwei!

Vielen Dank!

Code: Alles auswählen

public boolean overwriteAll (TreeNode<T> wurzel, <T> ow, <T> tf){

	if (wurzel == null) return false;

	return help (wurzel,ow,tf,0);
}

public boolean help (TreeNode<T> wurzel, <T> ow, <T> tf, int counter){

	if (wurzel == null && counter == 1) return true;

	if (wurzel != null){
	
		if (wurzel.key1.equals(tf)){
		
			wurzel.key1 = ow;
			counter = 1;
		}
		if (wurzel.key2 != null && wurzel.key2.equals(tf)){
			
			wurzel.key2 = ow;
			counter = 1;
		}
		return help (wurzel.left,ow,tf,counter) || help (wurzel.middle,ow,tf,counter) ||
			   help (wurzel.right,ow,tf,counter);
	}
	return false;
}
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben: Ist der folgende Code eine mögliche rekursive Implementierung von der Methode overwriteAll auf einem Ternärbaum?
Was genau soll Ihre Methode leisten?

KW

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Ich habe doch geschrieben, dass ich mich auf die rekursive Methode overwriteAll auf einem Ternärbaum beziehe (Java Übungsblatt Aufgabe 3). Oder meinen sie mit ihrer Frage etwas anderes?
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von Prof. Karsten Weihe »

D'Angelo Russell hat geschrieben:Ich habe doch geschrieben, dass ich mich auf die rekursive Methode overwriteAll auf einem Ternärbaum beziehe (Java Übungsblatt Aufgabe 3). Oder meinen sie mit ihrer Frage etwas anderes?
Ich frage nach, weil ich Ihren Code nicht so ganz mit der Aufgabenstellung zusammenbringe. Wozu brauchen Sie beispielsweise die Variable counter?

KW

Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Re: Java-Übungsaufgaben - Lösungsvorschlag

Beitrag von D'Angelo Russell »

Diese Variable habe ich einfach genommen, um bei einer Überschreibung den Zustand zu ändern. Man hätte ja auch einen boolean nehmen können, der dann von false auf true gesetzt wird. Hier wird diese Variable von 0 auf 1 gesetzt.
I got ice in my veins! 8)

Antworten

Zurück zu „AuD: Programmieraufgaben“