|
中缀表达式是最符合我们人类阅读的一种方式，因为它和我们日常的数学表达式很接近
算法思想：基于二叉树的中序遍历，但是我们要给关键位置加上左括号和右括号。除了根结点和叶子结点，遍历到其他结点的时候，在遍历左子树之前加左括号，遍历完右子树后加上右括号。
void Ready2Btree2Exp(BTree *root)
{
Btree2Expression(root, 1); //根结点的高度为1
}
void Btree2Expression(BTree *root, int deep)
{
if(root == NULL)
{
return; //根结点为空，说明是个空树
}
else if(root->lchild==NULL && root->rchild==NULL)
{
//为叶子结点
printf("%s", root->data); //输出操作数，但是不用加括号
}
else
{
if(deep > 1)
{
printf("("); //还有子表达式，要加括号
}
Btree2Expression(root->lchild, deep+1);//递归调用遍历左边
printf("%s", root->data);
Btree2Expression(root->rchild, deep+1);
if(deep > 1)
{
printf(")");
}
}
}
|