计算机视觉技术 XShell java设计模式 CSS选择器 Hibernate Transformer iis arraylist charts orm scripting jboss null vb6 Backbonejs pythonapi python中的zip python循环语句 python图形化编程 python参数 python条件判断 python正则表达 python基础教程免费 python中re模块 java9 java开发环境 javasocket通信 java什么是多态 java抛出自定义异常 sql语句大全实例教程 kafka中文教程 服务器系统下载 房产证生成器 蒙文字体 笔记本外接显示器好吗 vbs表白代码 java电子书 矩阵分析与应用 js关闭当前页面 骰子表情
当前位置: 首页 > 学习教程  > 编程语言

C++西电复试机试---2009ProblemD

2021/2/13 17:19:15 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目描述: 已知某二叉树的先序序列和中序序列,编程计算并输出该二叉树的后序序列。 输入输出: 有多组数据,每组分为两行输入,第一行表示指定二叉树的先序序列,第二行表示该二叉树的中序序列,序…

题目描述:

已知某二叉树的先序序列和中序序列,编程计算并输出该二叉树的后序序列。


输入输出:

有多组数据,每组分为两行输入,第一行表示指定二叉树的先序序列,第二行表示该二叉树的中序序列,序列元素均为大写英文字符,表示二叉树的结点。
对于每组数组,在一行上输出该二叉树的后序序列。

代码(c++):

#include<iostream>
#include<string>
using namespace std;

typedef struct Tree {
	char ch;
	Tree* lchild;
	Tree* rchild;
	Tree(char ch) :ch(ch) {}
}Tree;

// 建树
Tree* build(string prior, string inorder) {
	if (prior.length() == 0) 
		return NULL;
	char ch = prior[0];
	Tree* root = new Tree(ch);
	int index = inorder.find(ch);
	root->lchild = build(prior.substr(1, index), inorder.substr(0, index));
	root->rchild = build(prior.substr(index + 1), inorder.substr(index + 1));
	return root;
}
// 后序遍历
void postorder(Tree* root) {
	if (root == NULL) return;
	postorder(root->lchild);
	postorder(root->rchild);
	cout << root->ch;
}

int main() {
	string prior, inorder;
	while (cin >> prior >> inorder) {
		Tree* root = build(prior, inorder);
		postorder(root);
		cout << endl;
	}
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_700121.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?