以二叉链表为存储结构,统计二叉树的叶结点个数,用c语言实现
时间: 2024-02-29 09:53:16 浏览: 26
好的,以下是用 C 语言实现统计二叉树叶节点个数的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体
typedef struct TreeNode {
int data; // 数据域
struct TreeNode *left; // 左子节点指针
struct TreeNode *right; // 右子节点指针
} TreeNode;
// 创建二叉树(前序遍历)
TreeNode* createTree() {
TreeNode *pNode = NULL;
int data;
scanf("%d", &data);
if (data == -1) { // 输入-1表示该节点为空(即叶节点)
return NULL;
}
pNode = (TreeNode*)malloc(sizeof(TreeNode));
if (!pNode) { // 内存分配失败
return NULL;
}
pNode->data = data;
pNode->left = createTree();
pNode->right = createTree();
return pNode;
}
// 统计二叉树叶节点个数
int countLeafNodes(TreeNode *root) {
if (!root) { // 空树
return 0;
}
if (!root->left && !root->right) { // 叶节点
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right); // 递归遍历左右子树
}
int main() {
TreeNode *root = createTree(); // 创建二叉树
int count = countLeafNodes(root); // 统计叶节点个数
printf("叶节点个数为:%d\n", count);
return 0;
}
```
以上代码中,`createTree` 函数用于创建二叉树,输入-1表示该节点为空(即叶节点);`countLeafNodes` 函数用于统计二叉树的叶节点个数,若为空树则返回0,若为叶节点则返回1,否则递归遍历左右子树并返回节点数之和。最后在 `main` 函数中调用这两个函数即可。
阅读全文