Question

已知一算术表达式的中缀形式为A+B*C-D E，后缀形式为ABC*+DE -，其前缀形式为()。

A.-A+B*C/DE
B.-A+B*CD/E
C.-+*ABC/DE
D.-+A*BC/DE

Answer 1

【答案】：D
将算术表达式的前缀形式、中缀形式和后缀形式分别看成二叉树的前序遍历、中序遍历和后序遍历，本题可转化成已知二叉树的中序遍历和后序遍历序列，如何求出其前序遍历序列。前序遍历的顺序是根结点，左子树，右子树；中序遍历的顺序是左子树，根结点，右子树；后序遍历的顺序是左子树，右子树，根结点；因此后序遍历中最后访问的结点是根结点，该结点将中序遍历分成两个子序列，分别为其左右子树的中序序列，之后递归应用这个过程，构造出一个二叉树，前序遍历该序列，即可得到表达式的前缀形式。