数据结构实验5：基于二叉树的表达式求值（c语言）

1.第一个节点先成为表示树的根

2.第二个结点插入时变为根，原根结点变为新结点的左孩子。

3.插入节点为数字时，沿根结点右链插入到最右端。

4.插入节点为操作符时，先与根结点操作符优先级对比。

a.优先级不高时，新结点成为根结点，原表达式成为新结点的左子树。

b.优先级高时，新结点成为根结点的右孩子，原根结点的右孩子成为新结点的左子树。

#include#include#include#define MS 20typedef struct node{char op;int data;struct node* left;struct node* right;}Node;typedef struct root{Node* root;}BT;void Read(char s[]){for(int i=0;idata = q;n->op = p;n->left = NULL;n->right = NULL;return n;}void InitBT(BT* a,char s[]){a->root = CN(-1,s[1]);a->root->left = CN(s[0]-'0','#');}void go(Node *p,Node *a){if(p->right!=NULL) go(p->right,a);else p->right = a;}float CAL(Node* p)                                            //计算二叉树 {if(p->data!=-1) return p->data;else{float lvalue = CAL(p->left);float rvalue = CAL(p->right);switch(p->op){case '+':{printf("%.2f+%.2f=%.2f\n",lvalue,rvalue,lvalue+rvalue);return lvalue+rvalue;break;}case '-':{printf("%.2f-%.2f=%.2f\n",lvalue,rvalue,lvalue-rvalue);return lvalue-rvalue;break;}case '*':{printf("%.2f*%.2f=%.2f\n",lvalue,rvalue,lvalue*rvalue);return lvalue*rvalue;break;}case '/':{printf("%.2f/%.2f=%.2f",lvalue,rvalue,lvalue/rvalue);return lvalue/rvalue;break;}}}}void BuildBT(BT* a,char s[])                             //构建二叉树 {InitBT(a,s);printf("\n");char temp[MS];BT* b = (BT*)malloc(sizeof(BT));                     //构造临时树存括号内的东西 for(int i=2;i'0'&&s[i]root,CN(s[i]-'0','#'));}else{if(GetPriority(a->root->op,s[i])=='>'){Node* n = CN(-1,s[i]);Node *p = a->root;n->left = p;a->root = n;//printf("root=%c\n",a->root->op);}else{Node* n = CN(-1,s[i]);Node *p = a->root->right;a->root->right = n;n->left = p; }}}}int main(){char s[MS]={0};BT* a = (BT*)malloc(sizeof(BT));printf("------------------------------------------chen le------------------------------------------\n");printf("-------------------------------------------cqupt-------------------------------------------\n");printf("请输入表达式：（eg：1+2=）\n");Read(s);BuildBT(a,s);float rs = CAL(a->root);printf("\n");printf("rs=%.2f\n",rs);return 0;}