标识符树的后序计算表达式的值（运算只涉及+、-、*、/）

1. 定义二叉树的结构如下：

struct tree            //定义结构体
{int data;             //定义一个整型数据域
struct tree *left;    //定义左子树指针
struct tree *right;   //定义右子树指针
}；
typedefstruct tree btnode;  //树的结构类型
typedefstruct *bt;          //定义树结点的指针类型

2. 把算术表达式2*3+6/3的标识符树存入一维数组
3. 求标识符的前序遍历、中序遍历和后序遍历的序列
4. 以后序计算标识符树的值

代码展示

#include
#include
#include
typedef struct CBTree {
	char  data;
	struct CBTree* left;
	struct CBTree* right;
}CBTree;

int n;//字符串长度
CBTree* CreateCBTree(int* data, int pos)
{
	CBTree* newnode;
	if (data[pos] == 0 || pos > n)
		return NULL;
	else 
	{
		newnode = (CBTree*)malloc(sizeof(CBTree));
		newnode->data = data[pos];
		newnode->left = CreateCBTree(data, 2 * pos);
		newnode->right = CreateCBTree(data, 2 * pos + 1);
		return newnode;
	}
}
void DLRPrint(CBTree* pnode)//前序输出结点
{
	if (pnode != NULL)
	{
		printf("%c", pnode->data);
		DLRPrint(pnode->left);
		DLRPrint(pnode->right);
	}
}
void LDRPrint(CBTree* pnode)//中序输出结点
{
	if (pnode != NULL)
	{
		LDRPrint(pnode->left);
		printf("%c", pnode->data);
		LDRPrint(pnode->right);
	}
}

void RDLPrint(CBTree* pnode)//后序输出结点
{
	if (pnode != NULL)
	{
		RDLPrint(pnode->left);
		RDLPrint(pnode->right);
		printf("%c", pnode->data);
	}
}

int count(CBTree* pnode)
{
	int operand1 = 0;
	int operand2 = 0;
	int num = 0;
	int getvalue(int op, int operand1, int operand2);
	if (pnode->left == NULL && pnode->right == NULL)
	{
		num = int(((pnode->data) - '0'));
		return num;
	}
	{
		operand1 = count(pnode->left);
		operand2 = count(pnode->right);
		return getvalue(pnode->data, operand1, operand2);
	}
}

int getvalue(int op, int operand1, int operand2)
{
	switch ((char)op)
	{
	case'*':return(operand1 * operand2);
	case'/':
		if (operand2 != 0)
			return (operand1 / operand2);
		else printf("除数不能为0，数学错误");
		return 0;
	case'+':return(operand1 + operand2);
	case'-':return(operand1 - operand2);
	}
}

void main()
{
	CBTree* root = NULL;
	int result;
	int k = 1;
	int data[100] = { ' ' };
	char ch;
	printf("按层次输入结点数据，以回车键表示结束n");
	while ((ch = getchar()) != 'n')
		data[k++] = ch;
		data[k] = '';
		n = k - 1;
	root = CreateCBTree(data, 1);
	printf("tn前序表达式：");
	DLRPrint(root);
	printf("tn中序表达式：");
	LDRPrint(root);
	printf("tn后序表达式：");
	RDLPrint(root);
	result = count(root);
	printf("tn表达式结果为：%dn", result);
}

代码效果呈现：