二叉树应用(表达式处理).cpp

利用C语言写的二叉树应用关于表达式处理源代码

#include "stdlib.h"
#include "stdio.h"

struct tree   
{struct tree *left;
char data;   
struct tree *right;  
};
typedef struct tree treenode;  
typedef treenode *b_tree;     //声明部分 

//创建二叉树
b_tree create_btree(int *nodelist,int position)
{
    b_tree newnode;  
if(nodelist[position]==0||position>7)   //递归的终止条件
return NULL;
else
{
	newnode=(b_tree) malloc (sizeof(treenode));//动态分配地址
    newnode->data=nodelist[position];//节点
    newnode->left=create_btree(nodelist,2*position);//左子树
    newnode->right=create_btree(nodelist,2*position+1);//右子树

return newnode;
}
}

//先根遍历
void preorder(b_tree point)
 {
   if (point!=NULL)                     
     {  
    printf("%c",point->data);          
    preorder(point->left);              
    preorder(point->right);            
     }
 }
//中根遍历
void inorder(b_tree point)
 {
   if (point!=NULL)                     
     {  
    inorder(point->left);              
    printf("%c",point->data);           
    inorder(point->right);            
     }
 }
//后根遍历
void postorder(b_tree point)
 {
   if (point!=NULL)                    
     {  
    postorder(point->left);              
    postorder(point->right);           
    printf("%c",point->data);           
     }
 }

//抽取运算值并计算
int get_value(int oper,int oper1,int oper2)
 {
     switch((char)oper)
      {
        case'*':return (oper1*oper2);
        case'/':return (oper1/oper2);
        case'+':return (oper1+oper2);
        case'-':return (oper1-oper2);
      }
 } 
//表达式计算
int calculate(b_tree point)
 {
   int oper1=0;                 
   int oper2=0;                 
   
     if (point->left==NULL && point->right==NULL)
        return point->data-48;
   else
    {
      oper1=calculate(point->left);      
      oper2=calculate(point->right);
      return get_value(point->data,oper1,oper2);
    }
 }


//主函数
void main()
 {
   b_tree root=NULL;                    
   int cal_result;                     
   int nodelist[20]={' ','+','*','/','4','8','6','2'};
   root=create_btree(nodelist,1); 
   
   printf("\nPreorder expression: [ ");
   preorder(root);
   printf("]\n");
  
   printf("Inorder expression: [ ");
   inorder(root);
   printf("]\n");
  
   printf("Postorder expression: [ ");
   inorder(root);
   printf("]\n");
  
   cal_result=calculate(root);
   printf("\nCalulate result is [%2d]\n",cal_result);
 }