请设计一个算法，将给定的表达式树(二叉树)转换为等价的

第1题

请设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。例如，当下列两棵表达式树作为算法的输入时，输出的等价中缀表达式分别为(a+b) * (c * (-d)和(a * b)+(-(c-d))。

二叉树结点定义如下：

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

请回答下列问题。

（1）给出算法的基本设计思想。

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

答：

（1）算法的基本设计思想

表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。(3分)

表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层(对应根结点)及操作数(对应叶结点)不需要添加括号。

（2）算法实现(10分)

void BtreeToE(BTree *root) {
    BtreeToExp(root,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层括号
    }
}