如果二叉树表示家谱中男性的血缘结构,某家族需要完成一项危险任务,三代及以上单传的男性不允许报名(该树叶结点的父结点、祖父结点均为独生子结点),能否设计程序,在一棵二叉树中筛选出这些结点,用C语言写出代码

时间: 2024-02-11 22:07:43 浏览: 26
是的,可以设计一个程序来筛选出符合条件的结点,并且可以用 C 语言来实现。下面是具体的代码实现: ```c #include <stdio.h> #include <stdbool.h> // 定义二叉树结点的结构体 typedef struct TreeNode { char name[20]; // 用字符串表示结点的名称 bool is_leaf; // 是否是叶结点 struct TreeNode *left; // 左子树 struct TreeNode *right; // 右子树 } TreeNode; // 判断一个结点的祖先中是否存在单传的情况 bool is_single_pass(TreeNode *node) { if (!node) { return false; } if (!node->left && !node->right) { return false; // 叶结点不可能是单传的 } if (node->left && node->right) { return false; // 有两个儿子的结点不可能是单传的 } if (node->left) { if (node->left->left || node->left->right) { return false; // 有兄弟的结点不可能是单传的 } return is_single_pass(node->left); // 继续判断其左儿子的情况 } if (node->right) { if (node->right->left || node->right->right) { return false; // 有兄弟的结点不可能是单传的 } return is_single_pass(node->right); // 继续判断其右儿子的情况 } return false; } // 筛选出符合条件的叶结点 void find_leaf_nodes(TreeNode *node) { if (!node) { return; } if (node->is_leaf) { if (!is_single_pass(node)) { printf("%s\n", node->name); // 输出符合条件的叶结点的名称 } return; } find_leaf_nodes(node->left); find_leaf_nodes(node->right); } // 测试代码 int main() { // 构造一个二叉树 TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode)); strcpy(root->name, "A"); root->is_leaf = false; root->left = (TreeNode*)malloc(sizeof(TreeNode)); strcpy(root->left->name, "B"); root->left->is_leaf = false; root->left->left = (TreeNode*)malloc(sizeof(TreeNode)); strcpy(root->left->left->name, "C"); root->left->left->is_leaf = true; root->left->left->left = NULL; root->left->left->right = NULL; root->left->right = (TreeNode*)malloc(sizeof(TreeNode)); strcpy(root->left->right->name, "D"); root->left->right->is_leaf = true; root->left->right->left = NULL; root->left->right->right = NULL; root->right = (TreeNode*)malloc(sizeof(TreeNode)); strcpy(root->right->name, "E"); root->right->is_leaf = false; root->right->left = (TreeNode*)malloc(sizeof(TreeNode)); strcpy(root->right->left->name, "F"); root->right->left->is_leaf = true; root->right->left->left = NULL; root->right->left->right = NULL; root->right->right = (TreeNode*)malloc(sizeof(TreeNode)); strcpy(root->right->right->name, "G"); root->right->right->is_leaf = true; root->right->right->left = NULL; root->right->right->right = NULL; // 筛选出符合条件的叶结点 find_leaf_nodes(root); return 0; } ``` 在这个程序中,我们首先定义了一个 `TreeNode` 结构体,用于表示二叉树的结点。然后,我们定义了一个 `is_single_pass` 函数,用于判断一个结点的祖先中是否存在单传的情况。接着,我们定义了一个 `find_leaf_nodes` 函数,用于遍历整棵二叉树,筛选出符合条件的叶结点。最后,我们在 `main` 函数中构造了一个二叉树,并调用 `find_leaf_nodes` 函数来输出符合条件的叶结点的名称。

相关推荐

最新推荐

recommend-type

递归删除二叉树中以x为根的子树

今天小编就为大家分享一篇关于递归删除二叉树中以x为根的子树,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
recommend-type

数据结构综合课设二叉树的建立与遍历.docx

建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。 2.基本要求: 从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立),并采用递归算法对其进行遍历(先序、中序...
recommend-type

C语言中计算二叉树的宽度的两种方式

主要介绍了C语言中计算二叉树的宽度的两种方式的相关资料,需要的朋友可以参考下
recommend-type

C语言数据结构之平衡二叉树(AVL树)实现方法示例

主要介绍了C语言数据结构之平衡二叉树(AVL树)实现方法,结合实例形式分析了C语言平衡二叉树的相关定义与使用技巧,需要的朋友可以参考下
recommend-type

C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)

主要介绍了C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)的相关资料,这里提供实例代码来帮助大家理解掌握二叉树,需要的朋友可以参考下
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

优化MATLAB分段函数绘制:提升效率,绘制更快速

![优化MATLAB分段函数绘制:提升效率,绘制更快速](https://ucc.alicdn.com/pic/developer-ecology/666d2a4198c6409c9694db36397539c1.png?x-oss-process=image/resize,s_500,m_lfit) # 1. MATLAB分段函数绘制概述** 分段函数绘制是一种常用的技术,用于可视化不同区间内具有不同数学表达式的函数。在MATLAB中,分段函数可以通过使用if-else语句或switch-case语句来实现。 **绘制过程** MATLAB分段函数绘制的过程通常包括以下步骤: 1.
recommend-type

SDN如何实现简易防火墙

SDN可以通过控制器来实现简易防火墙。具体步骤如下: 1. 定义防火墙规则:在控制器上定义防火墙规则,例如禁止某些IP地址或端口访问,或者只允许来自特定IP地址或端口的流量通过。 2. 获取流量信息:SDN交换机会将流量信息发送给控制器。控制器可以根据防火墙规则对流量进行过滤。 3. 过滤流量:控制器根据防火墙规则对流量进行过滤,满足规则的流量可以通过,不满足规则的流量则被阻止。 4. 配置交换机:控制器根据防火墙规则配置交换机,只允许通过满足规则的流量,不满足规则的流量则被阻止。 需要注意的是,这种简易防火墙并不能完全保护网络安全,只能起到一定的防护作用,对于更严格的安全要求,需要
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。