怎么用c语言求二叉树叶子结点
时间: 2023-08-02 15:12:50 浏览: 43
要计算二叉树的叶子节点数量,可以使用递归方法。
首先,定义一个结构体表示二叉树节点:
```
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
然后,编写一个递归函数,递归计算左子树和右子树的叶子节点数量,并将它们相加。
```
int countLeaves(struct TreeNode* root) {
if (root == NULL) { // 如果根节点为空,返回0
return 0;
} else if (root->left == NULL && root->right == NULL) { // 如果根节点是叶子节点,返回1
return 1;
} else { // 否则,递归计算左右子树叶子节点数量并相加
return countLeaves(root->left) + countLeaves(root->right);
}
}
```
在调用这个函数时,传入二叉树的根节点即可计算出叶子节点数量。
相关问题
用c语言求二叉树的叶子结点
以下是用 C 语言实现求二叉树叶子节点的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
// 创建二叉树
Node* createTree() {
int data;
scanf("%d", &data);
if (data == -1) { // -1 表示该节点为空
return NULL;
}
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = createTree();
node->right = createTree();
return node;
}
// 计算叶子节点数
int countLeafNodes(Node *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
int main() {
printf("请输入二叉树的节点数据:\n");
Node *root = createTree();
int count = countLeafNodes(root);
printf("叶子节点数为:%d\n", count);
return 0;
}
```
在这个示例中,我们首先定义了一个二叉树节点的结构体,包含节点的数据以及左右子节点的指针。然后,我们使用 `createTree()` 函数创建了一个二叉树,其中输入 -1 表示该节点为空。接着,我们使用 `countLeafNodes()` 函数计算二叉树的叶子节点数,该函数使用递归的方式遍历二叉树,当遇到叶子节点时返回 1,否则递归遍历左右子树并将结果相加。最后,我们在 `main()` 函数中输出叶子节点数。
C语言顺序存储二叉树求叶子结点
顺序存储二叉树是将二叉树的结点按照层次顺序依次存储在一维数组中,如果某个结点的下标为i,则它的左子结点下标为2i,右子结点下标为2i+1。如果数组下标从0开始,则左子结点下标为2i+1,右子结点下标为2i+2。
对于一个顺序存储的二叉树,如果一个结点的左右子树都为空,则它是叶子结点。因此,可以遍历数组中的每个结点,判断它是否为叶子结点,如果是,则统计计数器加1。
以下是求叶子结点数量的代码实现:
```c
#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函数并输出结果。