재귀 C++을 사용하여 BST에서 노드 수 계산

Question

재귀를 사용하여 BST에서 노드 수를 찾으려고합니다. 여기 내 코드는

struct Node{ 
    int key; 
    struct Node* left; 
    struct Node* right; 

    Node(){ 
     int key = 0; 
     struct Node* left = nullptr; 
     struct Node* right = nullptr; 
    } 
}; 

src_root는 트리의 루트 노드 주소입니다.

int BST::countNodes(Node* src_root, int sum){ 

     if((src_root==root && src_root==nullptr) || src_root==nullptr) 
      return 0; 
     else if(src_root->left==nullptr || src_root->right==nullptr) 
      return sum; 
     return countNodes(src_root->left, sum + 1) + countNodes(src_root->right, sum + 1) + 1; 
     } 

그러나 3 개의 노드가있는 경우 내 코드 만 작동하는 것 같습니다. 3보다 큰 값은 잘못된 대답을줍니다. 제발 내가 잘못한 것을 찾아 내도록 도와주세요. 감사!

Answer 1

C/C++로 작성한 이래로 구문 오류가있을 수 있습니다.

나는 그 일을 할 것이라고 생각한다.

Answer 2

구현시 여러 가지 논리적 구조적 문제가 있습니다. Casperah는 웹에서 이미 발견했다고 가정하는 "깨끗한"대답을주었습니다 (아직 조사하지 않았다면 질문을 게시해서는 안됩니다). 따라서, 당신이 찾고있는 것은 다른 사람의 해결책이 아니라 당신 자신의 해결책을 찾는 것입니다.

1. 왜 아래로 합 트리 통과합니까? 하위 노드는 이전 카운트가 무엇인지 신경 쓰지 않아야합니다. 자녀로부터 카운트를 축적하는 것은 부모의 일입니다. 그것이 캐스 페라의 대답에서 어떻게 이루어 졌는지 보아라. 코드에서 추가 매개 변수를 삭제하십시오. 단지 오류의 또 다른 원인 일뿐입니다.
2. 귀하의 기본 케이스는 동일 거짓 절을 가지고 : 당신이 의미있는 전화를 걸 경우 src_root는 == 루트 & & src_root는 == nullptr ..., src_root 는는 루트 및 nullptr 둘 수 없습니다.
3. 글로벌 값인 과 비교하는 이유는 무엇입니까? 각 호출은 단순히 자체 작업을 완료하고 반환합니다. 호출 트리가 루트와 함께 호출 된 원래 호출로 다시 크롤링되면 단순히 작업을 수행하고 호출 프로그램으로 돌아갑니다. 이것은 이 아니라이 아니면 안됩니다.
4. else 절이 잘못되었습니다. 자식이 null 인 경우 다른 자식을 모두 무시하고 지금까지 계산 한 횟수 만 반환합니다. 이렇게하면 트리가 절대적으로 균형 있고 채워지지 않으면 N 레벨에 대해 총 2^N - 1 개의 노드가 아닌 잘못된 답을 줄 수 있습니다.

당신이 유익한 순서로 그 항목을 수정하십시오. 아이디어는 배우는 것입니다. 그러나 최종 코드는 Casperah가 제공 한 답변과 비슷해야합니다.