Seite 2 von 5

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 13. Sep 2016 22:01
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.

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 14. Sep 2016 12:01
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.

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 14. Sep 2016 12:23
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:

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 14. Sep 2016 21:14
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.

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 14. Sep 2016 21:21
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

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 15. Sep 2016 03:34
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

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 17. Mär 2017 11:08
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!

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 17. Mär 2017 12:15
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

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 21. Mär 2017 14:34
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;
}
 

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 21. Mär 2017 16:14
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

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 22. Mär 2017 16:15
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;
}

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 22. Mär 2017 20:25
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

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 22. Mär 2017 21:04
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?

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 22. Mär 2017 21:50
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

Re: Java-Übungsaufgaben - Lösungsvorschlag

Verfasst: 22. Mär 2017 21:54
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.