题目描述:
设计一个算法,将给定的表达式(二叉树)转换为等价的中缀表达式(通过括号来反映计算的次序)并输出。
算法思想:
表达式树的中序序列(左根右)加上必要的括号就是等价的中缀表达式,该题可以基于二叉树的中序遍历来做。
表达式树中的分支结点所对应的子表达式的计算次序,由分支结点所处的位置来决定。为得到正确的中缀表达式,需要在生成遍历序列的同时,在适当的位置上加上必要的括号。显然,表达式的最外层(对应根结点)和操作数(对应叶结点)不需要添加括号。
除根结点和叶结点外,遍历到其他结点时在遍历其左子树之前加上左括号,遍历右子树之后加上右括号。
代码如下:
void BtreeTo(BTree *root){
BtreeTo(root,1); //根的高度为1
}
void BtreeTo1(BTree *root,int deep){
if(root==NULL) return 0; //空结点返回
if(root->left==NULL && root->right==NULL) //若为叶结点
printf("%s",root->data); //输出操作数,不加括号
else{
if(deep>1) printf("("); //若有子表达式,加一层括号
BtreeTo1(root->left,deep+1);
printf("%s",root->data);
BtreeTo1(root->right,deep+1);
if(deep>1) printf(")");
}
}