信息学奥赛一本通 1339：【例3-4】求后序遍历 | 洛谷 P1827 [USACO3.4] 美国血统 American Heritage

2023-10-29 13:40
文章标签 遍历 洛谷 奥赛 信息学 一本 后序 美国 american 1339 p1827 usaco3.4 heritage 血统

本文主要是介绍信息学奥赛一本通 1339：【例3-4】求后序遍历 | 洛谷 P1827 [USACO3.4] 美国血统 American Heritage，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】

ybt 1339：【例3-4】求后序遍历
洛谷 P1827 [USACO3.4] 美国血统 American Heritage
两题都是已知先序和中序遍历序列，求后序遍历序列
区别为：【ybt 1339】先输入先序遍历序列，再输入中序遍历序列。【洛谷 P1827】先输入中序遍历序列，再输入先序遍历序列。

【题目考点】

1. 二叉树

已知先序、中序边路序列，求后序遍历序列

【解题思路】

解法1：

假设输入的中序遍历序列为：DBAECH，先序遍历序列为ABDCEF。以该输入为例讨论问题解法。
当前要解决的问题是：已知先序、中序遍历序列，构建二叉树。

  1. 首先先序遍历中第一个字母为树的根结点的值（A）。
  2. 而后在中序遍历序列中找到根结点值（A）的位置，根结点值左边的序列（DB）是根结点的左子树的中序遍历序列。根结点值右边的序列（ECF）为根结点的右子树的中序遍历序列。
  3. 在先序遍历序列中根据左子树中序遍历序列的长度，找到左子树的先序遍历序列（BD），及右子树的先序遍历序列（CEF）。
  4. 递归调用“已知先序中序遍历序列求二叉树”的函数。现在已知根结点的左子树、右子树的先序、中序遍历序列，那么就可以构建出根结点的左子树与右子树（构建子树相对于构建以A为根结点的树，是小规模问题，递归求解大规模问题时，小规模问题的解被视为是已知的）
  5. 以A为根结点，接上构造好的左右子树，即完成了树的构建。

接下来对这棵树做后序遍历，即可得到树的后序遍历序列。
在这里插入图片描述

写法1：使用字符数组

输入先序遍历序列到s_pre，中序遍历序列到字符数组s_in。
函数createTree需要传入ml，mr，pl，pr，意为：由先序序列s_pre[pl]~s_pre[pr]与中序序列s_in[ml]~s_in[mr]构造一棵二叉树在这里插入图片描述
根据上述算法，先在中序序列中找到先序序列第一个字符s_pre[pl]的位置，找到位置为i。那么左子树的中序遍历序列为s_in[ml]~s_in[i-1]，长度为i-ml，在先序遍历序列中，从pl+1开始取长为i-ml的序列，最后一个元素的位置为pl+i-ml，那么左子树的先序遍历序列为s_pre[pl+1]~s_pre[pl+i-ml]。类似地，可以得到右子树的中序序列为s_in[i+1]~s_in[mr]，先序序列为s_pre[pl+i-ml+1]~s_pre[pr]。
使用createTree分别生成左右子树，接在新分配出来的根结点的下面，就得到了这棵树。
递归出口为：先序与中序序列的下标范围一定有pl<=pr且ml<=mr，如果不满足这一条件，序列范围无意义，应该返回。

写法2：使用string类

思路与上述方法类似，不再赘述。
使用string类，可以使用substr成员函数来取子串。每次传入函数的先序、中序序列都是string类对象。
在这里插入图片描述

【题解代码】：ybt 1339：【例3-4】求后序遍历

写法1：使用字符数组
#include <bits/stdc++.h>
using namespace std;
#define N 1005
struct Node
{char val;int left, right;
};
Node node[N];
int p;
char pre_s[105], mid_s[105];
//由先序遍历序列pre_s[pl]~pre_s[pr]与中序遍历序列mid_s[ml]~mid_s[mr]构建二叉树，返回根结点地址 
int createTree(int pl, int pr, int ml, int mr)
{if(pl > pr || ml > mr)return 0;int np = ++p, i;node[np].val = pre_s[pl];//pre_s[pl]一定是根结点的值 for(i = ml; i <= mr; ++i)if(mid_s[i] == pre_s[pl])//找到根结点在中序序列中的下标为i break;node[np].left = createTree(pl + 1, pl + i - ml, ml, i - 1);node[np].right = createTree(pl + i - ml + 1, pr, i + 1, mr);return np;
}
void postOrder(int root)
{if(root == 0)return; postOrder(node[root].left);postOrder(node[root].right);cout << node[root].val;
}
int main()
{cin >> pre_s >> mid_s;int len_pre = strlen(pre_s), len_mid = strlen(mid_s);int root = createTree(0, len_pre - 1, 0, len_mid - 1);postOrder(root);return 0;
}
写法2：使用string类
#include <bits/stdc++.h>
using namespace std;
#define N 1005
struct Node
{char val;int left, right;
};
Node node[N];
int p;
string s_pre, s_in;
int createTree(string sp, string si)//用先序序列sp与中序序列si构建二叉树，返回树根 
{int np = ++p, i;node[np].val = sp[0];for(i = 0; i < si.length(); ++i)if(sp[0] == si[i])break;int len_l = i, len_r = si.length() - 1 - i;//左右子树序列长度 if(len_l > 0)//序列长度大于0，才可以建立一棵树 node[np].left = createTree(sp.substr(1, len_l), si.substr(0, len_l));if(len_r > 0)node[np].right = createTree(sp.substr(i+1, len_r), si.substr(i+1, len_r));return np;
}
void postOrder(int root)
{if(root != 0){postOrder(node[root].left);postOrder(node[root].right);cout << node[root].val;}
}
int main()
{cin >> s_pre >> s_in;int root = createTree(s_pre, s_in);postOrder(root);return 0;
}

【题解代码】：洛谷 P1827 [USACO3.4] 美国血统 American Heritage

写法1：使用字符数组
#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{char val;int left, right;
};
Node node[N];
int p = 1;
char s_pre[105], s_in[105];//s_pre:先序遍历序列 s_in:中序遍历序列 
//由先序序列s_pre[pl]~s_pre[pr]与中序序列s_in[ml]~s_in[mr]构造一棵二叉树，返回根结点 
int createTree(int pl, int pr, int ml, int mr)
{if(pl > pr || ml > mr)return 0;int np = p++, i;node[np].val = s_pre[pl];for(i = ml; i <= mr; ++i){if(s_in[i] == s_pre[pl])break;}node[np].left = createTree(pl + 1, pl + i - ml, ml, i - 1);node[np].right = createTree(pl + i - ml + 1, pr, i + 1, mr);return np;
}
void postOrder(int root)
{if(root != 0){postOrder(node[root].left);postOrder(node[root].right);cout << node[root].val;}
}
int main()
{cin >> s_in >> s_pre;int root = createTree(0, strlen(s_pre) - 1, 0, strlen(s_in) - 1);postOrder(root);return 0;
}
写法2：使用string类
#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{char val;int left, right;
};
Node node[N];
int p = 1;
string s_pre, s_in;
int createTree(string sp, string si)//用先序序列sp与中序序列si构建二叉树，返回树根 
{int np = p++, i;node[np].val = sp[0];for(i = 0; i < si.length(); ++i){if(sp[0] == si[i])break;}int len_l = i, len_r = si.length() - 1 - i;//左右子树序列长度 if(len_l > 0)//序列长度大于0，才可以建立一棵树 node[np].left = createTree(sp.substr(1, len_l), si.substr(0, len_l));if(len_r > 0)node[np].right = createTree(sp.substr(i+1, len_r), si.substr(i+1, len_r));return np;
}
void postOrder(int root)
{if(root != 0){postOrder(node[root].left);postOrder(node[root].right);cout << node[root].val;}
}
int main()
{cin >> s_in >> s_pre;int root = createTree(s_pre, s_in);postOrder(root);return 0;
}

这篇关于信息学奥赛一本通 1339：【例3-4】求后序遍历 | 洛谷 P1827 [USACO3.4] 美国血统 American Heritage的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/301007。

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
生信代码入门：从零开始掌握生物信息学编程技能

生信代码入门：从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域，结合了生物学、计算机科学和统计学。随着高通量测序技术的发展，海量的生物数据需要通过编程来进行处理和分析。因此，掌握生信编程技能，成为每一个生物信息学研究者的必备能力。 生信代码入门，旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用
阅读更多...
生信圆桌x生信分析平台：助力生物信息学研究的综合工具

生信圆桌x生信分析平台：助力生物信息学研究的综合工具

介绍 少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 生物信息学的迅速发展催生了众多生信分析平台，这些平台通过集成各种生物信息学工具和算法，极大地简化了数据处理和分析流程，使研究人员能够更高效地从海量生物数据中提取有价值的信息。这些平台通常具备友好的用户界面和强大的计算能力，支持不同类型的生物数据分析，如基因组、转录组、蛋白质组等。
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
2024年AMC10美国数学竞赛倒计时两个月：吃透1250道真题和知识点（持续）

2024年AMC10美国数学竞赛倒计时两个月：吃透1250道真题和知识点（持续）

根据通知，2024年AMC10美国数学竞赛的报名还有两周，正式比赛还有两个月就要开始了。计划参赛的孩子们要记好时间，认真备考，最后冲刺再提高成绩。 那么如何备考2024年AMC10美国数学竞赛呢？做真题，吃透真题和背后的知识点是备考AMC8、AMC10有效的方法之一。通过做真题，可以帮助孩子找到真实竞赛的感觉，而且更加贴近比赛的内容，可以通过真题查漏补缺，更有针对性的补齐知识的短板。
阅读更多...
react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注
阅读更多...
【生物信息学算法】图算法1：概念和算法

【生物信息学算法】图算法1：概念和算法

文章目录 1. 图的定义、分类、表达方式图的定义图的分类表达方式Python实现 2.相邻节点和度概念定义python实现 3.路径、距离和搜索路径和距离搜索环 4.图论中的欧拉定理 1. 图的定义、分类、表达方式 图的定义 图G可以由两个集合来定义，即G=(V,E)。其中，V是对象的集合，称为图的顶点或节点; E是V中(u,v)顶点对的集合，称为边或弧，表示u和v之间的关系
阅读更多...
hashmap的存值，各种遍历方法

hashmap的存值，各种遍历方法

package com.jefflee;import java.util.HashMap;import java.util.Iterator;import java.util.Map;public class HashmapTest {// 遍历Hashmap的四种方法public static void main(String[] args) {//hashmap可以存一个null，把
阅读更多...
高精度计算（代码加解析，洛谷p1601，p1303）除法待更新

高精度计算（代码加解析，洛谷p1601，p1303）除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时，正常加法不能得到精确解。在小学，我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位： c[i] = a[i] + b[i];if(c[i] >=
阅读更多...
Knight Moves -uva 简单的BFS遍历

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历，在uva上找了个题敲了出来，感觉还不错，最近敲代码挺有手感的，希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2