Problem C.二叉树（2017计算机）

超、凢脫俗 2023-07-16 03:49 16阅读 0赞

题目描述

> 输入二叉树的前序遍历和中序遍历结果，输出二叉树的后序遍历结果 输入格式 第一行为二叉树先序遍历结果 第二行为二叉树中序遍历结果。

输出格式

> 二叉树后序遍历结果。

Example  
Inputs

426315
    623415

Outputs

632514

#include<bits/stdc++.h>
    using namespace std;
    typedef struct BNode { 
    	char data;
    	struct BNode *lchild,*rchild;
    } BNode,*btree;
    btree buildtree(char pre[],int l1,int r1,char in[],int l2,int r2) { 
    	BNode *t;
    	int i;
    	t=(BNode *)malloc(sizeof(BNode));
    	t->data=pre[l1];
    	for(i=l2; in[i]!=t->data; i++); //寻找根在中序遍历的位置
    	int len1=i-l2,len2=r2-i;
    	if(len1>0) {  //如果有左子树
    		t->lchild=buildtree(pre,l1+1,l1+len1,in,l2,l2+len1-1);
    	} else
    		t->lchild=NULL;
    	if(len2>0) { 
    		t->rchild=buildtree(pre,r1-len2+1,r1,in,r2-len2+1,r2);
    	} else 
    		t->rchild=NULL;
    	return t;
    }
    void postorder(btree t) { 
    	if(t->lchild) postorder(t->lchild);
    	if(t->rchild) postorder(t->rchild);
    	cout<<t->data;
    }
    int main() { 
    	BNode *t;
    	int i=0;
    	string pre,in;
    	cin>>pre>>in;
    	int l1=pre.size();
    	char str1[l1],str2[l1];
    	for(int i=0; i<l1; i++) { 
    		str1[i]=pre[i];
    		str2[i]=in[i];
    	}
    	t=buildtree(str1,0,l1-1,str2,0,l1-1);
    	postorder(t);
    	cout<<endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++】二叉搜索树

二叉搜索树的相关基本操作

柔情只为你懂/ 2024年04月27日 07:33/ 0 赞/ 128 阅读

相关【二叉树教程详解以及C语言/C++实现二叉树】

二叉树二叉树是一种特殊的树状数据结构，其中每个节点最多有两个子节点。一个节点称为父节点，两个子节点分别称为左子节点和右子节点。一、什么是二叉树二叉树是一种特

秒速五厘米/ 2024年03月17日 13:05/ 0 赞/ 92 阅读

相关 C++ 复制二叉树

[原文链接][Link 1] 使用C++构建一个二叉树并复制、输出。程序： include <stdio.h> include <stdlib.h>

痛定思痛。/ 2023年10月08日 11:31/ 0 赞/ 47 阅读

相关 2012.计算机院.Problem C.二叉排序树

题目描述: 二叉排序树，也称为二叉查找树。可以是一颗空树,也可以是一颗具有如下特性的非空二叉树: 若左子树非空,则左子树上所有节点关键字值均不大于根节点的关键字值;

淡淡的烟草味﹌/ 2023年07月21日 08:43/ 0 赞/ 34 阅读

相关 Problem C.二叉树（2017计算机）

题目描述 > 输入二叉树的前序遍历和中序遍历结果，输出二叉树的后序遍历结果输入格式第一行为二叉树先序遍历结果第二行为二叉树中序遍历结果。输出格式 > 二叉树后序遍

超、凢脫俗/ 2023年07月16日 03:49/ 0 赞/ 17 阅读

相关 Problem B.字符串操作（2017计算机）

题目描述给定一个长度为n (n>=1)的字符串序列，标记为\[a1a2…an\]，在字符串序列上定义以下5种操作类型，分别标号为1,2,3,4,5，同时l和r分别表示al

骑猪看日落/ 2023年07月16日 03:46/ 0 赞/ 35 阅读

相关二叉搜索树--C++

![在这里插入图片描述][20210511151216134.png] 二叉搜索树目录: 一.概念二.接口声明

超、凢脫俗/ 2023年01月19日 12:54/ 0 赞/ 59 阅读

相关 C语言实现二叉树---＞二叉查找树

声明代码实现都是自己写的，而且没有借鉴别人的代码，也没有看任何教程，只看了下二叉树的具体定义，知道大概是个什么东西说这些只是为了说明下列代码实现肯定不是最优的，甚

柔情只为你懂/ 2023年01月13日 06:19/ 0 赞/ 236 阅读

相关 C 二叉树

\include<malloc.h> \include<stdio.h> \include<process.h> int da = 0; typedef struc

刺骨的言语ヽ痛彻心扉/ 2022年05月19日 09:27/ 0 赞/ 175 阅读

相关二叉树c++实现

[二叉树c++实现][c] \--- 欢迎指正--- 二叉树特点：　要么为空树；要么，当前结点的左孩子比当前结点值小，当前结点的右孩子比当前结点的值大。 1、插入

左手的ㄟ右手/ 2022年02月28日 08:18/ 0 赞/ 250 阅读