实验：编写一个二叉树来表示一个简单算术表达式，树的每一个结点包括一个运算符或运算数。在简单算术表达式中只包含 + - * / 和 一位正整数。并且按要求先乘除后加减的原则构造二叉树。

所示为1+2*3-4/5 代数表达式对应的二叉树，然后由对应二叉树计算该表达式的值

解题思路：

1.给出一个简单算术表达式，形如：1+2*3-4/5，这个表达式其实就是中缀表达式（栈的那一章），也是这颗二叉树的中序遍历;

2.且 二叉树可以由 中序遍历 和 先序 或 后序遍历 求出一颗唯一二叉树，中序表达式已经有了，现在只需要利用栈的特性，就可以得出后序遍历;

3.接着由两个遍历的排序可以推演（构建）出一颗唯一二叉树;

4.最后再用 深度优先的算法思想 给这颗构建好的二叉树求值;

以下是 由 中序遍历 转 后序遍历 的详细代码： 

char* Sort_Change(Satack &S, char *formula) {  //转后缀表达式
	int i = 0, k = 0, count = 0;
	char *str = (char*)calloc(sizeof(char), 10);

	while (formula[i] != '\0') {

		if (formula[i] > 47 && formula[i] < 58) { //如果是数字，直接排列进数组
			str[k++] = formula[i];
			count++;
		}

		if (formula[i] == '+' || formula[i] == '-') { //@ 如果是+ 、 - 号 ，考虑栈优先级

			if (S.c[S.top - 1] == '*' || S.c[S.top - 1] == '/') {
				while (S.top != 0) {
					str[k++] =  Pop(S);
				}
				Push(S, formula[i]);
			} else {
				Push(S, formula[i]);
			}
		}

		if (formula[i] == '*' || formula[i] == '/') {  //如果是* / 直接进栈 
			Push(S, formula[i]);
		}

		i++;
	}

假设输入的式子为：1+2*3-4/5   ，经过这段代码将会生成一个 后缀模式：123*+45/-;

接下来就可以又两个表达书确定一颗唯一的二叉树 ;    //（怎么推演的，这里不做解释）

以下是由中序 、 后序遍历 构造一颗二叉树的代码：

Bnode* Insert_Tree(char str[], char laststr[], int n) { //参数说明str 是后续遍历 laststr 是中序遍历 n为算式长度
	Bnode *b;
	char r, *p;
	int k;
	if (n <= 0)return NULL;
	r = *(str + n - 1);
	b = (Bnode*)malloc(sizeof(Bnode));
	b->data = r;
	for (p = laststr; p <= laststr + n; p++) {
		if (*p == r)break;
	}

	k = p - laststr;
	b->lchild = Insert_Tree(str, laststr, k);
	b->rchild = Insert_Tree(str + k, p + 1, n - k - 1);

	return b;
}

这样就构造好一颗 由 1+2*3-4/5  和 123*+45/-  推演出来的二叉树；

最后，再用 深度优先算法 计算这颗二叉树即可，详情看代码； 

int evaluation(Bnode *B) {

	if (B) {


		if (B->data > 47 && B->data < 58) {   //数字直接返回 
			return B->data - '0';
		}
		//**运算符 则跟返回的数字进行相应运算      此处采用深度优先算法（DF）的思想 
		switch (B->data) {
			case 43://	 + 
				return 	evaluation(B->lchild) + 	evaluation(B->rchild);
				break;
			case 45://	 - 
				return 	evaluation(B->lchild) - 	evaluation(B->rchild);
				break;
			case 42://   * 
				return 	evaluation(B->lchild) * 	evaluation(B->rchild);
				break;
			case 47://   / 
				return 	evaluation(B->lchild) / 	evaluation(B->rchild);
				break;

		}

	}
	return 0;
}

 以上为此实验主要思路，下面贴出完整代码：

（WIN10 64平台，编译器：小熊猫Dev C++  :  MinGW GCC10.2.0）

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>

using namespace std;

typedef struct node {
	char data;
	struct node *lchild, *rchild;
} Bnode;

typedef struct tack {
	char c[10];
	int top ;
} Satack;

//栈的操作		栈的操作		栈的操作		栈的操作		栈的操作		栈的操作

void Creat_Satack(Satack &S) {  //初始化栈 
	S.top = 0;
}

bool Is_Empty(Satack &S) {   //栈判空 
	return  S.top == 0 ? true : false;
}

bool Is_Full(Satack &S) {   //栈判满 
	return S.top == 11 ? true : false;
}

bool Push(Satack &S, char str) {  //进栈 
	if (Is_Full(S))return false;
	S.c[S.top++] = str;
	return true;
}

char Pop(Satack &S) {  //出栈 
	if (Is_Empty(S))return 0;
	return S.c[--S.top];
}

//@ 将原中缀表达式，转换成后缀表达式 
//**             
//利用栈的特性
 
char* Sort_Change(Satack &S, char *formula) {  //转后缀表达式
	int i = 0, k = 0, count = 0;
	char *str = (char*)calloc(sizeof(char), 10);

	while (formula[i] != '\0') {

		if (formula[i] > 47 && formula[i] < 58) { //如果是数字，直接排列进数组
			str[k++] = formula[i];
			count++;
		}

		if (formula[i] == '+' || formula[i] == '-') { //@ 如果是+ 、 - 号 ，考虑栈优先级

			if (S.c[S.top - 1] == '*' || S.c[S.top - 1] == '/') {
				while (S.top != 0) {
					str[k++] =  Pop(S);
				}
				Push(S, formula[i]);
			} else {
				Push(S, formula[i]);
			}
		}

		if (formula[i] == '*' || formula[i] == '/') {  //如果是* / 直接进栈 
			Push(S, formula[i]);
		}

		i++;
	}
	
	//** 
	//遍历完了以后，判断栈里还有没有运算符 ，如有，全部输出 
	//**
	 
	while (S.top != 0) {  
		str[k++] = Pop(S);
	}


	return str;
}


//树的操作		树的操作		树的操作 		树的操作 		树的操作 		树的操作




// @可以根据 原式（中缀表达）和 转换后的后缀表达式 构造树
// 例
//  中缀：1+2*3-4/5
//  后缀：123*+45/-
//
//@由中缀表达式和后缀表达式（或前缀表达式） 即可推出构造树！
//**
//@ 此函数，思路是我的，代码是课本的 

Bnode* Insert_Tree(char str[], char laststr[], int n) {  //构造二叉树  ，此处参照课本  ，详情看课本 P.231 
	Bnode *b;
	char r, *p;
	int k;
	if (n <= 0)return NULL;
	r = *(str + n - 1);
	b = (Bnode*)malloc(sizeof(Bnode));
	b->data = r;
	for (p = laststr; p <= laststr + n; p++) {
		if (*p == r)break;
	}

	k = p - laststr;
	b->lchild = Insert_Tree(str, laststr, k);
	b->rchild = Insert_Tree(str + k, p + 1, n - k - 1);

	return b;
}


void firstroutine(Bnode *B) { //先序 遍历
	if (B) {
		printf(" %c ", B->data); //先访问根节点
		firstroutine(B->lchild); //再访问左数
		firstroutine(B->rchild); //最后再右树
	}
	return;
}


//**    二叉树求值  深度优先搜索  DF
 
int evaluation(Bnode *B) {

	if (B) {


		if (B->data > 47 && B->data < 58) {   //数字直接返回 
			return B->data - '0';
		}
		//**运算符 则跟返回的数字进行相应运算      此处采用深度优先算法（DF）的思想 
		switch (B->data) {
			case 43://	 + 
				return 	evaluation(B->lchild) + 	evaluation(B->rchild);
				break;
			case 45://	 - 
				return 	evaluation(B->lchild) - 	evaluation(B->rchild);
				break;
			case 42://   * 
				return 	evaluation(B->lchild) * 	evaluation(B->rchild);
				break;
			case 47://   / 
				return 	evaluation(B->lchild) / 	evaluation(B->rchild);
				break;

		}

	}
	return 0;
}

int main() {
	Satack S;
	Creat_Satack(S);
	Bnode *T;


	char formula[10];
	char *formula1;
	
	cout << "输入简单算术表达式：" << endl;
	
	gets(formula);//输入中缀表达式 

	formula1 = Sort_Change(S, formula);//转换成后缀表达式，由formula1进行地址接收 




	T = Insert_Tree(formula1, formula, strlen(formula));  //又中缀、后缀表达式 构造二叉树T 

	cout << "数得构造 ： 先序遍历：" << endl;
	firstroutine(T);            //输出 二叉树 T 的先序遍历 

	printf("/n %d", evaluation(T));//深度优先算法 进行二叉树求值 
}

运行结果：

感谢阅读