Binary Search tree

computernerds

Hallo,

kann mir mal einer sagen warum das so nicht geht.
Ich uebergeb einen root Knoten und pruefe dann ob
es sich um einen Binary Search Tree handelt.
Aber mit dem return false das funktioniert leider nicht.
Die Ausgabe wird aber gemacht.

public boolean checkIfBST(Node node)
	{
		if(node==null)
			return true;

		if(node.left !=null)
		{
			if(node.left.value > node.value)
			{
				System.out.println("Fehler"); // wird ausgegeben
				return false;//kommt im main nicht an
			}
		}

		if(node.right !=null)
		{
			if(node.right.value < node.value)
			{
				return false;
			}
		}

		checkIfBST(node.left);
		checkIfBST(node.right);
		return true;

	}

//Main Programm , Aufruf der Methode 
		if(checkIfBST(rootNode) == false)
		{
			System.out.println("Kein BST");
		}

SG1

Du ignorierst den Rückgabewert der rekursiven Aufrufe.

computernerds

return false. Das ist doch der Rueckgabewerte. Und in der main Funktion frag ich == false ab.

Klar ich hab nen Denkfehler drin.
Aber wo?? Steh grad am Schlauch..

SG1

Zeile 23/24.

computernerds

hm aber wenn er doch in Zeile 11 reingeht, dann gibt er doch false zurueck und Zeile 23/24 werden gar nicht ausgefuert ??

ODER werden die Rueckgabewerte alle auf dem Stack gespeichert und es kommt nur ein einziger Rueckgabewert in der main an obwohl vielleicht tausende in der rekursiven Funktion erstellt wurden ??

Erst wenn die Funktion komplett abgearbeitet ist, dann wird etwas an die main Funktion zurueckgegeben. Die return Werte zwischendrin die kommen nie in der main an. Oder?

Tobiking2

computernerds schrieb:

Erst wenn die Funktion komplett abgearbeitet ist, dann wird etwas an die main Funktion zurueckgegeben. Die return Werte zwischendrin die kommen nie in der main an. Oder?

Rückgabewerte kommen immer da an wo die Funktion aufgerufen wird. In main wird deine Funktion nur für den Wurzelknoten aufgerufen. Warum sollten dort die Ergebnisse aller Kinderknoten ankommen? In Zeile 23/24 bekommst du aber die Ergebnisse der Kinderknoten. Die kannst du verwenden, um das Ergebnis des Wurzelknoten abhängig vom Ergebnis der Kinder zu machen. Da sich das weiterführt, sind die Kinder dann auch abhängig von deren Kindeskindern etc. und du deckst den ganzen Baum ab.

computernerds

ah ok danke.
Aber wie muesste ich denn mein Programm oben umschreiben,
damit ich auch false zurueckgeliefert bekomme und mich nicht auf die print Ausgabe "Fehler" in Zeile 10 verlassen muss ?

Das hab ich gerade bei stackoverflow gefunden.
Kommt hier 0 oder 10 raus ?

int count = 0; 
		for(int i=0; i < 10; ++i) 
			count = count++; 

		System.out.println(count);

checkIfBST(node.left); // du berechnest den linken Teilbaum
checkIfBST(node.right); // und den rechten Teilbaum
return true; // und ignorierst das Ergebnis, da du immer true zurückgibst

du berechnest für die Kindknoten zwar checkIfBST, verwirfst aber das Ergebnis, da du mit return true immer "ok" sagst.

Du musst das berechnete Ergebnis von den Kindknoten zurückgeben:
Also return checkIfBST(node.left) OP checkIfBST(node.right);

Du musst noch entscheiden, welchen Operator OP du verwenden willst: UND, ODER, ...