Rekursives suchen im TreeMenu

[Milo]

Hallo,

ich habe eine Methode, die das Baummenü nach einem Eintrag durchsucht und mir den Knoten zurück geben soll. Leider läuft die Methode "zu weit" und gibt immer null zurück.

	private TreeNode getTreeNodeByName(TreeNode node, String nodeName) {
		System.out.println("SUCHE: "+nodeName+"  -->  " +  node.toString()+"  "+node.toString().equals(nodeName));
		if (node.toString().equals(nodeName))
			return node;
		else {
			for (int i=0; i<node.getChildCount(); i++)
				this.getTreeNodeByName(node.getChildAt(i), nodeName);
			return null;
		}
	}

Wenn er den Eintrag findet, bricht die Methode nicht ab, sondern durchläuft weiterhin den gesamten Baum. Warum endet sich nicht beim return?

Gruß Micha

 

[Wildcard]

this.getTreeNodeByName(node.getChildAt(i), nodeName);

Hier musst du prüfen ob !=null und dann gegebenenfalls returnen

 

[SlaterB]

> for (int i=0; i<node.getChildCount(); i++)
> this.getTreeNodeByName(node.getChildAt(i), nodeName);

in diesem Teil findet sich gar kein return, ziemlich kaputt,

ansonsten wird ein return in Zeile 4 selbstverständlich ausgeführt, falls Zeile 3 true ergibt,

bei der Frage und den Ungenauigkeiten im Code sind alle möglichen Fehler und falsche Interpretationen denkbar..

 

[Milo]

Hi,

ganz ideal scheint es noch nicht zu sein:

	private TreeNode getTreeNodeByName(TreeNode node, String nodeName) { 
		//System.out.println("SUCHE: "+nodeName+"  -->  " +  node.toString()+"  "+node.toString().equals(nodeName)); 
		if (node.toString().equals(nodeName)) {
			System.out.println("1. TREFFER! " +node);
			return node; 
		}
		else { 
			for (int i=0; i<node.getChildCount(); i++) {
				TreeNode newNode = this.getTreeNodeByName(node.getChildAt(i), nodeName);
				if (newNode != null) {
					if (newNode.toString().equals(nodeName)) {
						System.out.println("2. TREFFER! "  +newNode);
						return newNode;
					}
//					else
//						this.getTreeNodeByName(newNode, nodeName);
				}
					
			}
		} 
		return null;
	}

Die Ausgabe ist:

1. TREFFER! Neupunkte
2. TREFFER! Neupunkte
Neupunkte
1. TREFFER! 1. Winkelgruppe
2. TREFFER! 1. Winkelgruppe
2. TREFFER! 1. Winkelgruppe
1. Winkelgruppe

Das Menü sieht wie folgt aus:

Root
 |--Neupunkte
 |   |----1DPunkte
 |   |----2DPunkte
 |
 |--Winkel
    |----1. Winkelgruppe

Neupunkte ist also ein Knoten, der direkt nach dem Wurzelelement kommt und weitere Kinder hat. Die 1. Winkelgruppe ist hingegen in der dritten (letzten) Ebene und hat keine Kinder mehr.

System.out.println( getTreeNodeByName(this.root, "Neupunkte") );
System.out.println( getTreeNodeByName(this.root, "1. Winkelgruppe") );

Warum werden die "Treffer" so oft ausgegeben? Sollte nicht beim ersten jeweils schon schluß sein?

Micha

 

[SlaterB]

in Zeile 9 rufst du rekusiv die Methode nocchmal auf
> TreeNode newNode = this.getTreeNodeByName(node.getChildAt(i), nodeName);

dann wird für eine untere Ebene irgendwann was gefunden, eine Ausgabe gemacht und der Knoten zurückgegeben,
oder es kommt null zurück

nun bist du wieder in einer höheren Rekursionsstufe am Ende von Zeile 9, quasi in Zeile 10,
in newNode steht nun entweder null (weitermachen) oder der richtige Knoten (dann gabs schon eine Ausgabe),
und was machst du in Zeile 12? gibst nochmal Treffer aus, obwohl doch garantiert schon mindestens einmal Treffer ausgegeben wurde

Zeile 12 kann komplett weg, Zeile 11 und 14-16 sind auch ohne Bedeutung, stören bisher aber nicht

 

[Milo]

Hi,

sei mir nicht böse aber verszanden habe ich nichts von dem was Du beschrieben hast. ;-)
Ich versuch nachher noch mal...

Gruß Micha

Nachtrag: Deine Änderungen habe ich schon verszanden:

	private TreeNode getTreeNodeByName(TreeNode node, String nodeName) { 
		//System.out.println("SUCHE: "+nodeName+"  -->  " +  node.toString()+"  "+node.toString().equals(nodeName)); 
		if (node.toString().equals(nodeName)) {
			System.out.println("1. TREFFER! " +node);
			return node; 
		}
		else { 
			for (int i=0; i<node.getChildCount(); i++) {
				TreeNode newNode = this.getTreeNodeByName(node.getChildAt(i), nodeName);
				if (newNode != null) 
					return newNode;					
			}
		} 
		return null;
	}

Nur warum ist die Bedingung in der Schleife bzw. das, was in der Bedingung steht korrekt?

 

[SlaterB]

hier noch was zum nachdenken

public class Test
{

    public static void main(String[] args)
        throws Exception
    {
        rek(1, 4);
    }

    public static boolean rek(int tiefe, int k)
    {
        if (tiefe == k)
        {
            System.out.println("k == tiefe, Treffer in Ebene " + tiefe);
            return true;
        }
        else
        {
            boolean erg = rek(tiefe + 1, k);
            if (erg)
            {
                System.out.println("Treffer-Erwähnungs-Wiederholung in Ebene " + tiefe);
                return true;
            }
            return false;
        }
    }
}

->

k == tiefe, Treffer in Ebene 4
Treffer-Erwähnungs-Wiederholung in Ebene 3
Treffer-Erwähnungs-Wiederholung in Ebene 2
Treffer-Erwähnungs-Wiederholung in Ebene 1

 

[Milo]

Hallo,

die Wiederholungen kommen vermutlich, weil die Methode noch drei weitere mal aufgerufen wird und alle bis zum Ende abgearbeitet werden. Alle Aufrufe erreichen irgendwann den Status true und enden. Danke fürs Beispiel, klarer ist es trotzdem nicht geworden.

Gruß Micha

 

[SlaterB]

nochmal: wenn du in Zeile 9 vom rekursiven Aufruf einen Node != null erhälst, dann heißt das doch, dass weiter unten/ hinten/ vorher etwas gefunden wurde,
damit zwangsläufig irgendwann Treffer1 ausgegeben wurde, denn nur Zeile 5 kann einen Node != null zurückgeben,
was ist an diesem Punkt nicht zu verstehen?

falls doch verstanden dann darfst du nun einfach nicht mehr NOCHMAL Treffer ausgeben,
fertig

 

[Milo]

Hi,

so wie ich es zuletzt gepostet habe, funktioniert es ja nun. Keine Ahnung, ob das nun das optimum ist. Was daran nicht zu verstehen ist, weiß ich leider nicht; ggf. sind Deine Erklärungen für mich nicht so didaktisch und nachvollziehbar, wie es für Dich erscheint - wie gesagt, ich weiß es nicht.

Im Moment habe ich das Gefühl, es wird doppelt das Ergebnis zurückgegeben und nicht nur bei der eigentlichen Prüfung:

      if (node.toString().equals(nodeName)) { 
         System.out.println("1. TREFFER! " +node); 
         return node; 
      }

Hier erwarte ich das Objekt, was ich auch suche. Letztlich bekommen werde ich aber das, was in der Schleife zurückgegeben wird. Das aus der Schleife stammt nun wiederum aus der Bedingung. Vll muss das ja auch so sein, wer weiß ;-)

Schönen Abend und vielen Danl noch mal
Micha

 

[Milo]

Hi,

Dein Beispiel würde ich so ändern:

public class Test
{

    public static void main(String[] args)
        throws Exception
    {
        rek(1, 4);
    }

    public static boolean rek(int tiefe, int k)
    {
        if (tiefe == k)
        {
            System.out.println("k == tiefe, Treffer in Ebene " + tiefe);
            return true;
        }
        else
            return rek(tiefe + 1, k);
    }
}

Gruß Micha