题目

表达式(a-(b+c))*(d/e)存储在如下图所示的一棵以二叉链表为存储结构的二叉树中（二叉树结点的data域为字符型），编写程序求出该表达式的值（表达式中的操作数都是一位的整数）。

分析

左子树为表达式A，右子树为表达式B，经过分析可以得：先求左子树所表示的表达式的值，然后求右子树所表示的表达式的值，最后将两个结果相乘就是整个表达式的数值。即先遍历左子树（得左子树的值），再遍历右子树（得右子树的值），最后访问根（得运算符）的二叉树的后序遍历方式。

代码

核心代码：

/*  求表达式的值 */
/* 例：*-9##+3##2##/4##2##  */
int comp(BTNode *p) {
	int A,B;
	if(p!=NULL) {
		if(p->lchild!=NULL&&p->rchild!=NULL) { // 如果当前结点的左子树和右子树非空，则为表达式，再用后序遍历求值 */
			A=comp(p->lchild);// 后序遍历求出左子树的值，赋值给A
			B=comp(p->rchild);// 后序遍历求出右子树的值，赋值给B
			return op(A,B,p->data);// 根据已求得的A与B和当前结点的运算符求出整个表达式的值
		} else { // 如果当前结点的左右子树都为空，则为数值，直接返回，p->data-'0'是将字符型数字转化为整型数字
			return p->data-'0';
		}
	} else { // 如果是空树，则表达式的值为0
		return 0;
	}
}

完整代码：

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

/* 数结构体类型定义*/
typedef struct BTNode {
	char data;// 这里默认结点data域为char类型
	struct BTNode *lchild;// 左孩子指针域
	struct BTNode *rchild;// 右孩子指针域
} BTNode,*BiTree;

/* 根据输入创建二叉树 */
/* 例：ABC##DE##F##GH### */
void CreatBiNode(BTNode **Node) { //此处应注意传递的参数（二重指针）
	char data;
	scanf("%c", &data);

	*Node = (BiTree)malloc(sizeof(BTNode));
	if (data == '#') {
		*Node = NULL;
	} else if ((data != '#') && (*Node)) {
		(*Node)->data = data;
		(*Node)->lchild = NULL;
		(*Node)->rchild = NULL;
		CreatBiNode(&(*Node)->lchild);
		CreatBiNode(&(*Node)->rchild);
	}
}

int op(int A,int B,char p) {
	if(p=='+') {
		return A+B;
	} else if(p=='-') {
		return A-B;
	} else if(p=='*') {
		return A*B;
	} else if(p=='/') {
		return A/B;
	}
}

/*  求表达式的值 */
/* 例：*-9##+3##2##/4##2##  */
int comp(BTNode *p) {
	int A,B;
	if(p!=NULL) {
		if(p->lchild!=NULL&&p->rchild!=NULL) { // 如果当前结点的左子树和右子树非空，则为表达式，再用后序遍历求值 */
			A=comp(p->lchild);// 后序遍历求出左子树的值，赋值给A
			B=comp(p->rchild);// 后序遍历求出右子树的值，赋值给B
			return op(A,B,p->data);// 根据已求得的A与B和当前结点的运算符求出整个表达式的值
		} else { // 如果当前结点的左右子树都为空，则为数值，直接返回，p->data-'0'是将字符型数字转化为整型数字
			return p->data-'0';
		}
	} else { // 如果是空树，则表达式的值为0
		return 0;
	}
}

int main() {
	printf("先序输入二叉树(空结点用'#'表示):");
	BiTree T=NULL;
	CreatBiNode(&T);// 创建二叉树

	/* 求表达式的值 */
	int r=comp(T);
	printf("%d",r);

	return 0;
}

以下面题为测试例：