2017 年数据结构统考真题

题目

设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列的两棵表达式树作为算法的输入时：

输出等价的中缀表达式分别为（a+b）（c（-d））和（a*b）+（-（c-d））。
二叉树的结点定义如下：

typedef struct node
{
	char data[10];
	struct node *left, *right;
}BTree;

要求：
（1）给出算法的基本设计思想
（2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释

解答

（1）基于二叉树的中序遍历方式即可得到该表达式
（2）算法实现：将二叉树的中序遍历递归算法稍加变形即可得到。除根结点而
哼叶子结点外，遍历到其他结点是在遍历其左子树之前加上左括号，遍历完右子
树后加上右括号：

void BtreeToExp(BTree *root, int deep)
{
	if(root == NULL)
		return ;
	else if(root->left == NULL && root->right == NULL) //若为叶子结点
	printf("%s", root->data);
	else
	{
		if(deep > 1)
			printf("("); //若有子表达式则加 1 层括号
		BtreeToExp(root->left, deep+1);
		printf("%s", root->data);
		BtreeToExp(root->right, deep+1);
		if(deep > 1)
			printf("）"); 若有子表达式则加 1 层括号
	}
}