C++ 二叉树应用 —— 前中后缀表达式
二叉树应用 —— 前中后缀表达式前中后缀表达式的概念
中缀表达式是一种通用的算术表示法，操作符以中缀形式处于操作数的中间。
需要注意，虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式是比较复杂的。
因此计算中缀表达式的值时，通常需要将中缀表达式转化为前缀或后缀表达式，然后再进行求值。
对计算机来说，计算前缀或后缀表达式的值非常简单。
中缀表达式转前 / 后缀表达式
给定一个表达式的中缀形式：(4+1*(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 是右子树。
得到的表达式树如下图：
https://img-blog.csdn.net/20170603205711071?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbGlxaXV0dW95dWFu/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
构造好表达式树之后，前缀表达式和后缀表达式可根据先序遍历和后序遍历得到。
前缀表达式：- + 4 * 1 - 5 2 / 6 3
后缀表达式：4 1 5 2 - * + 6 3 / -
以上内容来自 https://blog.csdn.net/fireflylane/article/details/83017889
页:
[1]