정렬되지 않은 이진 트리에서 문자열 검색

이진 트리에 저장된 문자열을 검색하려면 어떻게해야하는지 확신 할 수 없습니다. 필자는 검색 방법을 작성했지만 필자는 그것을 전달할 내용을 이해하지 못합니다. 트리에 추가하기 전에 문자열을 검색해야합니다. 발견되면 새로운 노드를 추가하는 대신 노드 객체 내의 카운터를 증가시켜야합니다. 나무는 그럭저럭 분류되지 않는다.정렬되지 않은 이진 트리에서 문자열 검색

내 질문에 추가하기 전에 어떻게 검색합니까?

public Node treeSearch(String s, TreeNode root){ 

    if(root.toString().equals(s)){ 

     return root; 
    } 
    if(left != null){ 

     left.treeSearch(s, root.left); 
     if(root.toString().equals(s)){ 
      return root; 
     } 
    } 
    if(right != null){ 

     right.treeSearch(s, root.right); 
     if(root.toString().equals(s)){ 
      return root; 
     } 
    }else{ 
      return null; 
      } 
}

System.out.println("Enter string to be stored"); 
stringValue = k.nextLine(); 
if (theString.isEmpty() == true) { 
    node.add(stringValue, count); 
} else { 
    // I am not sure what to do here 
    // How do I send the string to my search method? 
    stringValue.treeSearch(); 
}

나는이에 대한 검색 방법을 업데이트합니다.

public Node treeSearch(String s, Node root){ 

if(root.toString().equals(s)){ 

    return root; 
    } 
    if(left != null){ 

     left.treeSearch(s, root.left); 
     return root; 
    } 
    if(right != null){ 

     right.treeSearch(s, root.right); 
      return root; 
    }else{ 
     return null; 
    } 
}

출처

2013-04-01 Raymond G

문자열을 찾고 있으므로 원하는 문자열을 전달하십시오. 'treeSearch()'메소드는 어디에 구현 되었습니까? –

'treeSearch' 메쏘드의 서명에 따라 검색을 위해'String'을, 트리의 루트를위한'Node' 객체를 전달해야합니다. –

왼쪽 및 오른쪽 하위 트리를 검색하는 방식에 버그가 있습니다. 예를 들어 :

if (left != null) { 
    left.treeSearch(s, root.left); 
    if (root.toString().equals(s)) { 
     return root; 
    } 
}

그래서 ... 당신이 왼쪽 서브 트리를 검색하지만 검색의 결과를 무시하고 다시 ... root에 대해 s을 비교합니다.

오른쪽 하위 트리에 대해 동일한 패턴이 반복됩니다.

(이것은 "학습 운동"냄새 때문에, 내가 수정을 알아 내기 위해 당신을 떠날 수 있습니다.)

을

는 이진 트리의 요소를 주문하지 않는 경우, 그런 말로 미루어 보아, , 그것은 데이터 구조로서 거의 쓸모가 없다. 목록이나 배열에 요소를 저장하는 것이 좋습니다. ( treeSearch의 복잡성은 목록 또는 배열 검색과 마찬가지로 O(N)입니다.)

출처

2013-04-01 14:20:15

@ user2054868 - 뭐가? –

나는 수색을 편집했다. –

아니요. searchTree 메서드는 발견 한 요소가 포함 된 노드를 반환해야합니다. 그런 식으로 문제를 편집하면 ** 나쁜 생각을했습니다 **. 이제 대부분의 사람들은 원래의 질문에 대해 알지 못할 것입니다. –

정렬되지 않은 이진 트리에서 문자열 검색

답변

관련 문제