热门标签 | 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;
}




 



推荐阅读
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • 数据类型--char一、char1.1char占用2个字节char取值范围:【0~65535】char采用unicode编码方式char类型的字面量用单引号括起来char可以存储一 ... [详细]
  • Web动态服务器Python基本实现
    Web动态服务器Python基本实现 ... [详细]
  • 深入理解:AJAX学习指南
    本文详细探讨了AJAX的基本概念、工作原理及其在现代Web开发中的应用,旨在为初学者提供全面的学习资料。 ... [详细]
  • 本文介绍了在Linux环境下如何有效返回命令行状态、上一级目录及快速查找头文件和函数定义的方法。包括处理长时间运行命令、编辑器退出技巧、目录导航以及文件搜索策略。 ... [详细]
  • CSS Border 属性:solid 边框的使用详解
    本文详细介绍了如何在CSS中使用solid边框属性,包括其基本语法、应用场景及高级技巧,适合初学者和进阶用户参考。 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 本文通过C++语言实现了一个递归算法,用于解析并计算数学表达式的值。该算法能够处理加法、减法、乘法和除法操作。 ... [详细]
  • 本文介绍了如何通过C#语言调用动态链接库(DLL)中的函数来实现IC卡的基本操作,包括初始化设备、设置密码模式、获取设备状态等,并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]
  • 本文探讨了在SQL Server中处理几何类型列时遇到的INTERSECT操作限制,并提供了解决方案,包括通过转换数据类型和使用额外表结构的方法。 ... [详细]
  • 本文介绍如何手动实现一个字符串连接函数,该函数不依赖于C语言的标准字符串处理函数,如strcpy或strcat。函数原型为void concatenate(char *dest, char *src),其主要作用是将源字符串src追加到目标字符串dest的末尾。 ... [详细]
  • 本文介绍了一种方法,通过使用Python的ctypes库来调用C++代码。具体实例为实现一个简单的加法器,并详细说明了从编写C++代码到编译及最终在Python中调用的全过程。 ... [详细]
  • 本题要求计算一组正整数的最小公倍数(LCM)。输入包括多组测试数据,每组数据首先给出一个正整数n,随后是n个正整数。 ... [详细]
  • linux网络子系统分析(二)—— 协议栈分层框架的建立
    目录一、综述二、INET的初始化2.1INET接口注册2.2抽象实体的建立2.3代码细节分析2.3.1socket参数三、其他协议3.1PF_PACKET3.2P ... [详细]
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社区 版权所有