Java-Übungsblatt: isAscending auf Ternärbaum

mdk
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 18. Apr 2014 10:33

Java-Übungsblatt: isAscending auf Ternärbaum

Beitrag von mdk » 22. Sep 2017 20:12

Hallo,

hat jemand diese Aufgabe auch bearbeitet und kann evtl. mal über meinen Code schauen, ob das so richtig ist? Bin mir nämlich nicht sicher, ob das wirklich die richtige Vorgehensweise ist oder ich irgendwelche Sonderfälle vergessen habe. Insbesondere bin ich mir nicht sicher, ob ich die Vergleiche mit den zwei Keys richtig mache, also ob das überhaupt die richtige Vorgehensweise ist.

Parameter root soll auf einen Ternärbaum verweisen. Habe die Aufgabe rekursiv gelöst.

Code: Alles auswählen

boolean isAscending(TreeNode<T> root, Comparator<T> cmp) {
	if(root == null) //Abbruchbedingung 
		return true;
	
	int cmpResult1;
	int cmpResult2;

	if(root.left != null) {
		cmpResult1 = cmp.compare(root.left.key1, root.key1);
		cmpResult2 = cmp.compare(root.left.key2, root.key1);
		if(cmpResult1 > 0 || cmpResult2 > 0)
			return false;
	}
	if(root.middle != null) {
		cmpResult1 = cmp.compare(root.middle.key1, root.key1);
		cmpResult2 = cmp.compare(root.middle.key2, root.key1);
		if(cmpResult1 < 0 || cmpResult2 < 0)
			return false;
		cmpResult1 = cmp.compare(root.middle.key1, root.key2);
		cmpResult2 = cmp.compare(root.middle.key2, root.key2);
		if(cmpResult1 > 0 ||cmpResult2 > 0)
			return false;
	}
	if(root.right != null) {
		cmpResult1 = cmp.compare(root.right.key1, root.key2);
		cmpResult2 = cmp.compare(root.right.key2, root.key2);
		if(cmpResult1 < 0 || cmpResult2 < 0)
			return false;
	}
	
	return (isAscending(root.left, cmp) && isAscending(root.middle, cmp) && isAscending(root.right, cmp));
}

nozyde
Erstie
Erstie
Beiträge: 20
Registriert: 7. Jun 2017 21:22

Re: Java-Übungsblatt: isAscending auf Ternärbaum

Beitrag von nozyde » 23. Sep 2017 01:01

Laut Java Übungsblatt gilt:
Bei Knoten von ternären Bäumen ist key1 niemals null, und es ist key2==null genau dann, wenn right==null.
Du greifst hier bereits auf key2 zu:

Code: Alles auswählen

	if(root.left != null) {
		cmpResult1 = cmp.compare(root.left.key1, root.key1);
		cmpResult2 = cmp.compare(root.left.key2, root.key1);
Es könnte aber sein, dass root.left.right == null ist, dann würdest du hier eine NullpointerException bekommen. Das solltest du überall prüfen, bevor du auf key2 zugreifst.

mdk
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 18. Apr 2014 10:33

Re: Java-Übungsblatt: isAscending auf Ternärbaum

Beitrag von mdk » 23. Sep 2017 11:00

Ah! Ja, danke für den Hinweis. Daran habe ich nicht mehr gedacht. Das macht den Code natürlich ziemlich hässlich.

Antworten

Zurück zu „Archiv“