先序中序求后序/先序中序求层序/后序中序求先序/后序中序求层序(不用构造二叉树)

测试数据:

7
4 1 3 2 6 5 7
1 2 3 4 5 6 7
2 3 1 5 7 6 4
4 1 6 3 5 7 2

代码: 

#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
const int maxn=31;
int n;
int pre[maxn];
int post[maxn];
int inorder[maxn];
int layer[maxn];
struct node{
	int index;
	int data;		
};
bool cmp1(node a,node b){
	return a.index<b.index;
}
//序列里的数字不能重复 
//后序和中序转先序 ToPre(n-1,0,n-1)
void ToPre(int root,int start,int end){
	if(start>end)return;
	int k;
	for(k=start;k<=end;k++){
		if(post[root]==inorder[k])break;
	}
	printf("%d ",post[root]);
	
	int rightNum=end-k;
	ToPre(root-1-rightNum,start,k-1);//左子树的根节点以及左子树的中序序列 
	ToPre(root-1,k+1,end);
	
}
//后序中序转层序 ?
vector<node> ans;//存放层序的序列 
void ToLayer(int root,int start,int end,int index){
	
	if(start>end)return;
	int k;
	for(k=start;k<=end;k++){
		if(post[root]==inorder[k])break;
	}
	ans.push_back({index,post[root]});//后序根据index排列 :和结构体属性定义顺序得一致 
	int rightNum=end-k;
	//只要保证右节点的index永远比左节点的index大后序即可排序得到正确序列 
	ToLayer(root-1-rightNum,start,k-1,2*index+1);//左子树的根节点以及左子树的中序序列 
	ToLayer(root-1,k+1,end,2*index+2);
} 
//中序先序转后序 preToPost(0,0,n-1)
void preToPost(int root,int start,int end){
	if(start>end)return;
	int data=pre[root];//根节点
	int k;
	for(k=start;k<=end;k++){
		if(inorder[k]==data)break;
	} 
	//k是根节点在中序序列的位置
	int leftNum=k-start;
	preToPost(root+1,start,k-1);
	preToPost(root+1+leftNum,k+1,end);
	printf("%d ",data); 	
}
//中序先序转层序:其实是一样的:省略了 
 
//
 
int main()
{
	printf("请输入序列大小:");
	scanf("%d",&n);
	
	printf("请输入先序序列:\n");
	//先序 
	for(int i=0;i<n;i++){
		cin>>pre[i];
	}
	
	printf("请输入中序序列:\n");
	//中序
	for(int i=0;i<n;i++){
		cin>>inorder[i];
	}
	
	
	printf("请输入后序序列:\n");
	//后序
	for(int i=0;i<n;i++){
		cin>>post[i];
	}
	
	printf("请输入层次序列:\n");
	//层次 
	for(int i=0;i<n;i++){
		cin>>layer[i];
	}
	
	printf("-------------\n");

	printf("后序和中序转先序\n"); 
	ToPre(n-1,0,n-1);
	 
	printf("\n");
	printf("后序和中序转层序\n");
	ToLayer(n-1,0,n-1,0);
	sort(ans.begin(),ans.end(),cmp1);//容器的排序法只能用begin和end
	for(int i=0;i<ans.size();i++){
		printf("%d ",ans[i].data);
	} 
	
	printf("\n");
	printf("先和中序转后序\n");
	preToPost(0,0,n-1);
	
	return 0;
	}

 

热门文章

暂无图片
编程学习 ·

什么是嵌入式培养?要不要选嵌入式培养?

前言 马上要高考了,高考完后势必要面临选专业,本人作为大二的计算机专业老油条,要为想选计算机专业的小萌新们科普科普,什么是嵌入式培养。嵌入式培养的概述 这里的嵌入式,说白了,就是要把社会上的东西,嵌入到学校的教学里 这个概念本来是没有的,但是上级领导认为,计算…
暂无图片
编程学习 ·

Java-eclipse 设置字体字号大小,如何设置居中

文字一般都放在 标签内: 这里以 JLable 与 按钮 为实例: JLabel label; JButton exitBtn; //表题**标签** label = new JLabel("个人停车详情",JLabel.CENTER);//设置字体居中 label.setFont(new Font("微软雅黑", Font.BOLD, 20));//设置字体字号大小 l…
暂无图片
编程学习 ·

Day 11 武装飞船

《外星人入侵》游戏要实现的是:玩家控制一艘出现在屏幕底部中央的飞船,可以使用箭头左右移动飞船,还可以使用空格来进行射击,游戏开始时候一群外星人出现在天空,他们在屏幕中向下移动,玩家的任务是射杀这些外星人,玩家将所有外星人都消灭干净后,会出现一群新的外星人,…
暂无图片
编程学习 ·

理解持续测试,才算理解DevOps

软件产品的成功与否,在很大程度上取决于对市场需求的及时把控,采用DevOps可以加快产品交付速度,改善用户体验,从而有助于保持领先于竞争对手的优势。作为敏捷开发方法论的一种扩展,DevOps强调开发、测试和运维不同团队间的协作与沟通。持续集成和持续测试是一个在迭代中构…
暂无图片
编程学习 ·

02 | 该如何选择消息队列?

1.应用场景见: https://blog.csdn.net/william_n/article/details/1040254082.学习/操作2.1 阅读文档02 | 该如何选择消息队列?李玥 2020-01-1400:0013:59讲述:李玥 大小:12.81M你好,我是李玥。这节课我们来聊一下几个比较常见的开源的消息队列中间件。如果你正在做消息队…
暂无图片
编程学习 ·

EasyNTS上云网关内配置EasyNVR云终端成功后显示设备离线问题解决

之前为大家简单介绍过EasyNTS上云网关,一部分是为了进行网络穿透而产生的设备,目前有部分用户已经在进行了内测,我们也会收集一些内测用户的问题,集中排查解决,以达到更好的使用效果。有的用户在EasyNTS上云网关内进行流媒体终端EasyNVR硬件配置测试时,设备已经配置完成,…
暂无图片
编程学习 ·

Shiro框架简单使用

文章目录1. Shiro过滤器&标签简介Shiro过滤器Shiro的JSP标签2. Shiro登陆认证(一)使用认证过滤器目标实现3. Shiro登陆认证(二)完成登录认证(*)目标总结4. Shiro登陆认证(三)凭证匹配器-普通加密需求步骤总结5. Shiro登陆认证(四)凭证匹配器-加盐加密需求什么是加…
暂无图片
编程学习 ·

单调栈解决Next Greater Number一类题

单调栈是什么? 单调栈使得每次新元素入栈后,栈内元素都保持有序(单调递增或者单调递减)。 单调递增栈:栈中数据出栈的序列为单调递增序列。 单调递减栈:栈中数据出栈的序列为单调递减序列。 注意:这里所说的递增递减是出栈的顺序,不是栈中数据的顺序。 单调栈的应用 通…
暂无图片
编程学习 ·

CSS 总结

一、CSS三大特性:层叠性、继承性、优先级 层叠性 层叠性:就近原则。 分两种情况:同类选择器,第二个选择器样式会覆盖第一个选择器样式。 在同一个选择器中,相同的属性会以最后一个为准。继承性 继承性:子承父业 特殊:a标签不受影响因为它又自己的特性 优先级 优先级选择…
暂无图片
编程学习 ·

CentOS Liniux 使用john进行弱口令检测

什么是弱口令? 弱口令(weak password) 没有严格和准确的定义,通常认为容易被别人(他们有可能对你很了解)猜测到或被破解工具破解的口令均为弱口令。弱口令指的是仅包含简单数字和字母的口令,例如“123”、“abc”等,因为这样的口令很容易被别人破解,从而使用户的计算机面…
暂无图片
编程学习 ·

阿里云ECS服务器怎么安装宝塔面板?

首先,宝塔Linux面板安装前的环境要求: 1.操作系统:全新系统(支持CentOS、Ubuntu、Debian、Fedora、Deepin) 2.确保是纯净的操作系统,没有安装过其它环境带的Apache/Nginx/php/MySQL 3.宝塔Linux6.0版本是基于centos7开发的,强烈建议使用centos7.x 系统 4.内存要求:内存要…
暂无图片
编程学习 ·

1252 奇数值单元格的数目(模拟)

1. 问题描述:给你一个 n 行 m 列的矩阵,最开始的时候,每个单元格中的值都是 0。另有一个索引数组 indices,indices[i] = [ri, ci] 中的 ri 和 ci 分别表示指定的行和列(从 0 开始编号)。你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。请你在执行完所有 ind…
暂无图片
编程学习 ·

未root手机如何使用Xposed框架(Android抓包无忧矣~)

一、目的手机无法root还需要使用xposed框架配合JustTrustMe插件绕过SSL Pinning抓取手机应用数据包怎么办? 二、方法一:VirtualXposed 2.1 介绍一个APP应用,安装到手机即可在应用中使用Xposed框架,如果想抓取目的数据包,直接将应用导入到VirtualXposed中即可官网:https:/…
暂无图片
编程学习 ·

2020-07-02

网页 你知道什么是网页吗?或者你知道该用什么样的话来形容它吗? 我能想到的话是: 网页是由图片、文字、声音、视频、链接这些个东东组成的扩展名叫html的文件 那啥子叫扩展名呢? 扩展名就是指文件的类型 规定文件应该用哪个软件打开 晓得不啦?那html是个啥呢? html是一种…
暂无图片
编程学习 ·

HTML概述

HTML发展史HTML没有1.0,因为关于它的初版存在争议,1995年HTML 2.0面世,1997年由国际官方组织W3C推出了HTML 3.2以及HTML 4.0标准,后面W3C(万维网联盟)也渐渐变成Web技术领域的权威,经过漫长的演变,2014年,HTML 5标准最终面世。HTML 2.0——1995年11月,RFC 1866发布HTML…
暂无图片
编程学习 ·

微信测试公众号 接口配置信息

1:首先要先注册一个测试的公众号 1:这样就可以得到自己的appid 和 appsecret 2:接口配置信息 可以看到参数 (测试公众号只有url 和 token) 1:url 是开发者用来接收微信消息和事件 的接口URL。(必须以http://开头,目前支持80端口) 2: Token:可由开发者可以任意填写,用作…