41.（15分）请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时: 输出的等价中缀表达式分别为（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层括号 } }
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（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层括号 } }
正在整理中,欢迎在文下评论区提供答案解析,谢谢！