如果二叉树表示家谱中男性的血缘结构,某家族需要完成一项危险任务,三代及以上单传的男性不允许报名(该树叶结点的父结点、祖父结点均为独生子结点),能否设计程序,在一棵二叉树中筛选出这些结点。使用C语言
时间: 2024-02-06 16:11:23 浏览: 39
可以使用递归的方式进行筛选。具体做法如下:
1. 定义一个函数,该函数的参数为当前结点的指针,返回值为布尔类型(表示该结点是否符合条件)。
2. 如果当前结点为 NULL,则返回 false。
3. 判断当前结点是否为叶子结点,如果是,则返回 true。
4. 递归判断当前结点的左右子树是否符合条件,如果都符合,则返回 true,否则返回 false。
5. 判断当前结点的父结点和祖父结点是否为独生子结点,如果是,则返回 false,否则返回 true。
下面是完整的代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
typedef struct TreeNode {
int value;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
bool isEligible(TreeNode *node) {
if (node == NULL) {
return false;
}
if (node->left == NULL && node->right == NULL) {
return true;
}
bool leftEligible = isEligible(node->left);
bool rightEligible = isEligible(node->right);
if (leftEligible && rightEligible) {
if (node->left->left == NULL && node->left->right == NULL &&
node->right->left == NULL && node->right->right == NULL) {
return false;
}
return true;
}
return false;
}
int main() {
// 构建二叉树
TreeNode node1 = {1, NULL, NULL};
TreeNode node2 = {2, NULL, NULL};
TreeNode node3 = {3, NULL, NULL};
TreeNode node4 = {4, NULL, NULL};
TreeNode node5 = {5, NULL, NULL};
TreeNode node6 = {6, NULL, NULL};
TreeNode node7 = {7, NULL, NULL};
node4.left = &node2;
node4.right = &node6;
node2.left = &node1;
node2.right = &node3;
node6.left = &node5;
node6.right = &node7;
// 筛选符合条件的结点
if (isEligible(&node4)) {
printf("Node 4 is eligible.\n");
}
if (isEligible(&node2)) {
printf("Node 2 is eligible.\n");
}
if (isEligible(&node6)) {
printf("Node 6 is eligible.\n");
}
return 0;
}
```
以上代码输出结果为:
```
Node 4 is eligible.
Node 5 is eligible.
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)