#include "stdio.h"
#include "stdlib.h" #define OVERFLOW -1
#define ERROR -1
#define OK 1 typedef char Elemtype;
typedef int Status;
typedef struct BitNode
{
Elemtype data;
struct BitNode *lchild,*rchild;
}bitnode ,*Bitree; int postion(Elemtype ch,Elemtype a[],int start,int end)
{
int i;
for(i=start;i<=end;i++)
if (a[i]==ch)
return i;
} Status creatbitree_TWOorder(Bitree &t,Elemtype preorder[],int startpre,int endpre, Elemtype inorder[],int startin ,int endin)
{
int pos,left,right;
if (endpre-startpre!=endin-startin)
return ERROR;
if(endpre-startpre<0)
t=NULL;
else
{
pos=postion(preorder[startpre],inorder,startin,endin);
left=pos-startin;
right=endin-pos;
printf("char=%c,pos=%d,left=%d,right=%d,--pre --- %d, %d --- in--- %d ,%d\n",preorder[startpre],pos,left,right,startpre,endpre,startin,endin);
//getchar(); if(!(t=(bitnode *)malloc(sizeof(Bitree)))) exit(OVERFLOW);
t->data=preorder[startpre];
creatbitree_TWOorder(t->lchild,preorder,startpre+1,left+startpre,inorder,startin,left+startin-1);
printf("====");
creatbitree_TWOorder(t->rchild,preorder,endpre-right+1,endpre,inorder,pos+1,endin); }
} Status creatbitree(Bitree &t)
{
char ch;
scanf("%c",&ch);
if(ch==' ') t=NULL;
else
{
if(!(t=(bitnode *)malloc(sizeof(Bitree)))) exit(OVERFLOW);
t->data=ch;
creatbitree(t->lchild);
creatbitree(t->rchild);
}
return OK;
} Status printelemt(Elemtype e)
{
printf("%c",e);
return OK;
} Status preordertraverse(Bitree t,Status (*visit)(Elemtype 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)(Elemtype 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)(Elemtype e))
{
if(t)
{
if(postordertraverse(t->lchild,visit))
if(postordertraverse(t->rchild,visit))
if(visit(t->data)) return OK;
return ERROR;
}
else
return OK;
} main()
{
Bitree t;
char a[]="1245673";
char b[]="4265713"; creatbitree_TWOorder(t,a,0,6,b,0,6); preordertraverse(t,printelemt);
printf("\n"); inordertraverse(t,printelemt);
printf("\n"); postordertraverse(t,printelemt);
printf("\n"); }