NullPointerException bei rekursiven Funktionsaufruf

[hawkeye78]

Hallo,

ich hänge im moment bei einem Algorithmus der einen binären Baum durchsuchen soll, und null zurückgeben soll, wenn der Knoten gefunden wird. Wenn ich diesen Algorithmus als schleife implementiere läuft er, allerdings liefert das Programm einen Null Pointer Exception wenn ich es rekursiv implementiere.

Mein Quellcode schaut im moment so aus

public class Baum

{

	public Knoten search(int x, Knoten aktuellerKnoten)

	{

		if(x<aktuellerKnoten.getValue() && aktuellerKnoten.getNextLeft()!=null)

		{

			search(x,aktuellerKnoten.getNextLeft());

		}


		if(x>aktuellerKnoten.getValue() && aktuellerKnoten.getNextLeft()!=null)

		{

			search(x,aktuellerKnoten.getNextRight());			

		}


		if(x==aktuellerKnoten.getValue())

		{

			return null;

		}


		return aktuellerKnoten;

	}


	public void insert(int i)

	{

		Knoten aktuellerKnoten;

		Knoten neu=null;


		// Überprüfung auf einen leeren Baum

		if(first==null)

		{

			neu=new Knoten(i);

			setFirst(neu);

		}

		else

		{

			// Suche ob der Knoten bereits im Baum existiert

			aktuellerKnoten=search(i, first);

}


	public class Knoten

	{

		private int wert;

		private Knoten nextLeft;

		private Knoten nextRight;


		public Knoten(int i)

		{

			wert=i;

			nextLeft=null;

			nextLeft=null;

		}


		public int getValue()

		{

			return wert;

		}


		public Knoten getNextLeft()

		{

			return nextLeft;

		}


		public Knoten getNextRight()

		{

			return nextRight;

		}


		public void setNextLeft(Knoten e)

		{

			nextLeft=e;

		}

}

}

Der Fehler tritt offenbar in der Methode "search" auf, aber leider habe ich keine Ahnung warum, ich wäre daher über einen kleinen Hinweis, was ich noch an dem Quellcode modefizieren muß sehr dankbar.

Viele Grüsse

Dan

[Bubble]

Der Fehler entsteht beim Aufruf von getValue() auf einem nicht vorhandenne Objekt.

Wenn der Wert in einem Teilbaum nicht enthalten ist, wird dieser Unterbaum von Deinem Programm komplett durchsucht, da Du immer weiter getNextLeft() und getNextRight() aufrufst. Allerdings kommst Du dabei irgendwann an den Blättern an und dann geben Dir diese Funktionen den Wert null zurück. Damit gehst Du dann trotzdem in die nächste Iteration und rufst ohne auf null zu prüfen wieder getValue() auf, was nun fehlschlagen muss.

Abgesehen davon solltest Du Deine Rückgabewerte überprüfen, auf den ersten Blick schaut es für mich so aus, als ob Du etwas anderes beabsichtigst, als Du programmiert hast.

[hawkeye78]

Hallo Bubble,

erst einmal möchte ich mich für dein Posting bedanken, aber der Fehler ist viel Profaner und ich schäme mich fast wegen so einer nichtigkeit hier gepostet zu haben:

public class Baum

{

public Knoten search(int x, Knoten aktuellerKnoten)

{

if(x<aktuellerKnoten.getValue() && aktuellerKnoten.getNextLeft()!=null)

{

search(x,aktuellerKnoten.getNextLeft());

}


if(x>aktuellerKnoten.getValue() && aktuellerKnoten.getNextLeft()!=null) <---

{

search(x,aktuellerKnoten.getNextRight());

}

Ich habe statt einmal nach links und einmal nach Rechts zu verzweigen in beiden If-Statements nach Linksverzweigt bzw. abgefragt ob ein linkes Kind existiert. Nachdem ich die Bedingung für das If-Statement angepaßt habe lief das Programm ohne Probleme.

Noch einmal vielen Dank für deine Hilfe.

Viele Grüsse

Dan