首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

先序中序建二叉树出现的奇怪有关问题

2012-03-15 
先序中序建二叉树出现的奇怪问题#includestdafx.h #includemalloc.h #includestdio.h #defineOVERFL

先序中序建二叉树出现的奇怪问题
#include   "stdafx.h "
#include   "malloc.h "
#include   "stdio.h "

#define   OVERFLOW   -2
#define   OK   1
#define   ERROR   0
#define   TRUE   1
#define   FALSE   0
#define   NULL   0
#define   LEN   7

typedef   char   TElemType;
typedef   int   Status;

typedef   struct   BiTNode
{
TElemType   data;
struct   BiTNode   *lchild,   *rchild;
}BiTNode,   *BiTree;//定义结点


Status   PrintElement(   TElemType   e   )
{
printf( "%c ",e);
return   OK;
}


Status   PreOrderTraverse(   BiTree   T,   Status   (*   Visit)(TElemType   e)   )
{
if(T)
{
if(Visit(T-> data))
if(PreOrderTraverse(T-> lchild,Visit))
if(PreOrderTraverse(T-> rchild,Visit))
return   OK;
return   ERROR;
}
else   return   OK;
}//先序遍历

Status   InOrderTraverse(   BiTree   T,   Status   (*   Visit)(TElemType   e)   )
{
if(T)
{
if(InOrderTraverse(T-> lchild,Visit))
if(Visit(T-> data))
if(InOrderTraverse(T-> rchild,Visit))
return   OK;
return   ERROR;
}
else   return   OK;
}//中序遍历

Status   PostOrderTraverse(   BiTree   T,   Status   (*   Visit)(TElemType   e)   )
{
if(T)
{
if(PostOrderTraverse(T-> lchild,Visit))
if(PostOrderTraverse(T-> rchild,Visit))
if(Visit(T-> data))
return   OK;
return   ERROR;
}
else   return   OK;
}//后序遍历


Status   Search(TElemType   ino[],   TElemType   e)
{
int   k,   b;
for(b=0;   b <LEN;   b++)
if(ino[b]   ==   e)
k   =   b;
if(k   ==   LEN)
k   =   -1;
return   k;
}


void   CrtBT(BiTree   &T,   TElemType   pre[],   TElemType   ino[],   int   ps,   int   is,   int   n   )  
{
    //   已知pre[ps..ps+n-1]为二叉树的先序序列,  
    //   ino[is..is+n-1]为二叉树的中序序列,本算
    //   法由此两个序列构造二叉链表  
      int   k;
      if   (n   ==   0)  
      T   =   NULL;
      else  
      {
              k   =   Search(ino,   pre[ps]);   //   在中序序列中查询
              if   (k   ==   -1)  
      T   =   NULL;
              else
      {
        T   =   (BiTNode*)malloc(sizeof(BiTNode));
T-> data   =   pre[ps];
if   (k   ==   is)   //
T-> lchild   =   NULL;
else
CrtBT(T-> lchild,   pre,   ino,   ps+1,   is,   k-is   );
if   (k   =   is+n-1)
T-> rchild   =   NULL;
else  
CrtBT(T-> rchild,   pre,   ino,     ps+1+(k-is),   k+1,   n-(k-is)-1);


      }//else
      }   //else
}   //   CrtBT      


int   main()
{
BiTree   T;
TElemType   pre[LEN],   ino[LEN];
int   ps   =   0,   is   =   0;

printf( "请输入先序序列:\n ");
scanf( "%s ",pre);
printf( "\n请输入中序序列:\n ");
scanf( "%s ",ino);

        CrtBT(T,   pre,   ino,   ps,   is,   LEN);

printf( "\n建完树后,其先序序列为:\n ");
        PreOrderTraverse(T,   PrintElement);
printf( "\n其中序序列为:\n ");
InOrderTraverse(T,   PrintElement);
printf( "\n其后序序列为:\n ");
PostOrderTraverse(T,   PrintElement);
printf( "\n ");

return   OK;
}
VC8中,输出结果出错,请高手帮我看下,谢谢

[解决办法]
int main()
{
BiTree T;
TElemType pre[LEN], ino[LEN];
int ps = 0, is = 0;

printf( "请输入先序序列:\n ");
scanf( "%s ",pre);
printf( "\n请输入中序序列:\n ");
scanf( "%s ",ino);

CrtBT(T, pre, ino, ps, is, LEN); //这个地方参数错了,看看你CrtBT()的定义,
//应该为CrtBT(&T, pre, ino, ps, is, LEN);

printf( "\n建完树后,其先序序列为:\n ");
PreOrderTraverse(T, PrintElement);
printf( "\n其中序序列为:\n ");
InOrderTraverse(T, PrintElement);
printf( "\n其后序序列为:\n ");
PostOrderTraverse(T, PrintElement);
printf( "\n ");

return OK;
}

热点排行