1. 表达式树
表达式树（Binary Expression Tree）是一类特殊的二叉树，用以表示表达式，如图 7.6.1 所示，是一棵表示了 a + b * c + d * (e + f) 的表达式树。
表达式树有如下特点：
- 操作数总是叶子结点，运算符是非叶子结点。
- 根结点是表达式中优先级最低的运算符。
- 在内部结点中，下一层的运算符优先级高于上一层的运算符优先级。
2. 手工创建表达式树
（1）以手工方式，由中缀表达式生成表达式树
以中缀表达式 a + b * c + d * (e + f) 为例，生成表达式树的过程如下：
-
将原中缀表达式按照运算符的优先级进行划分，得到
(a + (b * c)) + (d * (e + f))。 -
由上述优先级划分可知，第 2 个
+运算符的优先级最低，作为表达式树的根结点，并且(a + (b * c))作为为左子树，(d * (e + f))作为右子树。 -
左子树
(a + (b * c))中优先级最低的是+运算符，作为左子树的根结点。-
a作为左子树，即叶子。 -
(b * c)作为右子树，*作为根结点b左子树，即叶子。c右子树，即叶子。
-
-
类似上一步骤的方式，递归地构造右子树
(d * (e + f))。
最终得到图 7.6.1 所示的表达式树。
（2）以手工方式，由后缀表达式生成表达式树
为了生成表达式树，需要使用栈，基本规则是：从左向右扫描后缀表达式。
- 如果遇到操作数，则生成只有一个根结点的二叉树（也就是一个结点），并将该二叉树进栈。
- 如果遇到运算符，则从栈中弹出两棵树，创建以该运算符为根结点的二叉树，并将该二叉树进栈。
如图 7.6.2 所示，显示了用手工方式，由后缀表达式生成表达式树的过程。
- 从左向右扫描后缀表达式，分别读取到三个操作数，
a b c，将它们分别作为三棵二叉树的根结点（即三棵只有一个根结点的树）入栈，如图 9.6.2(a) 所示。 - 继续扫描后缀表达式，读取运算符
*，从栈中弹出两棵二叉树：c, b，作为以*为根结点的二叉树的右、左子树，并将此二叉树入栈，如图 7.6.2(b) 所示。 - 继续扫描后缀表达式，读取运算符
+，从栈中弹出两棵二叉树：*, a，作为以+为根结点的二叉树的右、左子树，并将此二叉树入栈，如图 7.6.2© 所示。 - 继续扫描后缀表达式，读取操作数
d e f，将它们分别作为三棵二叉树的根结点，并入栈，如图 7.6.2(d) 所示。 - 继续扫描后缀表达式，读取运算符
+，从栈中弹出两棵二叉树：f, e，作为以+为根结点的二叉树的右、左子树，并将此二叉树入栈，如图 7.6.2(e) 所示。 - 继续扫描后缀表达式，读取运算符
*，从栈中弹出两棵二叉树：+, d，作为以*为根结点的二叉树的右、左子树，并将此二叉树入栈，如图 7.6.2(f) 所示。 - 继续扫描后缀表达式，读取运算符
+，从栈中弹出两棵二叉树：*, +，作为以+为根结点的二叉树的右、左子树，并将此二叉树入栈，如图 7.6.2(g) 所示。 - 后缀表达式扫描结束，且栈中只有一个以运算符为根结点的二叉树，该该二叉树出栈，即得到了表达式树。
对比图 7.6.2(g) 和图 7.6.1 的表达式树，二者相同，亦即说明：一个表达式，无论是后缀表达式、中缀表达式，亦或前缀表达式，计算结果都是一样的，也就是说均表达了同样的代数含义，那么它们所对应的表达式树，也是一样的。
以图 7.6.1 或者图 7.6.2(g) 的表达式树为例，分别对它进行三种遍历：
- 前序遍历：
+ + a * b c * d + e f，即前缀表达式； - 中序遍历：
(a + (b * c)) + (d * (e + f)) = a + b * c + d * (e + f)，即中缀表达式； - 后续遍历：
a b c * + d e f + * +，即后缀表达式。
_网店推广运营策略_拓客公司联系方式)
