数据结构考研分类复习真题 第六章 答案 (五)[2]

[题目分析] 本题是将符号算术表达式用二叉树表示的逆问题即将二叉树表示的表达式还原成原表达式二叉树的中序遍历序列与原算术表达式基本相同差别仅在于二叉树表示中消除了括号将中序序列加上括号就恢复原貌当根结点运算符优先级高于左子树（或右子树）根结点运算符时就需要加括号

int Precede(char optroptr)

// 比较运算符级别高低optr级别高于optr时返回相等时返回低于时返回

{switch(optr)

{case+:case:if(optr==+||optr==)return();else return();

case*:case/:if(optr==*||optr==/)return();else return();

} }

void InorderExp (BiTree bt)

//输出二叉树表示的算术表达式设二叉树的数据域是运算符或变量名

{int bracket;

if(bt)

{if(bt>lchild!=null)

{bracket=Precede(bt>databt>lchild>data)//比较双亲与左子女运算符优先级

if(bracket==) printf(()

InorderExp(bt>lchild); //输出左子女表示的算术表达式

if(bracket==)printf()) //加上右括号

}

printf(bt>data); //输出根结点

if(bt>rchild!=null) //输出右子树表示的算术表达式

{bracket=Precede(bt>databt>rchild>data)

if (bracket==)printf(() //右子女级别低加括号

InorderExp (bt>rchild);

if(bracket==)printf())

} }

}//结束Inorder Exp

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []