美国公立小学排名:表达式的二叉树
例如:1+2*(8+9),注意是任意表达式,怎么弄清运算符的优先级,怎么处理括号问题。谢谢
这个是转换逆波兰表达式的最好办法~XD难道是考研的?给你一个实现参考:
#define SIZE 21
typedef struct tagitem item;
typedefitem *itemptr;
typedefitemptr *itemref;
typedef struct tagitem
{
char *data;
itemptr left;
itemptr right;
};
void getstring(char *s,int size)
{
int i=0;
char c;
while(--size>0)
{
getchar();
c=getchar();
if(c==EOF||c=='\n')
size=0;
else
s[i++]=c;
}
s[i]='\0';
fflush(stdin);
}
itemptr newitem()
{
itemptr p=(itemptr)malloc(sizeof(item));
if(!p){
fprintf(stderr,"\nerror:out of memory\n");
exit(1);
}
p->data=NULL;
p->left=NULL;
p->right=NULL;
return p;
}
void process(itemptr node)
{
printf("%s",node->data);
}
void search(itemref tree,const char *s)
{
itemptr p;
int cmpresult;
if(*tree==NULL){
p=newitem();
p->data=strdup(s);
p->left=NULL;
p->right=NULL;
*tree=p;
}
else
{
p=*tree;
cmpresult=strcmp(s,p->data);
if(cmpresult<0)
search(&p->left,s);
else if(cmpresult>0)
search(&p->right,s);
else
{
puts("duplicate data!");
process(p);
puts("");
}
}
}
void preorder(itemptr node)
{
if(node!=NULL){
process(node);
preorder(node->left);
preorder(node->right);
}
}
void inorder(itemptr node)
{
if(node!=NULL){
inorder(node->left);
process(node);
inorder(node->right);
}
}
void postorder(itemptr node)
{
if(node!=NULL){
postorder(node->left);
postorder(node->right);
process(node);
}
}
void freetree(itemptr root)
{
if(root!=NULL){
freetree(root->left);
freetree(root->right);
free(root);
}
}
int main()
{
itemptr root=NULL;
char s[SIZE];
int done=0;
puts("tree demonstration");
while(!done){
printf("data (enter to quit):");
getstring(s,SIZE);
done=(strlen(s)==0);
if(!done)
search(&root,s);
}
puts("\nerror:\n");
preorder(root);
puts("\ninorder:\n");
inorder(root);
puts("\npostorder:\n");
puts("");
freetree(root);
return 0;
}