Получение числа узлов в двоичном дереве поиска

Question

Итак, я работаю над методом, который получает число узлов в двоичном дереве поиска, когда у меня есть 3 узла, это дает мне 3, но если я делаю 5, дает мне 4, что мне нужно изменить?

int BinaryTree::size(int count, Node *leaf) const 
{ 
    if(leaf != NULL)//if we are not at a leaf 
    { 
     size(count + 1, leaf->getLeft());//recurisvly call the function and increment the count 
     size(count + 1, leaf->getRight()); 
    } 
    else 
    { 
     return count;//return the count 
    } 

} 

Answer 1

int BinaryTree::size(Node *leaf) const 
{ 
    if(leaf == NULL) { //This node doesn't exist. Therefore there are no nodes in this 'subtree' 
     return 0; 
    } else { //Add the size of the left and right trees, then add 1 (which is the current node) 
     return size(leaf->getLeft()) + size(leaf->getRight()) + 1; 
    } 
} 

Хотя это другой подход, я считаю, что это легче прочитать, чем то, что у вас было.

Answer 2

int BinaryTree::size(Node *n) const 
{ 
    if(!n) 
     return 0; 
    else 
     return size(n->getLeft()) + 1 + size(n->getRight()); 
} 

Answer 3

Другие люди уже ввели правильный алгоритм. Я просто объясню, почему ваш алгоритм не работает.

Логика, лежащая в основе вашего алгоритма, заключается в следующем: сохранить текущее значение счета. Если лист имеет значение null, то у него нет детей, поэтому возвращайте счетчик, если лист не равен нулю, а затем регенерируйте детей.

Это наоборот. Потому что вам нужно будет передать ваш int по ссылке, а не по значению, а затем не увеличивать, если он равен нулю, увеличивать, если он не равен null, и рекурсивно.

Итак, ваша оригинальная идея будет работать с некоторыми изменениями, но Ник Мичинсон и стрелки имеют лучший способ. Это ваш алгоритм исправлен, поэтому он работает:

int BinaryTree::size(Node *leaf, int& count=0) const 
{ 
    if(leaf != NULL)//if we are not at a leaf 
    { 
     count++; 
     size(leaf->getLeft(), count);//recurisvly call the function and increment the count 
     size(leaf->getRight(), count); 
    } 

    return count;//return the count 
} 

Но опять-таки, есть лучшие способы написать это. И другие ответы показывают их.