写一个c语言代码按先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
时间: 2024-01-23 14:40:18 浏览: 63
求二叉树的建立、遍历、叶子结点树、深度
5星 · 资源好评率100%
以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 创建二叉树
struct TreeNode* createTree(int *preorder, int start, int end) {
if (start > end) {
return NULL;
}
// 创建根节点
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = preorder[start];
root->left = NULL;
root->right = NULL;
int i;
for (i = start; i <= end; i++) {
if (preorder[i] > root->val) {
break;
}
}
// 递归创建左子树和右子树
root->left = createTree(preorder, start + 1, i - 1);
root->right = createTree(preorder, i, end);
return root;
}
// 统计叶子节点个数
int countLeafNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
// 计算二叉树的深度
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() {
int preorder[] = {5, 3, 2, 4, 7, 6, 8};
int len = sizeof(preorder) / sizeof(preorder[0]);
// 创建二叉树
struct TreeNode* root = createTree(preorder, 0, len - 1);
// 统计叶子节点个数
int leafNodes = countLeafNodes(root);
printf("叶子结点个数:%d\n", leafNodes);
// 计算二叉树的深度
int depth = maxDepth(root);
printf("二叉树的深度:%d\n", depth);
return 0;
}
```
这里我们使用了先序遍历来创建二叉树,然后分别统计叶子节点个数和二叉树的深度。
阅读全文