用c语言,二叉树采用二叉链表存储,试编写算法,实现: (1)计算二叉树的所有叶子结点。 (2)求二叉树的深度。
时间: 2024-11-21 15:13:17 浏览: 45
在C语言中,我们可以使用递归的方式来处理二叉链表存储的二叉树。这里给出两个函数,分别用于计算所有叶子节点和计算二叉树的深度。
首先,我们定义一个结构体`TreeNode`表示二叉树的节点:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
然后,我们开始编写这两个函数:
### 计算所有叶子节点
```c
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0; // 如果为空节点,返回0
}
if (root->left == NULL && root->right == NULL) { // 如果当前节点左右孩子都为空,则是叶子节点
return 1;
} else {
// 递归遍历左、右子树并累加叶子节点数
return countLeaves(root->left) + countLeaves(root->right);
}
}
```
### 求二叉树的深度
```c
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0; // 空树深度为0
}
int leftDepth = maxDepth(root->left); // 左子树的深度
int rightDepth = maxDepth(root->right); // 右子树的深度
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; // 返回较大子树深度加1作为当前层深度
}
```
这两个函数的使用方法是先创建二叉树结构,然后传入根节点给上述函数即可得到结果。例如:
```c
// 创建二叉树示例
TreeNode* buildTree() {
// ... 实现具体的节点构建代码 ...
}
int leafCount = countLeaves(buildTree());
int treeDepth = maxDepth(buildTree());
printf("叶节点数: %d\n", leafCount);
printf("树的深度: %d\n", treeDepth);
```
阅读全文