问答题
试分别画出表示下列两个表达式的二叉树。【华中科技大学2006三、1(6分)】(1)a一b+c (2)a+(b一c)/d—e*f
【正确答案】正确答案:人们日常使用的表达式是中缀表达式,由于存在括号和运算符的优先级,直接转换成表达式二叉树比较困难。最好的办法是先将中缀表达式转换成后缀表达式,转换规则已在第3章的应用题部分的第21题做了介绍,读者可参照。由后缀表达式转换成表达式二叉树的规则如下。从左到右读入后缀表达式,遇操作数就入栈,遇操作符就将该操作符做当前的根结点,并从栈内弹出两个操作数,后弹出的是第一操作数(被乘/除/加/减数)做左子树,先弹出的做右子树,之后将该根结点入栈。继续读后缀表达式,如上处理,直至表达式结束。限于篇幅,表达式的二又树不再画出。
【答案解析】