实在是恨自己智商欠费，一个二叉树搞了好长时间才弄清！！！
怎样通过先序和中序确定二叉树？
我的算法设计思路参考学习网上的，但代码是自己实现的，其实还是在创建二叉树的基础上添加一些条件。我们刚开始根据先序序列中第一个数据，在中序序列中找与该结点数据相等的与元素，将中序序列中该元素所在下标返回。创建节点，将先序序列的第一个有效元素存起来。将中序序列中与前序序列当前第一个元素相等的元素所在位置置为’\0’，并将前序序列中的该元素所在位置值置为’\0’，先序序列的首个有效元素也同时应改为下一个元素(即此时遍历下标应后移)。这是建立二叉树之前所做的工作。
创建二叉树还是用递归，根据以上返回的下标将中序序列分为两部分，判断左边为空，就将创建节点的左孩子置为空，右边同理。
若不为空，前半部分为左子树，后半部分为右子树。
将前序序列和中序序列前半部分，以及创建的结点的左孩子指针传进去。递归调用函数。
将前序序列和中序序列后半部分，以及创建的结点的右孩子指针传进去。递归调用函数。
以上所述为火星人理解思路，看不懂不怪你们，怪我，表达上确实欠缺逻辑性，下面我们看代码就行～～～
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;
typedef struct node{
char ch ;
struct node * l,*r ;
}node_t,*node_l;
void create_tree(node_l * root,char prelist[],char midlist[]);
int findIndex(char prelist,char* midlist);
void print(node_l root);
int main(){
node_l root ;
char prelist[100];
char midlist[100];
bzero(prelist,sizeof(prelist));
bzero(midlist,sizeof(midlist));
cin>>prelist;
cin>>midlist;
create_tree(&root,prelist,midlist);
print(root);
}
void print(node_l root){
if(root){
print(root->l);
print(root->r);
cout<<root->ch<<"";
}
}
//该函数时恢复二叉树的，root为根指，prelist为先序序列，midlist为中序序列
//三者在恢复二叉树的过程中时变化的
void create_tree(node_l* root,char prelist[],char midlist[]){
//定义静态变量，因为每次前序每一个元素，就销毁一个元素，
//下标也作相应的移动。
static int index = 0;
int mid_index ;
//传入前序序列的首元素，在中序列中搜索 ，记录元素在中序序列中所处的下标
mid_index = findIndex(prelist[index],midlist);
*root = (node_l)malloc(sizeof(node_t));
//将节点数据存在根结点中
(*root)->ch = prelist[index];
将先序已遍历的数据全置为‘\0’
prelist[index++]='\0' ;
//将中序的那个数据所处位置置为'\0'
midlist[mid_index]='\0';
//判断那个位置之前是否为空，若非空，说明当前节点有左子树，继续递归创建左子树
if(midlist[mid_index-1]!='\0'){
create_tree(&((*root)->l),prelist,midlist);
}
//否则的话就将当前节点的左孩子置为空
else{
(*root)->l = NULL ;
}
//若当前节点有右孩子，递归创建
if(midlist[mid_index+1]!='\0'){
create_tree(&((*root)->r),prelist,&midlist[mid_index+1]);
}
else{
(*root)->r = NULL ;
}
}
//根据传进来的中序首元素节点，在中序序列中找该结点下标。
int findIndex(char pre,char * mid){
int i ;
for(i = 0; *(mid+i)!= '\0' ;i++){
if(pre == *(mid+i)){
return i ;
}
}
return 0;
}
根据后序和中序创建二叉树时同样的道理，自己在这个基础上尝试找一些规律，就可以自己恢复了。
后序和中序
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;
typedef struct node{
char ch ;
struct node * l,*r ;
}node_t,*node_l;
void create_tree(node_l * root,char lastlist[],char midlist[]);
int findIndex(char last,char* midlist);
void print(node_l root);
int main(){
node_l root ;
char lastlist[100];
char midlist[100];
bzero(lastlist,sizeof(lastlist));
bzero(midlist,sizeof(midlist));
cin>>midlist;
cin>>lastlist;
create_tree(&root,lastlist,midlist);
print(root);
}
void print(node_l root){
if(root){
cout<<root->ch<<"";
print(root->l);
print(root->r);
}
}
void create_tree(node_l* root,char lastlist[],char midlist[]){
static int index = strlen(lastlist)-1;
int mid_index ;
mid_index = findIndex(lastlist[index],midlist);
*root = (node_l)malloc(sizeof(node_t));
(*root)->ch = lastlist[index];
lastlist[index--]='\0' ;
if(index==-1)return ;
midlist[mid_index]='\0';
if(midlist[mid_index+1]!='\0'){
create_tree(&((*root)->r),lastlist,&midlist[mid_index+1]);
}
else{
(*root)->r = NULL ;
}
if(midlist[mid_index-1]!='\0'){
create_tree(&((*root)->l),lastlist,midlist);
}
else{
(*root)->l = NULL ;
}
}
int findIndex(char last,char * mid){
int i ;
for(i = 0; *(mid+i)!= '\0' ;i++){
if(last == *(mid+i)){
return i ;
}
}
return 0;
}