| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 882 人关注过本帖
标题:找错:关于用中序和后序系列建立二叉树的问题
只看楼主 加入收藏
君破浪
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2011-11-21
结帖率:50%
收藏
 问题点数:0 回复次数:2 
找错:关于用中序和后序系列建立二叉树的问题
这是我在书上看到的一个用先序和中序建立二叉树,随后我尝试用后序和中序建立二叉树,下面是程序代码,用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;
    }


}
搜索更多相关主题的帖子: 成功 检验 二叉树 color 
2011-11-28 02:46
君破浪
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2011-11-21
收藏
得分:0 
不用大家回答了,我找到错误的地方了,原来由于粗心,把中序和后序建立二叉树中递归时把函数名写错了。修改如下:
程序代码:
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;
2011-11-28 11:47
君破浪
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2011-11-21
收藏
得分:0 
还真是丢脸丢到家了,竟然犯如此低级的错误,惭愧啊!
2011-11-28 12:03
快速回复:找错:关于用中序和后序系列建立二叉树的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.048785 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved