c - C中的二进制搜索树中的叶子数

我是一个初学者，正在研究C语言的二叉搜索树。我正在尝试做一个返回树中叶子数的方法。叶子是指没有子节点(左/右)的节点(父节点)我的树结构:

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)。我不知道该怎么做。

谢谢!

最佳答案

除了像@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

关于c - C中的二进制搜索树中的叶子数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41132740/