读书人

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

发布时间: 2012-03-15 11:50:38 作者: rapoo

先序中序建二叉树出现的奇怪问题
#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;
}

读书人网 >C语言

热点推荐