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

输出的中缀表达式分别为 (a+b)*(c*(−d)) 和 (a*b)+(−(c−d)) 。

二叉树结点的定义如下：

typedef struct node{
    char data[10];   // 存储操作数或操作符
    struct node *left, *right;
} BTree;

要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

二叉树遍历

[tag_link]

1）算法的基本设计思想表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。（3 分）表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层（对应根结点）及操作数（对应叶结点）不需要添加括号。（2 分）

2）算法实现（10 分）

void preorder(node *root, int depth) {
  if (!root) {
    return;
  }
  bool isRoot = (depth == 1);
  bool isLeaf = (!root->left && !root->right);
  if (!isRoot && !isLeaf) {
    printf("(");
  }
  preorder(root->left, depth+1);
  printf("%s", root->data);
  preorder(root->right, depth+1);
  if (!isRoot && !isLeaf) {
    printf(")");
  }
}

void solve(node *root) {
  preorder(root, 1);
}

将二叉树的中序遍历递归算法稍加改造即可得本题答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子树之前加上左括号，在遍历完右子树后加上右括号。【评分说明】①若考生设计的算法满足题目的功能要求，则（1)、(2) 根据所实现算法的策略及输出结果给分，评分标准见下表。

②若考生采用其他方法得到正确结果，可参照①的评分标准给分。③如果程序中使用了求结点深度等辅助函数，但没有给出相应的实现过程，只要考生进行了必要的说明，可不扣分。④若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，则可参照①的标准给分。⑤若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。