在计算机科学中，除了堆栈之外，二叉树也是处理表达式的常用工具，为了处理表达式而按照适当的规则结构化的树被称为表达式树。
公式树的算术表达式是分层递归结构，其中运算符作用于对应的运算对象，该运算对象可以是任意复杂的表达式。 树的递归结构用于表示此表达式。 这里只说明二项式。
二项式可以自然地与二叉树相连：以基本运算对象为叶节点中的数据的算子为非叶节点的数据，其两个子树为其运算对象，子树可以是基本运算对象，也可以是复杂的表达式。 图为公式树。
前缀、骑马订和后缀表达式中缀表达式（中缀记法）
我们平时省略的表达式，把运算符写在两个操作数中间的表达式称为骑马订表达式。 在骑马订表达式中，运算符具有不同的优先级，括号用于更改运算顺序。 因此，运算规则变得复杂，不能直接从左到右进行评价过程，不利于计算机处理。
后缀表达式
在两个操作数之后描述运算符的表达式称为后缀表达式。 后缀表达式没有括号，运算符没有优先级。 后缀表达式的评价过程可以按照从左到右的顺序严格进行，有利于计算机处理。
前缀表达式
前缀表达式是将运算符写在两个操作数之前的表达式。 与后缀表达式一样，前缀表达式没有括号，运算符没有优先级，可以严格按从右到左的顺序计算。
此外，公式和公式树的关系如下。
表达式树的开头根导线：前缀表达式树的中间根导线：骑马订表达式树的结尾根导线：后缀表达式转换使用表达式树提供表达式的骑马订格式。 (41*(5-2) )-6/3
首先，对每个运算加括号并赋予优先顺序，得到(4(1* ) (5-2) ) )6/3)
括号外的-优先级最低，作为根节点，将(4(1*(5-2) ) )作为左侧子树，(6/3)作为右侧子树
递归变换4(1*(5-2) )、最根节点、4是左子树、(1* )5-2) )是右子树。 *是右侧子树的根节点，1是左侧子树，(5-2)是右侧子树。 最后的计算(5-2)，-是根节点，5是左子树，2是右子树。 的表达式树好像是文章开头给的图。
创建表达式树后，可以从根导线测量和根导线测量获取前缀表达式和骑马订表达式。
前缀表达式：- 4 * 1 - 5 2/6 3
后缀表达式：4 1 5 2 - * 6 3/-
堆栈将中缀表达式转换为后缀表达式
step1:初始化堆栈和后缀表达式字符串
step2)按从左到右的顺序处理骑马订表达式中的每个字符，直到表达式结束
如果字符为“”，则堆栈它的字符为数字；如果要添加到后缀表达式字符串的字符为运算符，则堆栈顶层优先级不低于运算符的运算符，添加到后缀表达式，然后堆栈运算符。 请注意，当“”位于堆栈中时，如果字符为“”，则优先级最低。 将堆栈的顶级元素添加到堆栈中，并将其添加到后缀表达式中，直到堆栈变为“”
step3)如果表达式结束后堆栈中仍有元素，则堆栈所有元素并将其添加到后缀表达式中。 例如，一个表达式的骑马订格式(41*(5-2) )-6/3，堆栈中元素和表达式的变化如下表所示：
扫描目标要素堆栈后缀式的说明(式空4(4为式加4(4为式加1 (41为式加1 (* 4为式加* ) ) )、41为() ) ) )、式加5 ) ) 堆栈空----4152(*-堆栈6 ) 4152 ) *66公式/----4152(*6/堆栈3(/4152 ) *633公式) 52-*63/-式扫描结束
将中缀表达式转换为前缀表达式
从骑马订式到前缀表现的转换方法与后缀式的转换过程一致，细节发生变化
step1初始化一个堆栈s1和s2
step2:对于“骑马订”表达式中的每个字符，从右到左依次执行以下操作，直到表达式结束
如果字符为“)”，则堆栈的字符为数字；如果要添加到s2的字符为运算符，则堆栈顶部优先级不低于运算符的运算符，添加到s2，然后堆栈运算符。 如果“”在堆栈中，则如果具有最低优先级的字符是“”，则将堆栈的顶级元素提交到堆栈中，并将其添加到s2直到堆栈为“”
step3:表达式结束后，如果堆栈中仍有元素，则从堆栈中提取所有元素，并将其添加到s2
step4(依次堆栈s2的要素。 也就是说，得到被给出前缀表达式的骑马订形式。 (41*(5-2) ) )6/3，其前缀形式为-4*1-5)2/6
表达式计算中前缀表达式的计算已经很清楚，前缀和后缀表达式更
适合计算机处理后缀表达式的计算
后缀表达式没有括号，运算符的顺序即为实际运算顺序，在求值过程中，当遇到运算符时，只要取得前两个操作数就可以立即进行计算。当操作数出现时，不能立即求值，需要先保存等待运算符。对于等待中的操作数而言，后出现的先运算，所以需要一个栈辅助操作。
后缀表达式的运算过程如下：
step1：设置一个栈
step2：从左到右对后缀表达式中的字符进行以下处理：
- 如果字符是数字，现将其转化为数字，然后入栈
- 如果字符是运算符，出栈两个值进行计算。计算结果入栈
- 重复以上步骤，直到后缀表达式扫描结束，栈中最后一个元素就是表达式的结果。
给定后缀表达式4 1 5 2 - * + 6 3 / -，依次将4 1 5 2 入栈，当扫描到-时，2,5出栈，计算5-2=3；将3入栈，此时栈中元素为4 1 3。接着扫描到*，3 1出栈，计算1*3=3,3入栈，栈中元素为4 3,。扫描+，3 4出栈，计算4+3=7,7入栈。接着6 3 入栈，栈中该元素为7 6 3，扫描到/，3 6出栈，计算6/3=2,2入栈，栈中元素为7 2.扫描-，2 7 出栈，计算7-2=5,5入栈。表达式扫描完毕，栈中元素为5，表达式结果为5.
前缀表达式的计算
前缀表达式的计算扫描顺序从右到左，其他和后缀表达式的计算完全一致。
以上内容转载自二叉树的简单应用–表达式树，略加修改，给此文博主一个大大的赞，良心好文！！！本文以下内容为我对于这篇博文的一个补充。
表达式树代码实现如何给一个表达式建立表达式树呢？方法有很多，这里只介绍一种：找到"最后计算"的运算符(它是整棵表达式树的根)，然后递归处理(这也是前文介绍的方法)。下面是程序：
const int maxn = 1000;int lch[maxn], rch[maxn]; char op[maxn];int nc = 0;//结点数int build_tree(char* s, int x, int y){int i, cl = -1, c2 = -1, p = 0;int u;if(y-x == 1)//仅一个字符，建立单独结点{u = ++nc;lch[u] = rch[u] = 0; op[u] = s[x];return u;}for(i = x; i < y; i++){switch(s[i]){case '(': p++; break;case ')': p--; break;case '+': case '-': if(!p) c1 = i; break;case '*': case '/': if(!p) c2 = i; break;}}if(c1 < 0) c1 = c2;//找不到括号外的加减号，就用乘除号if(c1 < 0) return build_tree(s, x+1, y-1);//整个表达式被一对括号括起来u = ++nc;lch[u] = build_tree(s, x, c1);rch[u] = build_tree(s, c1+1, y);op[u] = s[c1];return u;}注意上述代码是如何寻找“最后一个运算符”的。代码里用了一个变量p，只有当p=0时才考虑这个运算符。为什么呢？因为括号里的运算符一定不是最后计算的，应当忽略。例如(a+b)*c中虽然有一个加号，但却是在括号里的，实际上比它优先级高的乘号才是最后计算的。由于加减和乘除号都是左结合的，最后一个运算符才是最后计算的，所以用两个变量c1和c2分别记录“最右”出现的加减号和乘除号。
再接下来的代码就不难理解了：如果括号外有加减号，它们肯定最后计算；但如果没有加减号，就需要考虑乘除号( if(c1<0) c1 = c2 )；如果全都没有，说明整个表达式外面被一对括号括起来，把它去掉后递归调用。这样，就找到了最后计算的运算符s[c1]，它的左子树是区间[x, c1]，右子树是区间[c1+1, y]。
提示：建立表达式树的一种方法是每次找到最后的运算符，然后递归建树。“最后计算”的运算符是在括号外的、优先级最低的运算符。如果有多个，根据结合性来选择：左结合的(如加减乘除)选最右边；右结合的(如乘方)选最左边。根据规定，优先级相同的运算符的结合性总是相同。
这个代码十分简单，只要将算法直译过来即是代码，博主比较懒，就将这个工作交给读者了，如果学校里后面有这个作业，博主会贴上代码。。
拓展：由浅入深表达式树（一）创建表达式树