## 根据二叉树前序和中序遍历，生成二叉树 原

哭哭吓唬你

``````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;
}
}``````

### 哭哭吓唬你

【编程题目】重建二叉树（C++实现）

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

2017/10/25
0
0

2018/11/25
0
0

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

2017/12/31
0
0
12.遍历二叉树与二叉树的建立

2017/12/01
0
0

MySQL查询执行

45分钟前
0
0
CDH5动静态资源池配置与回滚

hblt-j
49分钟前
3
0
WordPress仿站实战教程

52分钟前
3
0

https://github.com/nothings/stb 目前一般主流的图像格式也就是bmp，jpg，png，tga，dds，除了DDS一般是给DX用的，虽然一堆OpenGL程序也有用的，但是我一般只用png和tga， png不用说了，带a...

robslove

1
0
Spring 事务提交回滚源码解析

TSMYK

2
0