Seite 1 von 1

Java-Übungsblatt: isAscending auf Ternärbaum

Verfasst: 22. Sep 2017 20:12
von mdk
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));
}

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

Verfasst: 23. Sep 2017 01:01
von nozyde
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.

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

Verfasst: 23. Sep 2017 11:00
von mdk
Ah! Ja, danke für den Hinweis. Daran habe ich nicht mehr gedacht. Das macht den Code natürlich ziemlich hässlich.