Binary Search tree



  • 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");
    		}
    


  • Du ignorierst den Rückgabewert der rekursiven Aufrufe.



  • 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..



  • Zeile 23/24.



  • 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?



  • 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.



  • 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, ...