中缀表达式(21.6.17)

题目描述:

设计一个算法,将给定的表达式(二叉树)转换为等价的中缀表达式(通过括号来反映计算的次序)并输出。

算法思想:

表达式树的中序序列(左根右)加上必要的括号就是等价的中缀表达式,该题可以基于二叉树的中序遍历来做。
表达式树中的分支结点所对应的子表达式的计算次序,由分支结点所处的位置来决定。为得到正确的中缀表达式,需要在生成遍历序列的同时,在适当的位置上加上必要的括号。显然,表达式的最外层(对应根结点)和操作数(对应叶结点)不需要添加括号。
除根结点和叶结点外,遍历到其他结点时在遍历其左子树之前加上左括号,遍历右子树之后加上右括号。

代码如下:

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(")");	
	}
}
上一篇:element ui plus自定义样式


下一篇:BlueCMS审计