文档章节

根据二叉树前序和中序遍历,生成二叉树

哭哭吓唬你
 哭哭吓唬你
发布于 2013/10/21 11:24
字数 511
阅读 51
收藏 0
点赞 0
评论 0

import java.util.Scanner;

/**
 *
 * 项目名称:jobdu
 * 类名称:Main2
 * 类描述:构建二叉树
 * 创建人:黄传聪
 * 创建时间:2013-10-21 上午10:24:10
 * 修改人:
 * 修改时间:
 * 修改备注:
 * @version
 */
public class Main2 {

	private char node;
	private Main2 lTree;
	private Main2 rTree;
	
	
	public Main2(char node) {
		this.node = node;
		this.lTree = null;
		this.rTree = null;
	}


	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			String preOrder = scanner.next();
			String inOrder = scanner.next();
			//生成二叉树
			Main2 binTree = new Main2(preOrder.charAt(0));
			generator(binTree,preOrder,inOrder);
			post(binTree);
			System.out.println();
		}
		
		
	}


	private static void post(Main2 binTree) {
		// TODO Auto-generated method stub
		if(binTree != null){
			post(binTree.lTree);
		post(binTree.rTree);
		System.out.print(binTree.node);
		}
	}


	private static Main2 generator(Main2 root ,String preOrder, String inOrder) {
		// TODO Auto-generated method stub
		
//		Main2 root = new Main2(preOrder.charAt(0));
		//根节点在中序遍历中的位置
		int index = inOrder.indexOf(preOrder.charAt(0));
		//拆分中序遍历的左右子树
		String lInorder = inOrder.substring(0,index);
		String rInorder = inOrder.substring(index+1,inOrder.length());
		//拆分前序遍历节点
		String lPreOrder = preOrder.substring(1,preOrder.length()-rInorder.length());
		String rPreOrder = preOrder.substring(preOrder.length()-rInorder.length(),preOrder.length());
		
		if(lPreOrder.length()>0){
			root.lTree = new Main2(lPreOrder.charAt(0));
			generator(root.lTree,lPreOrder,lInorder);
		}
		if(rPreOrder.length()>0){
			root.rTree = new Main2(rPreOrder.charAt(0));
			generator(root.rTree,rPreOrder,rInorder);
		}
		return null;
	}

}
c++ 实现: 1.直接输出方式实现;2. 先创建二叉树,再遍历

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

struct Node{
	char data;
	Node* lChild;
	Node* rChild;

	Node(char data){
		this->data = data;
		lChild = NULL;
		rChild = NULL;
	}
};

//生成二叉树
void generator(Node* root, const string &pre, const string &mid){

	if(pre.size() >0){
		int index = mid.find(pre[0]);

		string pre_pre = pre.substr(1,index);
		string pre_mid = mid.substr(0,index);


		string post_pre = pre.substr(index+1,pre.size() - pre_pre.size() );
		string post_mid = mid.substr(index+1,mid.size() - pre_mid.size());
		if(pre_pre.size() > 0){
			root->lChild = new Node(pre_pre[0]);
			generator(root->lChild, pre_pre, pre_mid);
		}

		if(post_pre.size() > 0){
			root->rChild = new Node(post_pre[0]);
			generator(root->rChild, post_pre, post_mid);
		}
	}
}


//直接输出
void pre_mid_post(const string &pre, const string &mid){
	if(pre.size() <= 0) return;
	if(pre.size() == 1){
		cout<<pre;
		return;
	}

	//拆分字符串
	//前序遍历,第一个字符为根节点
	int k = mid.find(pre[0]);

	string pre_pre = pre.substr(1,k);
	string pre_mid = mid.substr(0,k);
	pre_mid_post(pre_pre, pre_mid);
	string post_pre = pre.substr(k+1,pre.size() - k - 1);
	string post_mid = mid.substr(k+1,mid.size() - k - 1);
	pre_mid_post(post_pre,post_mid);
	cout<<mid[k];

}
int main() {
	void post(Node* );
	string pre, mid;
	while(cin>>pre>>mid){
		pre_mid_post(pre, mid);
		cout<<endl;

		Node* root = new Node(pre[0]);
		generator(root , pre , mid);
//		cout<<root->data;
		post(root);
	}
	return 0;
}


//后序遍历二叉树
void post(Node* root){
	if(root){
		post(root->lChild);
		post(root->rChild);
		cout<<root->data;
	}
}





© 著作权归作者所有

共有 人打赏支持
哭哭吓唬你
粉丝 3
博文 98
码字总数 39471
作品 0
石景山
程序员
【编程题目】重建二叉树(C++实现)

题目描述:输入二叉树的前序遍历和中序遍历结果 ,请重建出该二叉树,返回其头节点并给出后序遍历序列。假设输入的遍历序列不包含重复数字。 题目分析: 根据前序遍历和中序遍历的特征,我们...

qq_28869927
2017/03/17
0
0
JS - 二叉树算法实现与遍历 (更新中...)

一、关于二叉树: 截图来自:https://segmentfault.com/a/1190000000740261 温馨提示:学习以及使用二叉树概念,心中永远有这么一个图,对于理解和接受二叉树有很大的帮助。 截图来自慕课:h...

鋒o丫头
2017/10/25
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
跟我一起学算法系列6---重建二叉树

1.题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,...

充电实践
2017/12/31
0
0
剑指Offer学习总结-重建二叉树

剑指Offer学习总结-重建二叉树 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog.163.co...

wwlcsdn000
01/16
0
0
12.遍历二叉树与二叉树的建立

一、遍历二叉树 1.定义 二叉树的遍历(travering binary tree)是指从根结点出发。依照某种次序依次訪问二叉树中的全部结点,使得每一个结点被訪问一次且仅被訪问一次。 2.前序遍历 (1)规则:若...

技术mix呢
2017/12/01
0
0
前序中序求后序的java算法

datacube
2016/07/07
27
0
【剑指Offer】重建二叉树——JavaScript实现

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,...

highboys
2017/11/27
0
0
剑指Offer-根据二叉树的前序和后序遍历重建二叉树

原文地址:点击打开链接 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8} 和...

z956281507
2017/12/13
0
0
数据结构学习笔记(树、二叉树)

                       树(一对多的数据结构) 树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树种: (1)有且仅有一个特定的称为根(Root)...

希希里之海
2017/05/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
4
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
1
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
165
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0
python里求解物理学上的双弹簧质能系统

物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定。假定没有外力时,两个弹簧的长度为L1和L2。 由于两物体有重力,那么...

wangxuwei
昨天
0
0
apolloxlua 介绍

##项目介绍 apolloxlua 目前支持javascript到lua的翻译。可以在openresty和luajit里使用。这个工具分为两种模式, 一种是web模式,可以通过网页使用。另外一种是tool模式, 通常作为大规模翻...

钟元OSS
昨天
2
0
Mybatis入门

简介: 定义:Mybatis是一个支持普通SQL查询、存储过程和高级映射的持久层框架。 途径:MyBatis通过XML文件或者注解的形式配置映射,实现数据库查询。 特性:动态SQL语句。 文件结构:Mybat...

霍淇滨
昨天
2
0
开发技术瓶颈期,如何突破

前言 读书、学习的那些事情,以前我也陆续叨叨了不少,但总觉得 “学习方法” 就是一个永远在路上的话题。个人的能力、经验积累与习惯方法不尽相同,而且一篇文章甚至一本书都很难将学习方法...

_小迷糊
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部