c语言求该二叉树的叶结点个数、结点总个数和二叉树的深度。
时间: 2024-01-23 22:40:11 浏览: 25
假设二叉树结点的数据类型为 `struct TreeNode`,其中包括左子树和右子树指针,那么可以使用递归来求解二叉树的叶结点个数、结点总个数和深度。具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点定义
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// 求二叉树叶结点个数
int countLeaves(struct TreeNode* root) {
if (root == NULL) {
return 0;
} else if (root->left == NULL && root->right == NULL) {
return 1;
} else {
return countLeaves(root->left) + countLeaves(root->right);
}
}
// 求二叉树结点总个数
int countNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
} else {
return countNodes(root->left) + countNodes(root->right) + 1;
}
}
// 求二叉树的深度
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
} else {
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}
}
int main() {
// 构建一个二叉树
struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->data = 1;
root->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->left->data = 2;
root->left->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->left->left->data = 4;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = NULL;
root->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->right->data = 3;
root->right->left = NULL;
root->right->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->right->right->data = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 求解二叉树的叶结点个数、结点总个数和深度
int leaves = countLeaves(root);
int nodes = countNodes(root);
int depth = maxDepth(root);
// 输出结果
printf("叶结点个数:%d\n", leaves);
printf("结点总个数:%d\n", nodes);
printf("二叉树深度:%d\n", depth);
return 0;
}
```
输出结果为:
```
叶结点个数:3
结点总个数:5
二叉树深度:3
```