Suche Double Linked List Java rekursiv

Question

Ich versuche, eine doppelt verknüpfte Liste in Java für einen Begriff zu suchen, und geben Sie es zurück, wenn gefunden. Hier ist mein Code so weit:

private class Node { 
    public String content; 
    public Node up; 
    public Node left; 
    public Node right; 
} 

private Node searchList(String term, Node node) { 
    while (node != null) { 
     System.out.print(node.name + " - "); //To see process 

     if (node.content.equals(term)) { 
      return node; 
     } else if (node.right != null) { 
      return searchList(term, node.right); 
     } 

     node = node.left; 
    } 

    return null; 
} 

Mein Algorithmus ist im Grunde:

• Während der Knoten ist nicht null
• Überprüfen Sie, ob es den Suchbegriff passt
• Wenn es ein Element er richtig, scanne das mit Rekursion
• Beide Punkte sind jetzt null, Artikel ist nicht vorhanden

Mit meiner Frage bearbeiten, tut mir leid: Ich kann es nicht zu unteren Ebenen suchen und habe Schwierigkeiten zu verstehen, wo ich falsch gelaufen bin.

Jede Hilfe wäre willkommen!

Answer 1

Ich denke, dass Ihr Algorithmus denselben Knoten mehrmals berechnet, weil Sie nach links gehen und alle rechten Knoten der linken wiederholt finden.

Sie können Knoten durch Suche zwei Richtungen jeweils von Startknoten finden.

private Node internalSearchList(String term, Node node, int direction) { 
    if (node == null) { 
    return null; 
    } 
    if (term.equals(node.content)) { 
    return node; 
    } else { 
    return internalSearchList(term, direction == 0 ? node.left : node.right, direction); 
    } 
} 

private Node searchList(String term, Node node) { 
    // search to left side 
    Node result = internalSearchList(term, node, 0); 
    if (result != null) { 
    return result; 
    } else { 
    return internalSearchList(term, node, 1); 
    } 
} 

Und auch ich denke, der Typ von Node.left und Node.right muss Node sein.

private class Node { 
    public String content; 
    public Node up; 
    public Node left; 
    public Node right; 
} 

Answer 2

Ich muss den Kommentaren zustimmen, dass Ihre Frage unklar ist. Ich nehme jedoch an, dass Sie nur nach einer Möglichkeit suchen, eine rekursive Suche in einer doppelt verknüpften Liste zu implementieren (in der Nullelemente nicht zulässig sind). Wie die andere Antwort bereits erwähnt, nehme ich an, dass Typ Page ein Untertyp von Node ist. In der Tat werde ich es in meinem Beispiel unten ersetzen.

Da es scheint, einige Irrglaube über die Implementierung einer doppelt verketteten Liste und über Rekursion selbst zu sein, werde ich ein kondensiertes aber laufendes Beispiel geben.

Der Code, den Sie präsentieren, fehlt eine Abbruchbedingung für die Rekursion. Das gilt leider auch für die Lösung von ikicha. Ein Weg (unter anderem), dies zu erreichen, besteht darin, eine Hilfsmethode zu verwenden, um eine Invariante (z. B. das Startelement) oder einen Zähler von einer Iteration der Rekursion zur nächsten zu übergeben.

Die Zeile node = node.left in Ihrem Beispiel hat keine Auswirkung. Wenn Sie eine Suche in beide Richtungen (wie Ikicha skizziert) erreichen möchten, würde mich interessieren, warum die Richtung für Sie wichtig ist.

public class DoubleLinked { 

private Node first; 
private Node last; 
private int size; 

private class Node { 
    public String content; 
    public Node left; 
    public Node right; 

    public Node(String content) { 
     this.content = content; 
    } 
} 

private void addElement(Node addedNode) { 
    if (first == null) { 
     first = addedNode; 
     last = addedNode; 

    } else { 
     last.right = addedNode; 
     addedNode.left = last; 
     addedNode.right = first;    
     last = addedNode; 
    } 
    size++; 
} 

private Node searchList(String term, Node node) { 
    int tries = 0; 
    if (node != null) { 
     return searchHelper(term, node.right, tries); 
    } 
    return null; 
} 

private Node searchHelper(String term, Node node, int tries) { 
    if (node == null || tries >= size) { 
     return null; 
    } 

    if (node.content.equals(term)) { 
     return node; 
    } else { 
     return searchHelper(term, node.right, tries); 
    } 
} 

public static void main(String[] args) { 
    DoubleLinked list = new DoubleLinked(); 

    list.addElement(list.new Node("first")); 
    Node startNode = list.new Node("second"); 
    list.addElement(startNode); 
    list.addElement(list.new Node("third")); 
    list.addElement(list.new Node("forth")); 

    Node r = list.searchList("forth", startNode); 
    System.out.println(r!=null?r.content:"term not found"); 
} 
}