找错:关于用中序和后序系列建立二叉树的问题
时间:2011-11-28
来源:互联网
这是我在书上看到的一个用先序和中序建立二叉树,随后我尝试用后序和中序建立二叉树,下面是程序代码,用c++写的,编译没问题,能通过,其中用先序和中序建立二叉树能够建立,三个遍历是为了用来检验是否建立成功。其中我改写的用后序和中序建立二叉树,总是出错误,不能建立。求高手解答为什么,到底哪里出错了?
C/C++ code
C/C++ code
#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分别为区间的起止节点,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; } }
作者: rain097790 发布时间: 2011-11-28
不用大家回答了,我找到错误的地方了,原来由于粗心,把中序和后序建立二叉树中递归时把函数名写错了。修改如下:
程序代码:
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=postin_creat(Post,ps+i-is,pe-1,In,i+1,ie); //生成右子树
t->lchild=postin_creat(Post,ps,ps+i-is-1,In,is,i-1); //生成左子树
return t;
}
还有主函数那里,调用函数也写错了:
程序代码:
case 6:
cout<<"请输入后序序列:"<<endl;
cin>>Post;
cout<<"请输入中序序列:"<<endl;
cin>>In;
t=postin_creat(Post,0,strlen(Post)-1,In,0,strlen(In)-1);
break;
程序代码:
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=postin_creat(Post,ps+i-is,pe-1,In,i+1,ie); //生成右子树
t->lchild=postin_creat(Post,ps,ps+i-is-1,In,is,i-1); //生成左子树
return t;
}
还有主函数那里,调用函数也写错了:
程序代码:
case 6:
cout<<"请输入后序序列:"<<endl;
cin>>Post;
cout<<"请输入中序序列:"<<endl;
cin>>In;
t=postin_creat(Post,0,strlen(Post)-1,In,0,strlen(In)-1);
break;
作者: rain097790 发布时间: 2011-11-28
来支持一下lz,我的博客里有 关于前序中序后序的相互转化 欢迎参观
http://hi.baidu.com/%CC%E1%CE%CA%D5%DF1022/blog/item/b3809b8023a0d8be0cf4d28e.html
http://hi.baidu.com/%CC%E1%CE%CA%D5%DF1022/blog/item/b3809b8023a0d8be0cf4d28e.html
作者: hss871838309 发布时间: 2011-11-28
还真是丢脸丢到家了,竟然犯如此低级的错误,惭愧啊!
作者: rain097790 发布时间: 2011-11-28
相关阅读 更多
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读:74
-
如何安装mysql8.0
阅读:31
-
Word快速设置标题样式步骤详解
阅读:28
-
20+道必知必会的Vue面试题(附答案解析)
阅读:37
-
HTML如何制作表单
阅读:22
-
百词斩可以改天数吗?当然可以,4个步骤轻松修改天数!
阅读:31
-
ET文件格式和XLS格式文件之间如何转化?
阅读:24
-
react和vue的区别及优缺点是什么
阅读:121
-
支付宝人脸识别如何关闭?
阅读:21
-
腾讯微云怎么修改照片或视频备份路径?
阅读:28