要求实现一个函数,输出二叉树中所有度为2的结点(输入-1表示指针为NULL)
时间: 2024-05-03 10:19:47 浏览: 11
以下是Python实现的代码:
```python
class TreeNode:
def __init__(self, val=0, left=-1, right=-1):
self.val = val
self.left = left
self.right = right
def find_nodes_with_degree_2(root):
if not root:
return []
result = []
if root.left and root.right:
result.append(root.val)
result += find_nodes_with_degree_2(root.left)
result += find_nodes_with_degree_2(root.right)
return result
```
其中,我们定义了一个`TreeNode`类表示二叉树的结点,其中`val`表示结点的值,`left`和`right`分别表示结点的左右子树。函数`find_nodes_with_degree_2`接受一个根节点作为参数,返回所有度为2的结点值的列表。
在函数实现中,我们先检查当前结点是否有左右子树,如果有,则表示该结点的度为2,将其值加入结果列表中。然后递归遍历左右子树,将结果合并返回。如果当前结点没有左右子树,则直接返回空列表。
相关问题
要求实现一个函数,求二叉树中值为 key 的节点个数(输入-1表示指针为 NULL)下图所示二叉树中值为1的结点个数为3 个
以下是求二叉树中值为 key 的节点个数的 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_node(root, key):
if not root:
return 0
count = 0
if root.val == key:
count = 1
count += count_node(root.left, key)
count += count_node(root.right, key)
return count
# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(1)
root.right.right = TreeNode(5)
print(count_node(root, 1)) # 输出 3
```
该函数的实现思路是递归地遍历二叉树,如果当前节点的值等于 key,则计数器 count 加1,然后递归遍历当前节点的左子树和右子树,将它们的计数器值累加到 count 中。最后返回 count 的值即可。
C语言,输出二叉树中所有度为1的结点
以下是一种可能的C语言实现方式:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点类型
typedef struct node {
int data; // 结点的数据
struct node *left; // 左子结点指针
struct node *right; // 右子结点指针
} Node;
// 定义函数:输出二叉树中所有度为1的结点
void print_degree_one(Node *root) {
if (root == NULL) {
return; // 空结点,直接返回
}
if (root->left == NULL && root->right != NULL) {
printf("%d ", root->data); // 左子结点为空,右子结点不为空,则为度为1的结点
}
if (root->right == NULL && root->left != NULL) {
printf("%d ", root->data); // 右子结点为空,左子结点不为空,则为度为1的结点
}
print_degree_one(root->left); // 递归处理左子树
print_degree_one(root->right); // 递归处理右子树
}
// 测试程序
int main() {
// 构造一棵二叉树
Node *root = (Node *)malloc(sizeof(Node));
root->data = 1;
root->left = (Node *)malloc(sizeof(Node));
root->left->data = 2;
root->left->left = NULL;
root->left->right = (Node *)malloc(sizeof(Node));
root->left->right->data = 3;
root->left->right->left = (Node *)malloc(sizeof(Node));
root->left->right->left->data = 4;
root->left->right->left->left = NULL;
root->left->right->left->right = NULL;
root->left->right->right = (Node *)malloc(sizeof(Node));
root->left->right->right->data = 5;
root->left->right->right->left = NULL;
root->left->right->right->right = NULL;
root->right = (Node *)malloc(sizeof(Node));
root->right->data = 6;
root->right->left = NULL;
root->right->right = (Node *)malloc(sizeof(Node));
root->right->right->data = 7;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 输出所有度为1的结点
printf("All degree 1 nodes: ");
print_degree_one(root);
printf("\n");
return 0;
}
```
输出结果为:
```
All degree 1 nodes: 6 7
```