用递归算法实现统计二叉树的度为 1 的结点个数
时间: 2024-01-22 16:19:55 浏览: 24
可以按如下步骤实现:
1. 定义一个递归函数,函数参数为二叉树的根节点,返回值为度为 1 的结点个数。
2. 如果当前节点为空,则返回 0。
3. 如果当前节点的度为 1,则返回 1 加上左子树和右子树中度为 1 的结点个数之和。
4. 如果当前节点的度不为 1,则返回左子树和右子树中度为 1 的结点个数之和。
下面是递归函数的 Python 代码实现:
```python
def count_degree_one(root):
if not root:
return 0
if (root.left and not root.right) or (root.right and not root.left):
return 1 + count_degree_one(root.left) + count_degree_one(root.right)
else:
return count_degree_one(root.left) + count_degree_one(root.right)
```
其中 `root.left` 和 `root.right` 分别表示当前节点的左子树和右子树。如果左子树或右子树为空,则当前节点的度为 1;否则,当前节点的度不为 1。
相关问题
c语言实现用递归算法实现统计二叉树的度为 1 的结点个数
二叉树的度是指一个结点拥有的子树个数,度为 1 的结点只有一个子树。统计二叉树的度为 1 的结点个数可以通过递归遍历二叉树来实现。
具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点的定义
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 统计度为 1 的结点个数
int count(TreeNode *root) {
if (root == NULL) {
return 0;
}
int cnt = 0;
if (root->left != NULL && root->right == NULL || root->left == NULL && root->right != NULL) {
cnt++;
}
cnt += count(root->left);
cnt += count(root->right);
return cnt;
}
int main() {
// 构造二叉树
TreeNode *root = (TreeNode *) malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *) malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode *) malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode *) malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode *) malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = (TreeNode *) malloc(sizeof(TreeNode));
root->right->right->left->val = 6;
root->right->right->left->left = NULL;
root->right->right->left->right = NULL;
root->right->right->right = NULL;
// 统计度为 1 的结点个数
int cnt = count(root);
printf("度为 1 的结点个数为 %d\n", cnt);
return 0;
}
```
运行结果:
```
度为 1 的结点个数为 2
```
这里构造了一个二叉树进行测试,可以根据实际需求来构造不同的二叉树进行测试。
用递归算法统计二叉树的叶结点个数
递归算法是一种自己调用自己的算法,对于统计二叉树的叶结点个数,可以使用递归算法来实现。具体步骤如下:
1. 如果当前节点为NULL,返回0。
2. 如果当前节点的左右子节点都为NULL,说明当前节点是叶子节点,返回1。
3. 递归计算当前节点的左子树中叶结点的个数。
4. 递归计算当前节点的右子树中叶结点的个数。
5. 将步骤3和步骤4的结果相加,即为当前二叉树中叶结点的个数。
下面是具体的实现代码:
```
int countLeafNodes(TreeNode* root) {
if(root == NULL) {
return 0;
}
if(root->left == NULL && root->right == NULL) {
return 1;
}
int leftLeafNodes = countLeafNodes(root->left);
int rightLeafNodes = countLeafNodes(root->right);
return leftLeafNodes + rightLeafNodes;
}
```
其中,`TreeNode` 表示二叉树节点的结构体,包含 `val`、`left` 和 `right` 三个成员变量,分别表示节点的值、左子节点和右子节点。