PTA 根据后序和中序遍历输出先序遍历 (25分)
2024-09-01 22:08:07
PTA 根据后序和中序遍历输出先序遍历 (25分)
本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。
输入格式:
第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。
输出格式:
在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格,行末不得有多余空格。
输入样例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例:
Preorder: 4 1 3 2 6 5 7
【程序思路】
在后序遍历的最后一个数字4是根结点,在中序遍历中找到根结点4,4左边的序列1 2 3共3个结点是左子树的中序遍历,4右边的序列5 6 7共3个结点是右子树的中序遍历。在后序遍历中前3个结点2 3 1是左子树的后序遍历,紧接着的3个结点5 7 6是右子树的后序遍历。即变成了两个子树的后序遍历和中序遍历序列以及根结点。
左子树的后序遍历为2 3 1
左子树的中序遍历为1 2 3
右子树的后序遍历为5 7 6
右子树的中序遍历为5 6 7
根结点为4
按同样的步骤可以将左子树也分成左子树、右子树和根这3部分,右子树也可以分成左子树、右子树和根这3部分。
然后递归创建树,最后递归先序遍历树输出。
【程序实现】
#include <bits/stdc++.h>
using namespace std;
struct Tree{
int data;
struct Tree *left;
struct Tree *right;
};
int p1[35],p2[35];
struct Tree *creat(int front1, int rear1, int front2, int rear2) {
struct Tree *root = new struct Tree;
root->data = p1[rear1];
root->left = NULL;
root->right = NULL;
int p = front2;
while(p2[p] != p1[rear1])
p++;
int c = p - front2;//左子树节点的个数
if(p != front2) //创建左子树
root->left = creat(front1, front1 + c - 1, front2, p - 1);
if(p != rear2) //创建右子树
root->right = creat(front1 + c, rear1 - 1, p + 1, rear2);
return root;
}
void preVisit(struct Tree *root) {
if(root) {
cout<<" "<<root->data;
preVisit(root->left);
preVisit(root->right);
}
}
int main()
{
int n;
cin>>n;
for(int i = 0; i < n; i++)
cin>>p1[i];
for(int i = 0; i < n; i++)
cin>>p2[i];
struct Tree *root = creat(0, n - 1, 0, n - 1);
cout<<"Preorder:";
preVisit(root);
return 0;
}
最新文章
- C++11 - 类型推导auto关键字
- Linux进程间通信(八):流套接字 socket()、bind()、listen()、accept()、connect()、read()、write()、close()
- Xcode5中如何切换Storyboards为xib
- 基本XML解析---编写
- IP地址的分类与寻址
- IIS:开启GZIP压缩效率对比及部署方法
- Android之jni入门
- HDU4570----Multi-bit Trie----简单的DP
- Centos系统mysql 忘记root用户的密码
- SQL server语句测试
- MySQL Procedure(MySQL存储过程)[转]
- 说说CSS学习中的瓶颈
- u盘烧写后实际容量变小了
- JNI 中文字符串传递(转)
- 在IntelliJ IDEA里创建简单的基于Maven的SpringMVC项目
- 一种解决eclipse中安装maven出错的方法
- GitHub-分支管理03-多人合作【重点】
- hdu1213并查集
- 【Redis】事务
- FireDAC内部初探
热门文章
- Gitee自动化部署python脚本
- 最详细的搭建web自动化测试网站,别再说你没有实战项目(文未有福利)
- fastjson将json转为Map<;String,String>;踩坑
- js Promise用法
- asp.net core使用identity+jwt保护你的webapi(三)——refresh token
- UOJ 2021 NOI Day2 部分题解
- Sentinel-Go 源码系列(一)|开篇
- python socket 基本使用
- Golang通脉之流程控制
- .Net2.0连接PG数据注意事项