使用c语言完成：使用层次遍历，求每一层叶子结点的个数

在C语言中，我们可以使用递归的方式来进行层次遍历并计算每个层级的叶子节点（没有孩子的节点）的数量。这里是一个简单的示例，假设我们有一个二叉树结构：

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int countLeaves(TreeNode* root) {
    if (root == NULL) { // 如果节点为空，则返回0
        return 0;
    }

    if (root->left == NULL && root->right == NULL) { // 如果当前节点是叶子节点
        return 1; // 返回1，表示该节点是一颗叶子
    } else { // 否则，递归计算左右子树的叶子节点总数
        return countLeaves(root->left) + countLeaves(root->right);
    }
}

这个函数`countLeaves`会从根节点开始，如果遇到的是叶子节点就直接返回1，如果不是，就继续递归地计算其左右子树的叶子节点数并相加。

如果你想要获取特定层级的叶子节点数，可以在遍历时添加额外的计数器，并在达到目标层级时返回计数值。

相关问题

C语言顺序存储二叉树求叶子结点

顺序存储二叉树是将二叉树的结点按照层次顺序依次存储在一维数组中，如果某个结点的下标为i，则它的左子结点下标为2i，右子结点下标为2i+1。如果数组下标从0开始，则左子结点下标为2i+1，右子结点下标为2i+2。

对于一个顺序存储的二叉树，如果一个结点的左右子树都为空，则它是叶子结点。因此，可以遍历数组中的每个结点，判断它是否为叶子结点，如果是，则统计计数器加1。

以下是求叶子结点数量的代码实现：

#include <stdio.h>

#define MAXSIZE 100    // 定义数组最大长度

// 获取叶子结点数量
int getLeafNum(int tree[], int size) {
    int count = 0;    // 计数器

    for (int i = 0; i < size; i++) {
        // 判断该结点是否为叶子结点
        if (tree[i] != -1 && tree[2 * i + 1] == -1 && tree[2 * i + 2] == -1) {
            count++;
        }
    }

    return count;
}

int main() {
    int tree[MAXSIZE] = {1, 2, 3, -1, -1, 4, 5};    // 定义一个顺序存储的二叉树
    int size = 7;    // 数组中元素个数

    int leafNum = getLeafNum(tree, size);    // 获取叶子结点数量

    printf("叶子结点数量：%d\n", leafNum);

    return 0;
}

其中，tree数组存储了一个顺序存储的二叉树，-1表示该结点为空。size表示数组中元素的个数。getLeafNum函数用于获取叶子结点数量，遍历数组中的每个结点，判断它是否为叶子结点，如果是，则计数器加1。最终返回计数器的值。在主函数中，调用getLeafNum函数并输出结果。

数据结构用C语言或者C++已知深度为h的二叉树以一维数组BT［0．．2h-2］作为其存储结构，试编写一算法，求该二叉树中叶子结点的个数。为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相应的算法。

算法的基本思想是采用递归的方式来遍历二叉树并计算叶子节点的数量。对于给定的深度`h`的一维数组表示的二叉树，每个节点的数据会按照层次顺序存储。我们可以通过数组下标来确定左右孩子的位置，并判断当前节点是否是叶子节点。

下面是基于这个思路的C++实现：

int leafCount(int BT[], int h, int node = 0) {
    // 如果节点值为0，说明它是叶子节点，计数加1
    if (BT[node] == 0) {
        return 1;
    }

    // 如果左孩子存在且非空，递归处理左孩子
    if (node * 2 + 1 < 2 * h) {
        int leftLeaves = leafCount(BT, h, node * 2 + 1);
        // 同理，如果右孩子存在且非空，递归处理右孩子
        if (node * 2 + 2 < 2 * h) {
            int rightLeaves = leafCount(BT, h, node * 2 + 2);
            return leftLeaves + rightLeaves;  // 返回左右叶子节点之和
        } else {
            // 只有左孩子，返回左孩子叶子节点数量
            return leftLeaves;
        }
    } else {
        // 没有左孩子，只看右孩子
        return leafCount(BT, h, node * 2 + 2);
    }
}