设计一个算法,求二叉树第k层的结点个数的代码
时间: 2023-12-17 13:22:25 浏览: 40
以下是求二叉树第k层结点个数的算法实现:
```python
# 定义二叉树结点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 求二叉树第k层的结点个数
def get_node_num_k(root, k):
if not root or k <= 0:
return 0
if k == 1:
return 1
else:
return get_node_num_k(root.left, k - 1) + get_node_num_k(root.right, k - 1)
```
其中,`root`表示二叉树的根节点,`k`表示要求的层数。如果`root`为空或者`k`小于等于0,则返回0;如果`k`等于1,则返回1;否则递归求解左子树和右子树的第`k-1`层结点个数,然后将左右子树的结果相加即为第`k`层的结点个数。
相关问题
用C语言设计一个算法,求二叉树第k层的结点个数的代码
以下是使用C语言实现求二叉树第k层结点个数的算法实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点类型
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 求二叉树第k层的结点个数
int get_node_num_k(TreeNode* root, int k) {
if (root == NULL || k <= 0) {
return 0;
}
if (k == 1) {
return 1;
} else {
return get_node_num_k(root->left, k - 1) + get_node_num_k(root->right, k - 1);
}
}
int main() {
// 创建二叉树
TreeNode* root = (TreeNode*) malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*) malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = (TreeNode*) malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->right = NULL;
root->right = (TreeNode*) malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = (TreeNode*) malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 求第2层的结点个数
int k = 2;
int count = get_node_num_k(root, k);
printf("The number of nodes in level %d is %d.\n", k, count);
// 释放内存
free(root->left->left);
free(root->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
```
其中,`root`表示二叉树的根节点,`k`表示要求的层数。如果`root`为空或者`k`小于等于0,则返回0;如果`k`等于1,则返回1;否则递归求解左子树和右子树的第`k-1`层结点个数,然后将左右子树的结果相加即为第`k`层的结点个数。
c语言,设计一个算法,求二叉树第k层的结点个数。完整代码
以下是C语言设计的算法,用于求二叉树第k层的结点个数:
```
#include <stdio.h>
#include <stdlib.h>
struct node{
struct node *left;
struct node *right;
int value;
};
int countNodesAtLevelK(struct node *root, int k){
if(root == NULL){
return 0;
}
else if(k == 1){
return 1;
}
else{
return countNodesAtLevelK(root->left, k-1) + countNodesAtLevelK(root->right, k-1);
}
}
int main(){
struct node *root = (struct node*)malloc(sizeof(struct node));
root->value = 1;
root->left = (struct node*)malloc(sizeof(struct node));
root->left->value = 2;
root->right = (struct node*)malloc(sizeof(struct node));
root->right->value = 3;
root->left->left = (struct node*)malloc(sizeof(struct node));
root->left->left->value = 4;
root->left->right = (struct node*)malloc(sizeof(struct node));
root->left->right->value = 5;
root->right->left = (struct node*)malloc(sizeof(struct node));
root->right->left->value = 6;
root->right->right = (struct node*)malloc(sizeof(struct node));
root->right->right->value = 7;
int k = 3;
int count = countNodesAtLevelK(root, k);
printf("The number of nodes at level %d is %d", k, count);
return 0;
}
```
在此示例中,我们创建了一个二叉树,并求出了第三层的结点数。请注意,此算法使用递归来计算二叉树的层级结点数,因此效率可能不高。