用C语言编写:求二叉树中叶结点的个数、二叉树结点总数以及二叉树的深度。
时间: 2024-01-23 09:43:41 浏览: 87
c语言编写的二叉树深度优先遍历算法
以下是用C语言编写的求二叉树中叶结点的个数、二叉树结点总数以及二叉树的深度的代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
struct TreeNode {
int val;
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 1 + countNodes(root->left) + countNodes(root->right);
}
}
// 计算二叉树的深度
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->val = 1;
root->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->right->val = 3;
root->right->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = NULL;
// 计算二叉树中叶结点的个数
int leaves = countLeaves(root);
printf("叶结点的个数:%d\n", leaves);
// 计算二叉树结点总数
int nodes = countNodes(root);
printf("结点总数:%d\n", nodes);
// 计算二叉树的深度
int depth = maxDepth(root);
printf("二叉树的深度:%d\n", depth);
// 释放二叉树内存
free(root->left);
free(root->right->left);
free(root->right);
free(root);
return 0;
}
```
注意,本代码中只是简单构建了一颗二叉树作为示例,实际应用中应该根据具体需求构建二叉树。另外,为了简化代码,本代码中没有进行输入输出的错误处理,请在实际应用中加入相应的错误处理代码。
阅读全文