BST - 요소 수 찾기

Question

이진 검색 트리에서 요소 수를 찾는 방법이 있습니까?

struct node 
{ 
    node *p, *left, *right; 
    int key; 
}; 

이것은 내 노드의 구조이며, p 포인터는 부모 요소를 가리 킵니다.

트리를 검색하고 모든 요소가있는 배열을 반환하기 위해 메모리를 할당하려면이 번호를 찾아야합니다.

int numberOfElements(node *root, int count = 0) 
{ 
    if(root) 
    { 
     numberOfElements(root->left, ++count); 
     numberOfElements(root->right, ++count); 
    } 
    return count + 1; 
} 

그러나 잘, 그것은 어떤 임의의 결과를 보여줍니다 :

나는 이런 식으로 뭔가를 내놓았다 한 P를 들어 "1, 2"1, 2, 3, 4 "에 대한 표시 2,이다 , 5, 6, 7 "3 등을 표시합니다 ...

저는 이것을 한 함수 내에서 수행하고자합니다. 그 이유는 여기 count가 인수입니다.

어떻게하면됩니까? 당신은 모든 numberOfElements의 반환 값을 사용하지 않는 것

int numberOfElements(node *root) { 
    if (root) { 
     return 1 + numberOfElements(root->left) + numberOfElements(root->right); 
    } else { 
     return 0; 
    } 
} 

Answer 1

당신은 두 번째 인수가 필요하지 않습니다. 이 버전은 작동 할 수 있습니다 :

int numberOfElements(node *root) 
{ 
    if(root) 
    { 
     return numberOfElements(root->left) + 
       numberOfElements(root->right) + 1; 
    } 
    return 0; 
} 

일반적으로, 나무의 크기는 필드에 기록해야하며, 당신이 나무를 수정할 때마다 업데이트됩니다. 아무도 나무의 크기를 찾기 위해 O (N) 실행 시간을 기대하지 않습니다.

Answer 2

: