宁波优化网站哪家好_设计资源网_百度下载安装2021_深圳网站设计公司哪家好

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

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

二叉树结点的定义如下：

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

要求：

⑴ 给出算法的基本设计思想。

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

思想：利用中序遍历。除了根结点和叶节点以外，遍历到其他结点时，在遍历左子树之前加上左括号，遍历右子树之后加上右括号。 

代码：

void BtreeInExp(BTreen *T,int depth){//空树if(T==NULL){return ;} //左子树 if(depth>1&&(T->left!=NULL||T->right !=NULL)){printf("(");}if(T->left!=NULL){BtreeInExp(T->left,1+depth);}printf("%s",T->data);//右子树if(T->right!=NULL){BtreeInExp(T->right,1+depth);} if(depth>1&&(T->left!=NULL||T->right !=NULL)){printf(")");}
}
//程序入口 
void BtreeInExp(BTree *T){BtreeInExp(T,1);
}