homework5.cpp

刚才弄错了

#include <stdio.h>

#include <string.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE 1
typedef int BOOL;
typedef struct __tp
{
struct __tp *left;
char ch;
struct __tp *right;
}TreeElem;
char szFOrder[100],szMOrder[100];
TreeElem *root;
BOOL CreateTree(TreeElem**,char*,char*,int);
void FrontVisit(TreeElem *root);
void MiddleVisit(TreeElem *root);
void BackVisit(TreeElem *root);
BOOL checkout(char*,char*,int);
void main()
{
printf("input front-order's string:");
scanf("%s",szFOrder);
printf("input middle-order's string:");
scanf("%s",szMOrder);
int len=strlen(szFOrder);
if(len!=strlen(szMOrder))return;
if(CreateTree(&root,szFOrder,szMOrder,len))
{
FrontVisit(root);
printf("");
MiddleVisit(root);
printf("");
BackVisit(root);
}
}
BOOL CreateTree(TreeElem ** r,char* f,char* m,int len)
{
int pos;
TreeElem *root;
if((root=(TreeElem *)malloc(sizeof(TreeElem)))==NULL)
{
printf("Not Enough Memory!");
exit(0);
}
*r=root;
root->left=NULL;
root->right=NULL;
root->ch=f[0];
if(len==1)return TRUE;
for(pos=0;pos<len;pos++)
{
if((m[pos]==f[0])&&checkout(f+1,m,pos))
{
if(pos)
{
if(!CreateTree(&(root->left),f+1,m,pos))return FALSE;
}
if(len-pos-1)
{
if(!CreateTree(&(root->right),f+pos+1,m+pos+1,len-pos-1))return FALSE;
}
return TRUE;
}
}
return FALSE;
}
BOOL checkout(char *f,char *m,int len)
{
int i,j;
for(i=0;i<len;i++)
{
for(j=0;j<len;j++)
{
if(f[i]==m[j])break;
}
if(j>=len)return FALSE;
}
for(i=0;i<len;i++)
{
for(j=0;j<len;j++)
{
if(m[i]==f[j])break;
}
if(j>=len)return FALSE;
}
return TRUE;
}
void FrontVisit(TreeElem *root)
{
if(root==NULL)return;
printf("%c",root->ch);
FrontVisit(root->left);
FrontVisit(root->right);
}
void MiddleVisit(TreeElem *root)
{
if(root==NULL)return;
MiddleVisit(root->left);
printf("%c",root->ch);
MiddleVisit(root->right);
}
void BackVisit(TreeElem *root)
{
if(root==NULL)return;
BackVisit(root->left);
BackVisit(root->right);
printf("%c",root->ch);
}