이진 트리에서 특정 값을 가진 노드를 계산합니다.

Question

반복적으로 반복적으로 이진 트리를 탐색하고 특정 값을 찾는 횟수를 계산하는 방법을 찾고 있습니다. 내가 겪고있는 한 가지 문제는 첫 번째 방법에서 루트입니다.

노드 내부 클래스 :

private class Node { 

    int data; 
    Node root; 
    Node left; 
    Node right; 
} 

재귀 & 도우미 방법 : 나는 완전히 확실하지 않다, 그래서

public int valCount(int val) { 
    if (root != null) { 
     return valCount(val, root); 
    } 
    return 0; 
} 

public int valCount(int val, Node root) { 
    int cnt = 0; 
    if (root.left != null) { 
     if (root.left.data == val) { 
      cnt++; 
     } 
     valCount(val, root.left); 
    } 


    if (root.right != null) { 
     if (root.right.data == val) { 
      cnt++; 
     } 
     valCount(val, root.right); 
    } 
    return cnt; 
} 

나는 때문에 근본 문제로 테스트 할 수 없었던 내 출력 것이다 맞다. 그래서, 질문을 묻는 구걸한다. .. 나는 심지어 바른 길 위에있다? 내 접근 방식이 심지어 의미가 있습니까? 어떤 도움이라도 굉장합니다. 건배!

Answer 1

valCount이 호출 될 때마다 로컬 변수 cnt의 사본 이 별도로 생성됩니다. 따라서 valCount을 루트로 호출하면 cnt이라는 변수가 만들어집니다. valCount 다음 왼쪽 또는 오른쪽 하위 트리 자체를 호출 할 때, 새로운 valCount은 cnt을 증가 때, 그들은 하지 증가 최초의 valCount가 소유하는 cnt을, cnt의 자신이있다. 즉, 왼쪽 및 오른쪽 하위 트리에 대해 valCount에 의해 수행 된 모든 작업이 버려집니다.

이 문제를 해결하는 간단한 방법은 왼쪽 또는 오른쪽 하위 트리에 valCount을 호출하면 재귀 호출에서 값을 반환한다는 것을 알 수 있습니다. 대신 결과를 폐기의, 그 값을 사용한다 : 다음

int leftCount = valCount(val, root.left); 

하고 leftCount에 뭔가를 (당신이 그것을 사용하는 방법에 대해 생각 할 것이다).

편집 : 한 가지 더 : valCount가 root.data 봐야한다, 그러나 root.left.data 또는 root.right.data 보지한다. 재귀 호출이 하위 트리의 데이터를 보는 작업을하도록합니다. 이것이 바이너리 트리 재귀가 자주 작동하는 방식입니다.

Answer 2

Node 클래스에는 "root"가 필요하지 않습니다. "루트"는 "this"객체/포인터입니다. 맞습니까? valCount에 다른 매개 변수 "int [] cnt"를 전달하십시오. cnt를 int [1]로 인스턴스화하십시오. 그렇다면 valCount에서 [0] ++을 수행하십시오. 재귀 호출이 끝난 후 호출 함수에서 cnt [0]을 출력하십시오. 그리고 cnt 지역 변수를 제거하십시오.