中序和后序构造二叉树，但结果出现了一个问题，结果左子树一个节点错了！请高手帮忙看看！谢谢！急急急。。。
用中序和后序构造二叉树，但结果出现了一个问题，左边的一个节点反了？
请高手帮忙修改一下！谢谢！
#include <iostream>#include <string>#include <queue>using namespace std;#define OK 1#define ERROR -1void space(int n){ for (int i = 0; i < n; i++) cout << " ";}struct BiTNode{ char data; BiTNode *lchild, *rchild;};typedef BiTNode *BiTree;typedef int Status;Status CreatePreInBiTreeSq(BiTree &T,char PreOd[],int i,int j,char InOd[],int k,int h){ T = (BiTree)malloc(sizeof(BiTNode)); if (T) T->data = PreOd[i];//先序的第一个元素为树的根 int m=k; while(PreOd[i]!=InOd[m])//查找根在中序的位置 m++; if(m==k) T->lchild=NULL; else CreatePreInBiTreeSq(T->lchild,PreOd,i+1,i+m-k,InOd,k,m-1);//递归调用创建左子树 if(m==h) T->rchild=NULL; else CreatePreInBiTreeSq(T->rchild,PreOd,i+m-k+1,j,InOd,m+1,h);//递归调用创建右子数 return OK;}//根据中序和后序创建二叉树Status CreateInPosBiTreeSq(BiTree &T,char InOd[],int a,int b,char PosOd[],int c,int d){ T = (BiTree)malloc(sizeof(BiTNode)); if (T) T->data = PosOd[d];//后序的最后一个元素为树的根 int e=a; while(PosOd[d]!=InOd[e]) e++; if(e==a) T->lchild=NULL; else CreateInPosBiTreeSq(T->lchild,InOd,a,e-1,PosOd,c,c+e-1);//利用递归创建左子树 if(e==b) T->rchild=NULL; else CreateInPosBiTreeSq(T->rchild,InOd,e+1,b,PosOd,c+e,d-1);//利用递归创建右子树 d-(b-e)+1改为c+e-a return OK;}void ShowBiTree(BiTree T, int n){ if (!T) return; else { space(n); cout << T->data << endl; ShowBiTree(T->lchild, n+4); ShowBiTree(T->rchild, n+4); return; }}int main(){ BiTree T; int x; cout<<"请选择：1、根据先序和中序创建二叉树"<<endl; cout<<" 2、根据中序和后序创建二叉树"<<endl; cout<<"请输入："; cin>>x; switch(x) { case 1:{ int i(0),k(0); int j,h; cout<<"输入二叉树元素的个数："; cin>>j; h=j; char *PreOd,*InOd; PreOd=new char[j]; InOd=new char[h]; cout<<"输入先序："; for(int m=0;m<j;m++) cin>>PreOd[m]; cout<<"输入中序："; for(int m=0;m<h;m++) cin>>InOd[m]; j--;h--; CreatePreInBiTreeSq(T,PreOd,i,j,InOd,k,h); cout<<"输入二叉树图形"<<endl; ShowBiTree(T, 0); }break; case 2:{ int a(0),c(0); int b,d; cout<<"输入二叉树元素的个数："; cin>>b; d=b; char *InOd,*PosOd; InOd=new char[b]; PosOd=new char[d]; cout<<"输入中序："; for(int n=0;n<b;n++) cin>>InOd[n]; cout<<"输入后序："; for(int n=0;n<d;n++) cin>>PosOd[n]; b--;d--; CreateInPosBiTreeSq(T,InOd,a,b,PosOd,c,d); cout<<"输入二叉树图形"<<endl; ShowBiTree(T, 0); }break; default:break; }}#include <iostream>#include <string>using namespace std;#define OK 1#define ERROR -1void space(int n){ for (int i = 0; i < n; i++) cout << " ";}struct BiTNode{ char data; BiTNode *lchild, *rchild;};typedef BiTNode *BiTree;typedef int Status;Status CreatePreInBiTreeSq(BiTree &T,char PreOd[],int i,int j,char InOd[],int k,int h){ T = (BiTree)malloc(sizeof(BiTNode)); if (T) T->data = PreOd[i];//先序的第一个元素为树的根 int m=k; while(PreOd[i]!=InOd[m])//查找根在中序的位置 m++; if(m==k) T->lchild=NULL; else CreatePreInBiTreeSq(T->lchild,PreOd,i+1,i+m-k,InOd,k,m-1);//递归调用创建左子树 if(m==h) T->rchild=NULL; else CreatePreInBiTreeSq(T->rchild,PreOd,i+m-k+1,j,InOd,m+1,h);//递归调用创建右子数 return OK;}//根据中序和后序创建二叉树Status CreateInPosBiTreeSq(BiTree &T,char InOd[],int a,int b,char PosOd[],int c,int d){ T = (BiTree)malloc(sizeof(BiTNode)); if (T){ T->data = PosOd[d];//后序的最后一个元素为树的根 printf("Root:%c\n",T->data); } cout<<"a="<<a<<",b="<<b<<",c="<<c<<",d="<<d<<endl; int e=a; while(PosOd[d]!=InOd[e]) e++; if(e==a) T->lchild=NULL; else CreateInPosBiTreeSq(T->lchild,InOd,a,e-1,PosOd,c,c+e-1-a);//修改一 if(e==b) T->rchild=NULL; else CreateInPosBiTreeSq(T->rchild,InOd,e+1,b,PosOd,-b+e+1+d-1,d-1);//修改二 return OK;}void ShowBiTree(BiTree T, int n){ if (!T) return; else { space(n); cout << T->data << endl; ShowBiTree(T->lchild, n+4); ShowBiTree(T->rchild, n+4); return; }}int main(){ BiTree T; int x; cout<<"请选择：1、根据先序和中序创建二叉树"<<endl; cout<<" 2、根据中序和后序创建二叉树"<<endl; cout<<"请输入："; cin>>x; switch(x) { case 1:{ int i(0),k(0); int j,h; cout<<"输入二叉树元素的个数："; cin>>j; h=j; char *PreOd,*InOd; PreOd=new char[j]; InOd=new char[h]; cout<<"输入先序："; for(int m=0;m<j;m++) cin>>PreOd[m]; cout<<"输入中序："; for(int m=0;m<h;m++) cin>>InOd[m]; j--;h--; CreatePreInBiTreeSq(T,PreOd,i,j,InOd,k,h); cout<<"输入二叉树图形"<<endl; ShowBiTree(T, 0); }break; case 2:{ int a(0),c(0); int b,d; cout<<"输入二叉树元素的个数："; cin>>b; d=b; char *InOd,*PosOd; InOd=new char[b]; PosOd=new char[d]; cout<<"输入中序："; for(int n=0;n<b;n++) cin>>InOd[n]; cout<<"输入后序："; for(int n=0;n<d;n++) cin>>PosOd[n]; b--;d--; CreateInPosBiTreeSq(T,InOd,a,b,PosOd,c,d); cout<<"输入二叉树图形"<<endl; ShowBiTree(T, 0); }break; default:break; }}