数据结构
2017-41
请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时，输出的等价中缀表达式分别为 (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）算法实现：
通过递归中序遍历实现，传递当前节点深度。深度为1时对应根节点，不添加括号；深度大于1时为子表达式添加括号。核心代码如下：
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层括号
}
}
void BtreeToE(BTree *root) {
BtreeToExp(root, 1); // 根的深度为1
}入口调用：BtreeToE(root);
（3）关键结论：
算法正确将表达式树转换为带括号的中缀表达式。示例输入输出验证：
- 对于树1，输出
(a+b)*(c*(-d))； - 对于树2，输出
(a*b)+(-(c-d))。
括号嵌套准确，无冗余或缺失。