找错:关于用中序和后序系列建立二叉树的问题
这是我在书上看到的一个用先序和中序建立二叉树,随后我尝试用后序和中序建立二叉树,下面是程序代码,用c++写的,编译没问题,能通过,其中用先序和中序建立二叉树能够建立,三个遍历是为了用来检验是否建立成功。其中我改写的用后序和中序建立二叉树,总是出错误,不能建立。求高手解答为什么,到底哪里出错了?程序代码:
#include<iostream.h> #include <string.h> const int maxsize=100; typedef char datatype; typedef struct node *pointer; //二叉链表类型 struct node{ datatype data; pointer lchild, rchild; }; typedef pointer bitree; pointer data[maxsize]; bitree prein_creat(datatype Pre[],int ps, int pe, datatype In[],int is, int ie)//先序和中序建立二叉树,ps、pe、is、ie分别为区间的起止节点 { bitree t; int i; if(ps>pe) return NULL; t=new node; t->data=Pre[ps]; i=is; while(In[i]!=Pre[ps]) i++; t->lchild=prein_creat(Pre,ps+1,ps+i-is,In,is,i-1); t->rchild=prein_creat(Pre,ps+i-is+1,pe,In,i+1,ie); return t; } bitree postin_creat(datatype Post[],int ps, int pe, datatype In[],int is, int ie) //后序和中序建立二叉树,ps、pe、is、ie分别为区间的起止节点 { bitree t; int i; if(ps>pe) return NULL; t=new node; //生成根节点 t->data=Post[pe]; i=is; while(In[i]!=Post[pe]) i++;//寻找中序序列中根的位置i t->rchild=prein_creat(Post,ps+i-is,pe-1,In,i+1,ie); //生成右子树 t->lchild=prein_creat(Post,ps,ps+i-is-1,In,is,i-1); //生成左子树 return t; } void preorder(bitree t)//先根遍历 { if(t==NULL) return; cout<<t->data<<" "; //访问根 preorder(t->lchild); //先根遍历左子树 preorder(t->rchild); //先根遍历右子树 } void inorder(bitree t)//中根遍历 { if(t==NULL) return; inorder(t->lchild); //中根遍历左子树 cout<<t->data<<" "; //访问根 inorder(t->rchild); //中根遍历右子树 } void postorder(bitree t)//后根遍历 { if(t==NULL) return; postorder(t->lchild); //后根遍历左子树 postorder(t->rchild); //后根遍历右子树 cout<<t->data<<" "; //访问根 } void main() { int i,j; bitree t; datatype Pre[maxsize],In[maxsize],Post[maxsize]; datatype x; cout<<"二叉树的操作:5、先序和中序建立,6、后序和中序建立;"<<"7、先根遍历,8、中根遍历,9、后根遍历"<<endl; cout<<"请选择要执行的函数,输入对应的序号:"; cin>>i; while(i!=0) { switch(i) { case 5: cout<<"请输入先序序列:"<<endl; cin>>Pre; cout<<"请输入中序序列:"<<endl; cin>>In; t=prein_creat(Pre,0,strlen(Pre)-1,In,0,strlen(In)-1); break; case 6: cout<<"请输入后序序列:"<<endl; cin>>Post; cout<<"请输入中序序列:"<<endl; cin>>In; t=prein_creat(Post,0,strlen(Post)-1,In,0,strlen(In)-1); break; case 7: cout<<"该二叉树的先跟遍历为:"; preorder(t); cout<<endl<<endl; break; case 8: cout<<"该二叉树的中跟遍历为:"; inorder(t); cout<<endl<<endl; break; case 9: cout<<"该二叉树的后跟遍历为:"; postorder(t); cout<<endl<<endl; break; } cout<<"请选择要执行的函数,输入对应的序号:"; cin>>i; } }