+ -
当前位置:首页 → 问答吧 → 找错:关于用中序和后序系列建立二叉树的问题

找错:关于用中序和后序系列建立二叉树的问题

时间:2011-11-28

来源:互联网

这是我在书上看到的一个用先序和中序建立二叉树,随后我尝试用后序和中序建立二叉树,下面是程序代码,用c++写的,编译没问题,能通过,其中用先序和中序建立二叉树能够建立,三个遍历是为了用来检验是否建立成功。其中我改写的用后序和中序建立二叉树,总是出错误,不能建立。求高手解答为什么,到底哪里出错了?

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;

作者: rain097790   发布时间: 2011-11-28

来支持一下lz,我的博客里有   关于前序中序后序的相互转化   欢迎参观
http://hi.baidu.com/%CC%E1%CE%CA%D5%DF1022/blog/item/b3809b8023a0d8be0cf4d28e.html

作者: hss871838309   发布时间: 2011-11-28

还真是丢脸丢到家了,竟然犯如此低级的错误,惭愧啊!

作者: rain097790   发布时间: 2011-11-28

热门下载

更多