C中二叉搜索树中的叶子数

Question

我是初学者，正在研究 C 二进制搜索 tree.I 我正在尝试使用一种方法来 return 我的 tree.By 叶子中的叶子数量我的意思是一个节点(parent) 没有 child(left/right) 这是我的树结构：

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);
 }

当然这首先不起作用没有实际的循环，但是我试过了它没有return任何错误但是0（例如在将元素2222和3添加到树之后这个函数return 0 ).我不知道如何实现这个功能。

谢谢！

Answer 1

因为你必须初始化 nb。

int nb = 0;

由于 nb 未初始化，它包含一个“random”或“garbage”值，因此您看到的行为是因为该值可能非常大。但是无法预测该值是多少。

注意：不要使用空格“吝啬”，不要使用太多但让你的代码呼吸一下。

比较

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

和

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

Answer 2

除了@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中二叉搜索树中的叶子数

Number of leaves in binary search tree in C

c

tree

binary-tree

binary-search-tree