Количество листьев в двоичном дереве поиска в C

Question

Я начинаю и работаю над деревом двоичного дерева C. Я пытаюсь сделать метод, который вернет количество листьев в моем дереве. Лишь я имею в виду узел (родитель), который не имеет ребенка (левый/правый) Heres мое дерево структура:

struct Node { 
    int value; 
    struct Node *left; 
    struct Node *right; 
}; 

typedef struct Node TNode; 
typedef struct Node *binary_tree; 

Он создается так:

binary_tree NewBinaryTree(int value_root) { 
    binary_tree newRoot = malloc(sizeof(TNode)); 
    if (newRoot) { 
     newRoot->value = value_root; 
     newRoot->left = NULL; 
     newRoot->right = NULL; 
    } 
    return newRoot; 
} 

добавить элементы к ней, как:

void Insert(binary_tree *tree, int val) { 
    if (*tree == NULL) { 
     *tree = (binary_tree)malloc(sizeof(TNode)); 
     (*tree)->value = val; 
     (*tree)->left = NULL; 
     (*tree)->right = NULL; 
    } else { 
     if (val < (*tree)->value) { 
      Insert(&(*tree)->left, val); 
     } else { 
      Insert(&(*tree)->right, val); 
     } 
    } 
} 

Мой фактический метод для подсчета количества листьев:

int nbleaves(binary_tree tree) 
{ 
    int nb; 
    if(tree->right==NULL && tree->left ==NULL){ 
     nb=nb+1; 
    } 
    printf("%d",nb); 
} 

Конечно, это не работает первый Тереза ​​нет фактического цикла, однако я пробовал оно не возвращать какие-либо ошибки, но 0 (ех после добавления элемента 2222 и 3 к дерево возвращает эту функцию 0). Я не знаю, как это сделать.

спасибо!

Answer 1

Помимо инициализации, как @iharob отметил, вам просто нужно рекурсию на левую и правую половины дерева и добавить, что к общей сумме (как говорится в комментариях). Этот подход работал для меня на моих тестах, поэтому я не уверен, какую ошибку вы получаете, когда вы это пробовали. Вот моя nbleaves() функция:

int nbleaves(binary_tree tree) 
{ 
    int nb=0; 
    if(tree->right==NULL && tree->left ==NULL){ 
    nb=nb+1; 
    } 
    else { 
    if(tree->left!=NULL) 
     nb += nbleaves(tree->left); 
    if(tree->right!=NULL) 
     nb += nbleaves(tree->right); 
    } 
    return nb; 
} 

К примеру, на этом тесте:

int main() {  
    binary_tree root=NULL; 

    root=NewBinaryTree(5); 
    Insert(&root,3); 
    Insert(&root,7); 
    Insert(&root,2); 
    Insert(&root,8); 
    Insert(&root,6); 
    Insert(&root,1); 
    Insert(&root,4); 
    Insert(&root,9); 
    traverse(root); /*Just a function I created for testing*/ 

    printf("%d\n",nbleaves(root)); 

    free_tree(root); /*Also a function I wrote*/ 
    return 0; 
} 

Он производит этот выход:

5: 3 7 
3: 2 4 
2: 1 NULL 
1: NULL NULL 
4: NULL NULL 
7: 6 8 
6: NULL NULL 
8: NULL 9 
9: NULL NULL 
4 

последняя строка рассчитывать листья, а остальные выходы traverse().

Для моей полной программе: https://repl.it/Epud/0

Answer 2

Потому что вы ДОЛЖНЫ инициализировать nb.

int nb = 0; 

Поскольку nb не инициализирован он содержит «случайного» или «мусора» значения, так что поведение, которое вы видите, потому что значение может быть очень большим. Но нет способа предсказать, что это за значение.

ПРИМЕЧАНИЕ: Не «скуп» с пробелами, не используйте их слишком много, но пусть ваш код дыхание немного.

Сравнить

if(tree->right==NULL && tree->left ==NULL){ 
    nb=nb+1; 
} 

с

if ((tree->right == NULL) && (tree->left == NULL)) { 
    nb = nb + 1; 
}