首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >根据后序和中序遍历输出先序遍历

根据后序和中序遍历输出先序遍历

作者头像
AI那点小事
发布于 2022-06-14 23:56:58
发布于 2022-06-14 23:56:58
46700
代码可运行
举报
文章被收录于专栏:AI那点小事AI那点小事
运行总次数:0
代码可运行

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。

输入格式:

第一行给出正整数NN(\le 30≤30),是树中结点的个数。随后两行,每行给出NN个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出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


AC代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>  
#include <cstring>  
using namespace std;  
void getpre(int *post, int *in, int n) {  
    if(n <= 0) return;  
    int root = post[n - 1];  
    int i;  
    for(i = 0; i < n; i++) {  
        if(in[i] == root) {  
            break;  
        }  
    }  
    cout << ' ' << root;  
    getpre(post, in, i);  
    getpre(post + i, in + i + 1, n - i - 1);  
}  
int main() {  
    int post[40], in[40];  
    int n;  
    cin >> n;  
    int i, j;  
    for(i = 0; i < n; i++) {  
        scanf("%d", &post[i]);  
    }  
    for(i = 0; i < n; i++) {  
        scanf("%d", &in[i]);  
    }  
    printf("Preorder:");  
    getpre(post, in, n);  
    printf("\n");  
    return 0;  
} 
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-05-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
PTA 根据后序和中序遍历输出先序遍历(25 分)
根据给定的后序遍历和中序遍历结果,输出该二叉树的先序遍历结果。该代码是使用递归方法实现的。
Kindear
2017/12/29
2.1K0
根据后序和中序遍历输出先序遍历
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
喜欢ctrl的cxk
2019/11/08
1K0
后序+中序输出先序遍历(树)
第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。
叶茂林
2023/07/30
2270
4-15 根据后序和中序遍历输出先序遍历 (15 分)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
韩旭051
2019/11/07
8990
根据先序和中序输出后序遍历
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
喜欢ctrl的cxk
2019/11/08
2.3K0
二叉树的先序遍历 中序遍历 后序遍历 层序遍历
完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
小雨的分享社区
2022/10/26
1.2K0
二叉树的先序遍历 中序遍历 后序遍历 层序遍历
【数据结构】C语言实现二叉树的基本操作——二叉树的遍历(先序遍历、中序遍历、后序遍历)
通过前面的介绍,我们已经认识了二叉树的逻辑结构和存储结构。在今天的内容中,我们将会开始介绍二叉树的最后一个要素——二叉树的基本操作。
蒙奇D索隆
2024/09/07
1.3K0
【数据结构】C语言实现二叉树的基本操作——二叉树的遍历(先序遍历、中序遍历、后序遍历)
给出前序遍历和中序遍历求二叉树_已知前序遍历和后序遍历
1.已知先序遍历,中序遍历序列,能够创建出一棵唯一的二叉树,可以得出二叉树的后序遍历;
全栈程序员站长
2022/09/30
6320
【数据结构】树与二叉树(七):二叉树的遍历(先序、中序、后序及其C语言实现)
  二叉树是一种常见的树状数据结构,它由结点的有限集合组成。一个二叉树要么是空集,被称为空二叉树,要么由一个根结点和两棵不相交的子树组成,分别称为左子树和右子树。每个结点最多有两个子结点,分别称为左子结点和右子结点。
Qomolangma
2024/07/30
2720
【数据结构】树与二叉树(七):二叉树的遍历(先序、中序、后序及其C语言实现)
Binary Tree Traversals(二叉树) - HDU 1710
A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2.
ACM算法日常
2018/08/07
4010
Binary Tree Traversals(二叉树) - HDU 1710
数据结构实验之求二叉树后序遍历和层次遍历(SDUT 2137)
 输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的先序遍历序列,第二个字符串表示二叉树的中序遍历序列。
Lokinli
2023/03/09
2750
根据一棵树的中序遍历与后序遍历构造二叉树。
根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。
小雨的分享社区
2022/10/26
2910
c++二叉树的先序,中序,后序遍历_二叉树的构造
这里的根,指的是每个分叉子树(左右子树的根节点)根节点,并不只是最开始头顶的根节点,需要灵活思考理解,建议画图理解!!
全栈程序员站长
2022/11/04
2.3K0
c++二叉树的先序,中序,后序遍历_二叉树的构造
【题目/训练】二叉树的创建&&遍历(递归&&非递归)
这题我们主要用到dfs的想法 然后我们定义两个全局变量,preIndex,postIndex来分别表示当前前序遍历和后序遍历,遍历到哪一个节点,然后由于前序遍历的第一个节点就是根节点,我们先存下根节点,然后在后序遍历找到对应根节点的左右子树,然后返回根节点即可。
IsLand1314
2024/10/15
2320
【题目/训练】二叉树的创建&&遍历(递归&&非递归)
通过先序和中序数组生成后序数组
ppxai
2023/11/18
1760
玩透二叉树(Binary-Tree)及前序(先序)、中序、后序【递归和非递归】遍历
结点的度(Degree):结点的子树个数; 树的度:树的所有结点中最大的度数; 叶结点(Leaf):度为0的结点; 父结点(Parent):有子树的结点是其子树的根节点的父结点; 子结点/孩子结点(Child):若A结点是B结点的父结点,则称B结点是A结点的子结点; 兄弟结点(Sibling):具有同一个父结点的各结点彼此是兄弟结点; 路径和路径长度:从结点n1到nk的路径为一个结点序列n1,n2,…,nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度; 祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点; 子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙; 结点的层次(Level):规定根结点在1层,其他任一结点的层数是其父结点的层数加1; 树的深度(Depth):树中所有结点中的最大层次是这棵树的深度;
sunsky
2020/08/20
7850
玩透二叉树(Binary-Tree)及前序(先序)、中序、后序【递归和非递归】遍历
根据序列,进行中后序列输出
#include #include #include #include typedef struct BiTNode {//二叉树结点 char data; //数据 struct BiTNode* lchild, * rchild; //左右孩子指针 } BiTNode, * BiTree; int nn = 0; int CreateBiTree(BiTree* T) {//按先序序列创建二叉树 char data; sc
川川菜鸟
2021/10/18
2870
数据结构期末复习——还原二叉树(根据中序和后序遍历输出先序遍历)
参考博客:https://blog.csdn.net/qq_37708702/article/details/79644936
_DIY
2019/11/26
4680
数据结构树的专题
由于二叉树是有序的,为了避免混淆,对于无序树,我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。
用户2417870
2019/12/02
4170
数据结构期末复习——还原二叉树(根据先序和中序遍历输出先序遍历)
参考博客:https://blog.csdn.net/qq_37708702/article/details/79644068
_DIY
2019/11/27
4730
推荐阅读
相关推荐
PTA 根据后序和中序遍历输出先序遍历(25 分)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档