表达式（波兰式：前缀表达式 逆波兰式：后缀表达式）

中序求后缀（后缀和后序差不多）

注意：比赛中表达式求后缀中的表达式一般是中序
答案可能有多个

我们拿一个式子讲：a*(b+c)-d
我们先找到最后才运算的符号 -
将 - 号放在根部

-

然后它的左边为左子树，右边为右子树
因为右边只有一个d
所以d就可以直接进树

 -
  \
   d

接着，我们看它的左子树 a*(b+c)
重复第一步，找到最后才运算的符号 *
将 * 号放在左子树的根节点

  -
 / \
*   d

然后同理，它的左边为左子树，右边为右子树
因为左边只有一个a
所以a就可以直接进树

    -
   / \
  *   d
 /
a

右边还有（b+c）
重复第一步和第二步，得出

    -
   / \
  *   d
 / \
a   +
   / \
  b   c

最后根据树的后序求出答案 （左右根）
abc+*d-
就完成了
下面再出几题

表达式：a+(b-c)×d/e
答案：abc-d×e/+
表达式：a+b×(c-d)-e/f
答案：abcd-×+ef/-

前缀求结果（栈）

例如 - × + 3 4 5 6
我们从右往左遍历
找到一个数字就让入栈
就是

|   |  ←栈
|   |
| 6 |
-----

然后继续遍历
找到数字就入栈

|   |  ←栈
| 5 |
| 6 |
-----

| 3 |
| 4 |  ←栈
| 5 |
| 6 |
-----

直到遍历到符号
就取出栈顶的两个数
进行运算
然后将结果重新入栈

|             |  ←栈
| 35((3+4)*5) |
| 6           |
---------------

再继续遍历
数字就入栈，符号就运算
就是

|               |  ←栈
|               |
| 29((3+4)*5-6) |
-----------------

最后栈顶就是答案=29
顺便还把算式求出来了

后缀求结果（栈）

拿一个样例来讲：abc+*d- （a=1 b=2 c=3 d=4）
我们从左往右遍历
找到一个数字就让入栈
就是

|      |  ←栈
|      |
| a(1) |
--------

然后继续遍历
找到数字就入栈

|      |  ←栈
| b(2) |
| a(1) |
--------

| c(3) |  ←栈
| b(2) |
| a(1) |
--------

直到遍历到符号
就取出栈顶的两个数
进行运算
然后将结果重新入栈

|            |  ←栈
| c+b(3+2=5) |
| a(1)       |
--------------

再继续遍历
数字就入栈，符号就运算
就是

|            		 |  ←栈
| 					 |
| a*(c+b)(1*(3+2)=5) |
----------------------

|            		 |  ←栈
| d(4)				 |
| a*(c+b)(1*(3+2)=5) |
----------------------

|            		     |  ←栈
| 					     |
| a*(c+b)-d(1*(3+2)-4=1) |
--------------------------

最后栈顶就是答案=1
顺便还把算式求出来了
下面出几题

表达式：abc-d×e/+ (a=5 b=4 c=3 d=2 e=1)
答案：7 (a+(b-c)×d/e)
表达式：abcd-×+ef/- (a=6 b=5 c=4 d=3 e=2 f=1)
答案：9 (a+b×(c-d)-e/f)

我来科普一下树

前序（根左右）

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

若二叉树为空则结束返回，否则:

(1)访问根结点。

(2)前序遍历左子树。

(3)前序遍历右子树 。
前序遍历
前序遍历

需要注意的是:遍历左右子树时仍然采用前序遍历方法。

如下图所示二叉树

前序遍历结果:ABDECF

已知后序遍历和中序遍历，就能确定前序遍历。

中序（左根右）

后序（左右根）

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即:

若二叉树为空则结束返回，

否则:

(1)后序遍历左子树

(2)后序遍历右子树

(3)访问根结点

如下图所示二叉树

后序遍历结果:DEBFCA

已知前序遍历和中序遍历，就能确定后序遍历。

谢谢