exp3_2.cpp

1） 以二叉链表或三叉链表作为二叉树的存储结构； 2） 以某一种遍历的次序录入二叉树的元素

#include<malloc.h>
#include<stdlib.h>
#include<stdio.h>
#define OK 1
#define ERROR 0
#define LENGTH 100  
typedef int status;
typedef struct BiTNode{
	 char data;
	 struct BiTNode	*lchild, *rchild;
}BiTNode, *BiTree;


status PreCreateExpressionBitree(BiTree &T,char a[],int &i)
 {
	char ch;
	 ch=a[i];
	 
	 if(ch==' ')T=NULL;
	 else
	 {
		 T=(BiTree)malloc(sizeof(BiTNode));
		 T->data=ch;
		 PreCreateExpressionBitree(T->lchild,a,++i);
    	 PreCreateExpressionBitree(T->rchild,a,++i);
	 }
	 return(OK);
 }

status PreOrderTraverse(BiTree T, status ( *Visit ) (char c) )
{
     if ( T != NULL )
	 {

         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 ) (char c) )
{
     if ( T != NULL )
	 {
        if ( InOrderTraverse( T->lchild, Visit ) )
           if ( Visit(T->data) )  
             if ( InOrderTraverse( T->rchild, Visit ) )
             return(OK);
             return(ERROR);
	 } 
     else return(OK);
}
status PostOrderTraverse1(BiTree &T, status ( *Visit ) (char c) )
{
     if ( T != NULL )
	 {
        if ( PostOrderTraverse1( T->lchild, Visit ) )
           if ( PostOrderTraverse1( T->rchild, Visit ) )
			  if ( Visit(T->data) )  
             
             return(OK);
             return(ERROR);
	 } 
     else return(OK);
}
status PostOrderTraverse2(BiTree &T, status ( *Visit ) (BiTree T) )
{
     if ( T != NULL )
	 {
        if ( PostOrderTraverse2( T->lchild, Visit ) )
           if ( PostOrderTraverse2( T->rchild, Visit ) )
			  if ( Visit(T) )  
             
             return(OK);
             return(ERROR);
	 } 
     else return(OK);
}
status Visit(char c)
{
	if(printf("%c",c))return(OK);
	else return(ERROR);
}
status operate(BiTree T){
	if(T->data=='-')
		T->data=T->lchild->data-T->rchild->data;
	if(T->data=='+')
		T->data=T->lchild->data+T->rchild->data;
	if(T->data=='*')
		T->data=T->lchild->data*T->rchild->data;
	if(T->data=='/')
		T->data=T->lchild->data/T->rchild->data;
	return (OK);
}

void main()
 {
	BiTree T;int i=0;char a[LENGTH],ch;
     printf("输入前缀表达式：\n");  
	 while((ch=getchar())!='\n')
		 if(ch>=65&&ch<=90||ch>=97&&ch<=122){
			 a[i++]=ch;
			 a[i++]=' ';
			 a[i++]=' ';
		 }
		 else if(ch=='+'||ch=='-'||ch=='/'||ch=='*')
			 a[i++]=ch;
		 else
		 {printf("input is wrong\n");
		 exit(0);
		 }
         i=0;    
	 PreCreateExpressionBitree(T,a,i);
     PreOrderTraverse(T,Visit);
	 printf("\n");
	 InOrderTraverse(T,Visit);
	 printf("\n");
	 PostOrderTraverse1(T,Visit);
	 printf("\n");
	 printf("输入带值前缀表达式：\n");
	 i=0;
	 while((ch=getchar())!='\n')
		 if(ch>=48&&ch<=57){
			 a[i++]=ch-48;
			 a[i++]=' ';
			 a[i++]=' ';
		 }
		 else if(ch=='+'||ch=='-'||ch=='/'||ch=='*')
			 a[i++]=ch;
		 else
		 {printf("input is wrong\n");
		 exit(0);
		 }
         i=0;    
	 PreCreateExpressionBitree(T,a,i);
	 PostOrderTraverse2(T,operate);
	 printf(" %d ",T->data);
	 


}