热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

美国血统争议与遗传学研究进展

美国血统争议与遗传学研究进展:在遗传学领域,血统记录的准确性至关重要。然而,在实际操作中,记录错误时有发生。本文探讨了通过遗传学方法验证血统的有效性,并介绍了利用二叉树结构进行家谱分析的技术,特别是中序遍历和前序遍历的应用,为血统争议提供科学依据。

题目描述:

农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛 们的家谱作成二叉树,并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而 不是用图形的方法。

你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后,创建奶牛家谱的“树的 后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。(你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。)显然,这里的树不会有多于 26 个的顶点。 这是在样例输入和 样例输出中的树的图形表达方式:

        C
       / \
       /  \
       B   G
      / \  /
     A D H
       / \
       E F

 

树的中序遍历是按照左子树,根,右子树的顺序访问节点。

树的前序遍历是按照根,左子树,右子树的顺序访问节点。

树的后序遍历是按照左子树,右子树,根的顺序访问节点。

 


输入格式

第一行: 树的中序遍历

第二行: 同样的树的前序遍历


输出格式

单独的一行表示该树的后序遍历。


输入输出样例

输入 #1

ABEDFCHG
CBADEFGH

输出 #1

AEFDBHGC
解题思路:
首先我们要先找到两个遍历的根,前序遍历的根就是第一个节点,然后根据这个可以在中序遍历中找到根的位置,
而中序遍历的最左边就是左子树的左边界,根节点的左边就是左子树的右边界,根节点右边是右子树的左边界,最右边就是右子树的右边界,以此类推,分别给左右子树递归可以求得次根节点
而后序遍历是左右根的遍历顺序,在每次递归完当前左右子树之后就输出根节点的值。
代码如下:

#include
using namespace std;
char mid[100];
char fir[100];
int i,j;
void digui(int fl,int fr,int ml,int mr)
{
int gen,l,r;
for(i=0;i<strlen(mid);i++)
if(mid[i]==fir[fl])break;
gen=i;
l=gen-ml;

r=mr-gen;
if(l>0)
{
digui(fl+
1,fl+l,ml,ml+l-1);
}
if(r>0)
{
digui(fr-r+
1,fr,gen+1,gen+r);
}
cout<
}
int main()
{
cin>>mid>>fir;
digui(
0,strlen(fir)-1,0,strlen(mid)-1);
return 0;
}




 



推荐阅读
  • 本文探讨了如何在C#中实现USB条形码扫描仪的数据读取,并自动过滤掉键盘输入,即使不知道设备的供应商ID(VID)和产品ID(PID)。通过详细的技术指导和代码示例,展示了如何高效地处理条形码数据,确保系统能够准确识别并忽略来自键盘的干扰信号。该方法适用于多种USB条形码扫描仪,无需额外配置设备信息。 ... [详细]
  • 本文作为“实现简易版Spring系列”的第五篇,继前文深入探讨了Spring框架的核心技术之一——控制反转(IoC)之后,将重点转向另一个关键技术——面向切面编程(AOP)。对于使用Spring框架进行开发的开发者来说,AOP是一个不可或缺的概念。了解AOP的背景及其基本原理,对于掌握这一技术至关重要。本文将通过具体示例,详细解析AOP的实现机制,帮助读者更好地理解和应用这一技术。 ... [详细]
  • 结语 | 《探索二进制世界:软件安全与逆向分析》读书笔记:深入理解二进制代码的逆向工程方法
    结语 | 《探索二进制世界:软件安全与逆向分析》读书笔记:深入理解二进制代码的逆向工程方法 ... [详细]
  • C++ 进阶:类的内存布局与虚函数类的实现细节
    C++ 进阶:类的内存布局与虚函数类的实现细节 ... [详细]
  • 本文详细介绍了如何在Linux系统中搭建51单片机的开发与编程环境,重点讲解了使用Makefile进行项目管理的方法。首先,文章指导读者安装SDCC(Small Device C Compiler),这是一个专为小型设备设计的C语言编译器,适合用于51单片机的开发。随后,通过具体的实例演示了如何配置Makefile文件,以实现代码的自动化编译与链接过程,从而提高开发效率。此外,还提供了常见问题的解决方案及优化建议,帮助开发者快速上手并解决实际开发中可能遇到的技术难题。 ... [详细]
  • Java 零基础入门:SQL Server 学习笔记(第21篇)
    Java 零基础入门:SQL Server 学习笔记(第21篇) ... [详细]
  • 题目描述:小K不幸被LL邪教洗脑,洗脑程度之深使他决定彻底脱离这个邪教。在最终离开前,他计划再进行一次亚瑟王游戏。作为最后一战,他希望这次游戏能够尽善尽美。众所周知,亚瑟王游戏的结果很大程度上取决于运气,但通过合理的策略和算法优化,可以提高获胜的概率。本文将详细解析洛谷P3239 [HNOI2015] 亚瑟王问题,并提供具体的算法实现方法,帮助读者更好地理解和应用相关技术。 ... [详细]
  • 深入解析 Django 中用户模型的自定义方法与技巧 ... [详细]
  • 本文详细探讨了Java集合框架的使用方法及其性能特点。首先,通过关系图展示了集合接口之间的层次结构,如`Collection`接口作为对象集合的基础,其下分为`List`、`Set`和`Queue`等子接口。其中,`List`接口支持按插入顺序保存元素且允许重复,而`Set`接口则确保元素唯一性。此外,文章还深入分析了不同集合类在实际应用中的性能表现,为开发者选择合适的集合类型提供了参考依据。 ... [详细]
  • 使用cpphttplib构建HTTP服务器以处理带有查询参数的URL请求 ... [详细]
  • 在《PHP应用性能优化实战指南:从理论到实践的全面解析》一文中,作者分享了一次实际的PHP应用优化经验。文章回顾了先前进行的一次优化项目,指出即使系统运行时间较长后出现的各种问题和性能瓶颈,通过采用一些通用的优化策略仍然能够有效解决。文中不仅详细阐述了优化的具体步骤和方法,还结合实例分析了优化前后的性能对比,为读者提供了宝贵的参考和借鉴。 ... [详细]
  • 在Ubuntu系统中,由于预装了MySQL,因此无需额外安装。通过命令行登录MySQL时,可使用 `mysql -u root -p` 命令,并按提示输入密码。常见问题包括:1. 错误 1045 (28000):访问被拒绝,这通常是由于用户名或密码错误导致。为确保顺利连接,建议检查MySQL服务是否已启动,并确认用户名和密码的正确性。此外,还可以通过配置文件调整权限设置,以增强安全性。 ... [详细]
  • 在稀疏直接法视觉里程计中,通过优化特征点并采用基于光度误差最小化的灰度图像线性插值技术,提高了定位精度。该方法通过对空间点的非齐次和齐次表示进行处理,利用RGB-D传感器获取的3D坐标信息,在两帧图像之间实现精确匹配,有效减少了光度误差,提升了系统的鲁棒性和稳定性。 ... [详细]
  • Python学习:环境配置与安装指南
    Python作为一种跨平台的编程语言,适用于Windows、Linux和macOS等多种操作系统。为了确保本地已成功安装Python,用户可以通过终端或命令行界面输入`python`或`python3`命令进行验证。此外,建议使用虚拟环境管理工具如`venv`或`conda`,以便更好地隔离不同项目依赖,提高开发效率。 ... [详细]
  • 本文详细探讨了C语言中`extern`关键字的简易编译方法,并深入解析了预编译、`static`和`extern`的综合应用。通过具体的代码示例,介绍了如何在不同的文件之间共享变量和函数声明,以及这些关键字在编译过程中的作用和影响。文章还讨论了预编译过程中宏定义的使用,为开发者提供了实用的编程技巧和最佳实践。 ... [详细]
author-avatar
哈王豐3_408
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有