Tiefensuche im binären Baum

[hawkeye78]

Hallo,

ich hab ein kleines Problem, ich versuche auf einem binären Baum eine Tiefensuche zu implementieren. Hierbei soll zunächst immer der Linke Knoten besucht werden, bis ein Blatt erreicht worden ist. Danach soll ein Backtracking erfolgen und die passierten rechten Teilbäume aufgesucht werden, in welchen dann wieder die linken Kanten besucht werden soll bis ein Blatt erreicht worden ist usw.
Meine Implementierung des Baumes schaut im moment so aus, das die Knoten als Objekte gespeichert werden. Ein Knoten enthält hierbei zwei Referenzen auf den linken bzw. rechten Teilbaum. Das eigentliche gespeicherte Datum, sowie ein boolean der auf False steht falls der Knoten noch nicht betrachtet worden ist, und auf true falls der Knoten besucht worden ist
Mein Code für die Tiefensuche schaut im moment so aus:

// Aufruf der Tiefensuche mit dem Wurzeldatum
	public void dfs()
	{
		this.dfs(head);
	}
	
	public void dfs(Knoten akt)
	{
		// Falls der Knoten nocht nicht betrachtet worden ist
		if(!akt.getVisited())
		{
			akt.isVisited();  // Der Knoten wurde somit besucht
			System.out.print("Betrachteter Knoten "+akt.getValue());
			
			// Ausgabe des Linken Kindes, falls vorhanden
			if(akt.getLeftChild()!=null)
			{
				System.out.println();
				System.out.println("linkes Kind: "+akt.getLeftChild().getValue());
			}
			
			// Ausgabe des rechten Kindes falls vorhanden
			if(akt.getRightChild()!=null)
			{
				System.out.println("rechtes Kind: "+akt.getRightChild().getValue());				
			}
			
			if(akt.getLeftChild()==null && akt.getRightChild()==null)
			{
				System.out.println(": Blatt");
			}
			System.out.println();
		}

		// Besuch des linken Kindes falls es noch nicht betrachtet worden ist
		if(akt.getLeftChild()!=null && akt.getLeftChild().getVisited()==false)
		{
			this.dfs(akt.getLeftChild());
		}
		// Besuch des rechten Kindes falls noch nicht betrachtet worden ist
		else if(akt.getRightChild()!=null && akt.getRightChild().getVisited()==false)
		{
			this.dfs(akt.getRightChild());
		}
		// Backtracking
		else if(akt.getLeftChild()==null && akt.getRightChild()==null)
		{
			return;
		}
	}

und ich wäre sehr dankbar wenn evtl. mal jemand über den Quellcode schauen kann, und mir sagen kann wo mein Fehler liegt. Da ich im moment nur an der "äußeren" linken Kante bis zum Blatt laufe und dort die Tiefensuche abbricht bzw. dann das Backtracking beginnt und die rechten Teilbäume gar nicht aufgesucht werden.

 

[Beni]

      // Besuch des linken Kindes falls es noch nicht betrachtet worden ist
      if(akt.getLeftChild()!=null && akt.getLeftChild().getVisited()==false)
      {
         this.dfs(akt.getLeftChild());
      }
      // Besuch des rechten Kindes falls noch nicht betrachtet worden ist
      else if(akt.getRightChild()!=null && akt.getRightChild().getVisited()==false)
      {
         this.dfs(akt.getRightChild());
      }
      // Backtracking
      else if(akt.getLeftChild()==null && akt.getRightChild()==null)
      {
         return;
      }

Du hast ein paar else's zuviel. "Wenn das linke da ist, dann besuche es, sonst besuche das rechte (falls es existiert)" steht bei dir.

Das letzte if, mit dem return drin, ist überflüssig. Zurückkehren tut man immer.

 

[hawkeye78]

Hallo Beni,

vielen Dank für deine Antwort, ich habe nun den Quellcode ein klein bißchen modifziert, so das er wie folgt aussieht

		// Besuch des linken Kindes falls es noch nicht betrachtet worden ist
		if(akt.getLeftChild()!=null && akt.getLeftChild().getVisited()==false)
		{
			this.dfs(akt.getLeftChild());
		}
		// Besuch des rechten Kindes falls noch nicht betrachtet worden ist
		else if(akt.getRightChild()!=null && akt.getRightChild().getVisited()==false)
		{
			this.dfs(akt.getRightChild());
		}
				
		return;

Leider verändert das nichts an der Ausgabe. Vielleicht bin ich einfach nur blind
Viele grüsse
Dan

Edit:
Hat sich erledigt ich muß aus dem if...else if.... Statement zwei If-Abfragen man....dann geht es...