이 순환 함수가 이진 탐색 트리의 노드를 계산하면 왜 항상 예상보다 큰 결과가 반환됩니까?

이 함수는 항상 실제 노드 수보다 큰 응답을 반환합니다 (예 : 트리에 노드가 3 개 있지만 4를 반환). 나는 종이에 수동으로 코드를 실행하려고 시도했지만 여전히 문제를 보지 못했습니다. 재귀 또는 함수에 대한 기본 사항이 있습니까? 마지막 기능이 작동하지만 이유를 이해이 순환 함수가 이진 탐색 트리의 노드를 계산하면 왜 항상 예상보다 큰 결과가 반환됩니까?

int countNode (Tree &T) 
{ 
    if(T==NULL) return 0; 
    int a = countNode(T->left); 
    int b = countNode(T->right); 
    int count = a + b + 1; 
    return count; 
}

: 그러나

이

int countNode (Tree &T) 
{ 
    int count; 
    if(T==NULL) return 0; 
    return count+=1; 
    countNode(T->left); 
    countNode(T->right); 
}

이 완벽하게 작동합니다 :

int countNode (Tree &T) 
{ 
    int count; 
    if(T==NULL) return 0; 
    return count++; 
    countNode(T->left); 
    countNode(T->right); 
}

이 하나 더 N'- 포인트 2 인 대답을 돌려 준다 여전히 처음 두 가지가 무엇이 잘못되었는지 알지 못합니다.

출처

2017-10-10 Trần Đức Hiếu

코드의 첫 번째 부분에있는 문제는 다른 문제와 밀접하게 관련되어 있으므로 여기에 집중하겠습니다. 귀하의 코드는 다음과 같습니다.

int countNode (Tree &T) 
{ 
    int count; 
    if(T==NULL) return 0; 
    return count++; 
    countNode(T->left); 
    countNode(T->right); 
}

주의해야 할 사항이 몇 가지 있습니다. 먼저 컴파일러 경고 설정을 최대 값까지 올립니다. 당신은 가능성이 몇 가지 경고가 표시됩니다

당신은 실제로 당신이 count++를 반환 할 때, 당신은 쓰레기 값을 반환하고, count의 값을 초기화하지 않습니다. 그 이유는 왜 당신이 오버 카운트를보고 있는지 설명 할 수 있습니다.
return count++;을 쓰는 경우 "count을 증가시킨 다음 증가하지 않은 이전 값을 가져 와서 되돌립니다."라고 말합니다. 아마 당신이하고 싶지 않았을 것입니다. 증분 count을 원하면 count++으로 작성하십시오. count +1을 반환하려면 return count + 1;으로 작성하십시오.
작성한 문장 return은 재귀 호출을하기 전에 함수가 종료되도록합니다. countNode에 대한 호출은 절대로 실행되지 않고 실행되지 않습니다. 이 문제를 해결하려면 return 문을 사용하여 코드를 재정렬하거나 코드를 삭제하고 싶을 것입니다.
countNode에서 반환 값을 캡처하지 마십시오. countNode을 호출 할 때마다 자체 버전이 count이므로 하나의 순환 호출에서 count 만 증가 시키면 count의 다른 버전과 만나는 것은 아닙니다. 두 개의 재귀 호출의 반환 값을 저장해야합니다. 두 개의 순환 호출은 왼쪽 및 오른쪽 하위 트리에있는 노드 수를 반환해야하며이를 함께 집계하려는 방법을 파악해야합니다.

그림 컴파일러 경고는 처음 세 가지 문제를 표시하지만 마지막 것은 약간 더 미묘합니다.

이것을 바탕으로 다른 잘못된 구현에서 어떤 일이 벌어지고 있는지, 그리고 마지막 구현이 올바른지 확인할 수 있습니까?

출처

2017-10-10 02:52:59 templatetypedef

이 순환 함수가 이진 탐색 트리의 노드를 계산하면 왜 항상 예상보다 큰 결과가 반환됩니까?

답변

관련 문제