c语言实现 如果二叉树表示家谱中男性的血缘结构,某家族需要完成一项危险任务,三代及以上单传的男性不允许报名(该树叶结点的父结点、祖父结点均为独生子结点),能否设计程序,在一棵二叉树中筛选出这些结点。
时间: 2024-05-11 20:18:12 浏览: 21
可以通过遍历整个二叉树,在每个叶子结点判断其父结点和祖父结点是否为独生子结点,如果不是,则该叶子结点不符合条件,需要被筛选出来。这个过程可以使用递归实现。
具体实现步骤如下:
1. 定义二叉树节点结构体:
```c
typedef struct node {
char name[20]; // 名字
char sex; // 性别
struct node* left; // 左子节点
struct node* right; // 右子节点
} Node;
```
2. 定义一个递归函数,检查当前节点是否符合条件:
```c
int check(Node* node) {
if (node == NULL) return 1; // 空节点默认符合条件
if (node->sex == 'F') return 1; // 如果是女性,直接返回符合条件
if (node->left == NULL && node->right == NULL) { // 如果是叶子节点
if (node->left != NULL && node->right != NULL) return 0; // 如果有两个子节点,则一定不符合条件
if (node->left != NULL) { // 如果只有左子节点
if (node->left->left != NULL || node->left->right != NULL) return 0; // 如果左子节点有子节点,则不符合条件
return check(node->left); // 如果左子节点是独生子结点,则递归检查左子节点
} else { // 如果只有右子节点
if (node->right->left != NULL || node->right->right != NULL) return 0; // 如果右子节点有子节点,则不符合条件
return check(node->right); // 如果右子节点是独生子结点,则递归检查右子节点
}
} else { // 如果不是叶子节点,则递归检查左右子节点
return check(node->left) && check(node->right);
}
}
```
3. 在主函数中创建家谱二叉树,并调用check函数筛选符合条件的节点:
```c
int main() {
// 创建家谱二叉树
Node* root = (Node*)malloc(sizeof(Node));
strcpy(root->name, "Grandpa");
root->sex = 'M';
root->left = (Node*)malloc(sizeof(Node));
strcpy(root->left->name, "Father");
root->left->sex = 'M';
root->left->left = (Node*)malloc(sizeof(Node));
strcpy(root->left->left->name, "Me");
root->left->left->sex = 'M';
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (Node*)malloc(sizeof(Node));
strcpy(root->left->right->name, "Uncle");
root->left->right->sex = 'M';
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (Node*)malloc(sizeof(Node));
strcpy(root->right->name, "Aunt");
root->right->sex = 'F';
root->right->left = NULL;
root->right->right = NULL;
// 筛选符合条件的节点
printf("符合条件的节点:\n");
if (check(root)) {
printf("%s\n", root->name);
}
return 0;
}
```
在这个例子中,只有Me这个节点符合条件,程序的输出为:
```
符合条件的节点:
Me
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)