一个表达式与一棵二叉树之间_二叉树后序遍历算法

1. 概念

• 前缀表达式(Prefix Notation)是指将运算符写在前面操作数写在后面的不包含括号的表达式，而且为了纪念其发明者波兰数学家JanLukasiewicz，所以前缀表达式也叫做“波兰表达式”
• 后缀表达式(Postfix Notation)与之相反，是指运算符写在操作数后面的不包含括号的算术表达式，也叫做逆波兰表达式
• 中缀表达式(InfixNotation)就是常用的将操作符放在操作数中间的算术表达式。前缀表达式和后缀表达式相对于中缀表达式最大的不同就是去掉了表示运算符优先级的括号

2. 与二叉树关系
前缀表达式对应于二叉树的前序遍历

中缀表达式对应于二叉树的中序遍历

后缀表达式对应于二叉树的后序遍历

3. 中缀转后缀
人工转换的方法，假设有一个中缀表达式a+b*c-(d+e)

首先将这个中缀表达式的所有运算加括号((a+(b*c))-(d+e))
然后将所有运算符放到括号后面，这样就变成了((a(bc)* )+ (de)+ )-
把所有括号去掉abc*+de+ -，最后得出的结果就是后缀表达式
4. 表达式转二叉树
表达式（前缀，中缀，后缀表达式）的特点：树的树叶是操作数（常数或变量），而其他节点为操作符。
根据上面的特点我们可以把表达式转成二叉树。
如(a+b)*c-(d+e)的二叉树表示为：
tips：可以先写为：((a+b)*c))-(d+e))，转的时候记得去除括号

转为二叉树之后对其进行不同的遍历就形成了不同的表达式了。

5. 后缀表达式计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如后缀表达式“3 4 + 5 × 6 -”：

从左至右扫描，将3和4压入堆栈；
遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
将5入栈；
接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
将6入栈；
最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
为什么要设计后缀表达式，有什么好处？
便于用栈实现计算，而且不需要表示运算符优先级的括号。
————————————————
原文链接：https://blog.csdn.net/qq_22771739/article/details/88077977

今天的文章一个表达式与一棵二叉树之间_二叉树后序遍历算法分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。