이진 트리에서 노드의 경로를 반복적으로 찾는 것

Question

검색중인 노드가 정렬되지 않은 이진 트리에 있음을 알고 있지만 재귀 호출을 통해 내 경로를 다시 전달하는 방법을 알 수 없습니다. 내 두 가지 기능 : 하나는 특정 노드에 대한 경로를 찾고, 다른 하나는 모든 노드에 대한 경로 문자열을 반환합니다. 0은 왼쪽 경로가 취해지고 1이 오른쪽임을 나타냅니다.

private static String getAllPaths(final BinaryNodeInterface<Character> root) 
{ 
    // TO DO 
    String path = ""; 
    String returnStr = ""; 
    return getAP(root, path, returnStr); 
} 

private static String getAP(BinaryNodeInterface<Character> root, String path, 
     String returnStr) 
{ 
    returnStr += "" + root.getData() + " " + path + "\n"; 
    if(root.hasLeftChild()) 
     getAP(root.getLeftChild(), path.concat("0"), returnStr); 
    if(root.hasRightChild()) 
     getAP(root.getRightChild(), path.concat("1"), returnStr); 

    return returnStr; 
} 

private static String getPathTo(final BinaryNodeInterface<Character> root, char c) 
{ 
    // TO DO 
    String path = ""; 
    if(root.getData() == c) 
     return path; 

    if(root.hasLeftChild()) 
    { 
     String s = getPathTo(root.getLeftChild(), c); 

     if(s != null) 
     { 
      path += "0"; 
      path += s; 
      return path; 
     } 
    } 

    if(root.hasRightChild()) 
    { 
     String s = getPathTo(root.getRightChild(), c); 

     if(s != null) 
     { 
      path += "1"; 
      path += s; 
      return path; 
     } 
    } 

    return null; 
} 

나는 재귀에서 끔찍하다. 그래서 어떤 도움도 크게 감사하겠습니다. 나는 모든 것을 작동하도록했습니다. 위의 코드는 이제 좋습니다. 도와 주셔서 감사합니다.

Answer 1

문자열은 Java에서 변경할 수 없습니다. 메서드에 String을 전달하면 완전히 새로운 값이 만들어집니다. 예를 들어 :

당신이 방법을 사용할 경우

void modifyString(String x) { 
    x += "(modified)"; 
} 

는 :

String s = "myString!"; 
modifyString(s); 
// what does s equal? 

당신은 s == "myString!(modified)"를 예상 할 수 있지만, 이것은 사실이 아니다.

귀하의 경우, getAP에 대한 재귀 호출의 매개 변수로 returnStr을 전달합니다. 그러나 당신이 생각하는대로 그것은 수정되지 않습니다. 이 문제를 해결하려면 재귀 메서드 호출의 결과를 로컬 returnStr에 추가하고 반환하십시오.

// removed returnStr as a parameter 
private static String getAP(BinaryNodeInterface<Character> root, String path) 
{ 
    String returnStr = "" + root.getData() + " " + path + "\n"; 
    if(root.hasLeftChild()) 
     returnStr += getAP(root.getLeftChild(), path.concat("0")); 
    if(root.hasRightChild()) 
     returnStr += getAP(root.getRightChild(), path.concat("1")); 

    return returnStr; 
} 

나는 getPT 방법을 훑어 보았지만 실제로 어떤 명백한 문제도 보이지 않습니다.