前序加中序
void Create(BiTree &T,int *pre,int *in,int n){ if(n<=0||!pre||!in){T=NULL;return ;} T=new BiTNode; T->data=*pre; int *p; for(p=in;p<in+n;p++) if(*p==*pre)break; int k = p-in; //下面两句话比较关键 //左子树前序向右移动1，中序不动，大小变为k Create(T->lchild,pre+1,in,k); //右子树前序移动k+1，中序也移动k+1,大小变为n-k-1 Create(T->rchild,pre+k+1,in+k+1,n-k-1); //与后序的区别在于，后序左子树不移动，右子树移动k，比前序少1}
后序加中序：
void Create(BiTree &T,int *post,int *in,int n){ if(n<=0||post==NULL||in==NULL){T= NULL;return ;} T = new BiTNode; T->data=*(post+n-1); int *p; for(p=in;p<in+n;p++) { if(*p==*(post+n-1))break; } int k=p-in; Create(T->lchild,post,in,k); Create(T->rchild,post+k,in+k+1,n-k-1);}
例题：根据后序序列与中序序列构造二叉树并且层序输出二叉树
L2-006 树的遍历 (25分)
#include <bits/stdc++.h>using namespace std;typedef struct node{ int data; node *lchild,*rchild;}BiTNode,*BiTree;//queue<BiTree>q;void Create(BiTree &T,int *pre,int *in,int n){ if(n<=0||pre==NULL||in==NULL){T= NULL;return ;} T = new BiTNode; T->data=*(pre+n-1); int *p; for(p=in;p<in+n;p++) { if(*p==*(pre+n-1))break; } int k=p-in; Create(T->lchild,pre,in,k); Create(T->rchild,pre+k,in+k+1,n-k-1);}/*void re(BiTree &T){ if(!T)return ; if(T->lchild==NULL&&T->rchild==NULL)return ; BiTree t = T->lchild; T->lchild=T->rchild; T->rchild=t; re(T->lchild); re(T->rchild);}*/void print(BiTree T){ int flag=0; q.push(T); while(!q.empty()) { BiTree tmp = q.front();q.pop(); if(!flag)cout<<tmp->data; else cout<<" "<<tmp->data; flag=1; if(tmp->lchild!=NULL) q.push(tmp->lchild); if(tmp->rchild!=NULL) q.push(tmp->rchild); }}int main(){ int n; cin>>n; int pre[35],in[35]; for(int i=0;i<n;i++) { scanf("%d",pre+i); } for(int i=0;i<n;i++) { scanf("%d",in+i); } BiTree T; Create(T,pre,in,n); print(T); return 0;}