当前位置: 首页 > article >正文

洛谷问题美国血统 American Heritage、新二叉树题解(关于二叉树的遍历问题)

目录

一.美国血统 American Heritage

二.新二叉树


一.美国血统 American Heritage

P1827 [USACO3.4] 美国血统 American Heritage - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

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

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

这是在样例输入和样例输出中的树的图形表达方式:

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

附注:

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

输入格式

第一行一个字符串,表示该树的中序遍历。

第二行一个字符串,表示该树的前序遍历。

输出格式

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

输入输出样例

输入 #1

ABEDFCHG
CBADEFGH 

输出 #1

AEFDBHGC

首先,我们知道

先序遍历是:根左右

中序遍历是:左根右

后序遍历是:左右根

那么先序遍历的第一个就是树的根节点,那么我们在中序遍历可以找出树的左子树和右子树。

为了求出后序遍历,我们需要按照左右根的遍历方式,所以我们递归先将左子树递归完再将右子树递归完,再输出。

我们在分好的左子树区继续找根节点,根节点后面再分左子树和右子树,当左子树找不到根节点,即head>=tail,那么递归右边,当递归完所有节点,最后输出。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
string a,b;
void dfs(int head_a,int tail_a,int head_b,int tail_b)
{
	if(head_a>tail_a||head_b>tail_b) return; 
	for(int i=head_a;i<=tail_a;i++){
		if(a[i]==b[head_b])//在中序遍历找到根节点 
		{
			dfs(head_a,i-1,head_b+1,head_b+i-head_a);//左子树区,找下一个根节点 
			dfs(i+1,tail_a,head_b+1+i-head_a,tail_b);//右子树区 
			cout<<a[i];//输出 
		}
	}
}
int main()
{
	cin>>a>>b;
	int len=a.size();
	dfs(0,len-1,0,len-1);
	return 0;
}

P1030 [NOIP2001 普及组] 求先序排列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题目非常相似,可以练习一下。

二.新二叉树

P1305 新二叉树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

输入一串二叉树,输出其前序遍历。

输入格式
第一行为二叉树的节点数  n。(1≤n≤26)

后面 n 行,每一个字母为节点,后两个字母分别为其左儿子。特别地,数据保证第一行读入的节点必为根节点。

空节点用 * 表示

输出格式

二叉树的前序遍历。

输入输出样例

输入 #1

6
abc
bdi
cj*
d**
i**
j**

输出 #1

abdicj

由于题目规定输入的第一行为根节点,那么我们便可以继续往下递归,我们可以先找出第一行的第二个节点,如果不为’*‘,那么此树有左子树,由于是求先序遍历,按照根左右的遍历方式,先输出遍历到的节点,再递归左子树,最后递归右子树,当遇到’*‘就return。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
string a[30];
int n;
void dfs(char k)
{
	if(k=='*') return ;//遇到*表示当前节点为NULL,直接return 
	cout<<k;//直接输出 
	for(int i=1;i<=n;i++){
		if(a[i][0]==k)//找到对应的节点 
		{
			dfs(a[i][1]);//递归左子树 
			dfs(a[i][2]);//递归右子树 
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(a[1][0]);//第一个就是根节点,从这里开始递归 
	return 0;
}


http://www.kler.cn/a/227026.html

相关文章:

  • Cmake语法学习3:语法
  • anaconda+pytorch+pycharm安装总结
  • 【开源】JAVA+Vue+SpringBoot实现就医保险管理系统
  • 二叉树的最大深度
  • Day11代码随想录
  • 蓝桥杯每日一题-----数位dp
  • dcat admin + dingo + nginx 开发前台
  • Linux mount命令教程:如何挂载文件系统(附案例详解和注意事项)
  • ES6-const
  • 技术栈面试综合整理
  • 基于 Python 的 Web 应用程序的 Web 服务器比较
  • 初识vue3
  • python:lxml 生成思维导图 Freemind(.mm)文件
  • LeetCode 1686. 石子游戏 VI【排序,贪心】【Py3,Go】2000
  • 排队打水问题1(c++题解)
  • 深度解析Go字符串
  • C++基础语法 类 02
  • [349. 两个数组的交集](C语言)(两种解法:双指针+排序,哈希)
  • Qt/C++音视频开发66-音频变速不变调/重采样/提高音量/变速变调/倍速播放/sonic库使用
  • 图论练习1