Problem mit LinkedList

[Lissy98]

Hallo,
ich will einen Baum durchsuchen mit Tiefensuche, um festzustellen ob ein Knoten doppelt vorkommt, also nicht der Wert des Knotens sondern die Referenz. Das wollte ich mit Tiefensuche und LinkedList lösen, indem ich alle schon "besuchten" Knoten abspeichere und immer durchschau ob mein aktueller Knoten schon in dieser Liste vorhanden ist.

private boolean isTreeH (Node b, LinkedList <Node> h){

for (int i = 0; i < h.size(); i++){

    if (h.get(i)== b){
        return false;}
}
   
    h.add(b);
   
    if(b.right != null){
    isTreeH (b.right, h);
    }
    if (b.left != null){
        isTreeH (b.left, h);
    }
    return true;}

Aus irgendeinem Grund speichert er zwar alle Knoten ein, beim durchsuchen dieser Liste findet er aber doppelte nicht (also den gleichen Knoten zweimal besucht)....
Vielen Dank für Hilfe im Voraus!!!

Lieber Grüße

 

[JCODA]

Ich verstehe nicht ganz, warum du bei einem "Baum" dich um doppelte Elemente kümmerst. Ein Baum hat nunmal keine Zykel, deshalb gibt es auch nicht mehrere Wege um gleiche Knoten zu erhalten.

Bemerkung: du verwendet die Rückgabe von isTreeH innerhalb der ifs nicht, ist das gewollt?

 

[Lissy98]

Ja das Problem ist dass die Bäume die wir bekommen, leider zum Teil keine Bäume sondern eigentlich eher Graphen sind.... Also eigentlich ist es ein Test ob es ein Baum ist

Ich dachte dass wenn ich da bei jedem return schreibe in den ifs, des dann wen ein Knoten einen rechten und einen linken Nachfolger hat, nur der eine besucht wird.... Oder nicht?

 

[JCODA]

das ist denke ich richtig da nicht "return" zu schreiben, aber vielleicht sollte man den Wert nicht ignorieren. Wenn man die beiden Werte von isTree mit oder verknüpft und dies zurück gibt, vielleicht passiert dann das, was du möchtest ^^ (dann brauchst man aber noch eine positive Abbruchbedingung, etwa falls beide Kinder leer sind, dann ist das ja nur ein Knoten und deswegen auch ein baum, also falls beide null sind, wird true zurückgegeben )