2022CSP-J组初赛真题解析6

大家好，欢迎来到IT知识分享网。

6. 对表达式a+(b-c)*d的前缀表达式为（ ），其中+、-、*是运算符。

A. *+a-bcd

B. +a*-bcd

C. abc-d*+

D. abc-+d

解析：

背景知识：

树的遍历

树的遍历是指访问树的每个结点，且每个结点仅被访问一次。二叉树的遍历可按二叉树的构成以及访问结点的顺序分为三种方式：先序遍历、中序遍历、后序遍历。

先序遍历

遍历过程为：

1. 访问根结点
2. 先序遍历其左子树
3. 先序遍历其右子树

先序遍历顺序=> A B D F E C G H I

中序遍历

遍历过程为：

1. 中序遍历其左子树
2. 访问根结点
3. 中序遍历其右子树

中序遍历顺序=> D B E F A G H C I

后序遍历

其遍历过程为：

1. 后序遍历其左子树
2. 后序遍历其右子树
3. 访问根结点

后序遍历顺序=> D E F B H G I C A

前缀表达式、中缀表达式、后缀表达式都是四则运算的表达方式，用以四则运算表达式求值。

中缀表达式

中缀表达式就是常见的运算表达式，如(1+2)×3-4

前缀表达式

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前，如× + 3 4 5

后缀表达式

后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后，如1 2 + 3 × 4 –

知识点分类：

数据结构-简单树

答案解析：

题干中表达式a+(b-c)*d是中缀表达式，转化成二叉树后，它是中序遍历的结果。前缀表达式，就是先序遍历该二叉树(如下图所示）

先序遍历顺序=> + a * – b c d

所以本题的正确答案应该选B。