검색 Double Linked List Java 재귀 적으로

Question

용어로 Java에서 이중 연결 목록을 검색하고 발견되면이를 반환하려고합니다. 여기 내 코드는 지금까지 있습니다 :

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; 
} 

내 알고리즘은 기본적으로 님의 요소가있는 경우는 검색어

일치하는 경우 노드는 널 (null)

점검하지

• 동안 그는 맞습니다. 재귀로 스캔하십시오.
• 두 항목 모두 null이고 항목이 존재하지 않습니다.

내 질문에 편집, 미안 : 내가 어디로 잘못 갔는지 이해하는 데 문제가 아래쪽 수준을 검색하고 얻을 수 없습니다.

도움이 될 것입니다.

Answer 1

왼쪽으로 이동하고 모든 오른쪽 노드를 반복적으로 찾으므로 알고리즘이 동일한 노드를 여러 번 계산한다고 생각합니다.

노드를 시작 노드에서 양방향으로 검색하여 노드를 찾을 수 있습니다.

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); 
    } 
} 

또한 Node.left 및 Node.right의 유형은 노드 여야한다고 생각합니다.

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

Answer 2

귀하의 질문에 대한 의견에 동의해야합니다. 그러나 null 연결 요소가 허용되지 않는 이중 연결 목록에서 재귀 검색을 구현하는 방법을 찾고 있다고 가정합니다. 다른 대답은 이미 언급했듯이, Node는 노드 유형의 하위 유형으로 가정합니다. 사실, 저는 아래의 예에서 그것을 대체 할 것입니다.

이중 연결 목록을 구현하고 재귀 자체에 대해 오해가있는 것처럼 보이므로 압축 된 있지만 실행중인 예제를 제공합니다.

제시하는 코드에 재귀의 종료 조건이 없습니다. 불행히도, ikicha의 솔루션에도 해당됩니다. 이를 달성하기위한 한 가지 방법은 도우미 메서드를 사용하여 invariant (예 : start 요소) 또는 카운터를 반복의 한 반복에서 다음 반복으로 전달하는 것입니다.

예에서 행 node = node.left은 아무 효과가 없습니다. 양방향으로 검색을 수행하고 싶다면 (ikicha가 스케치 한 것처럼) 방향이 중요한 이유에 대해 관심을 가질 것입니다.

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"); 
} 
}