C++ 二叉树应用 —— 前中后缀表达式

zltzlt

二叉树应用 —— 前中后缀表达式

前中后缀表达式的概念

中缀表达式是一种通用的算术表示法，操作符以中缀形式处于操作数的中间。

需要注意，虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式是比较复杂的。

因此计算中缀表达式的值时，通常需要将中缀表达式转化为前缀或后缀表达式，然后再进行求值。

对计算机来说，计算前缀或后缀表达式的值非常简单。

中缀表达式转前 / 后缀表达式

给定一个表达式的中缀形式：(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 是右子树。

得到的表达式树如下图：

                               
登录/注册后可看大图

构造好表达式树之后，前缀表达式和后缀表达式可根据先序遍历和后序遍历得到。

前缀表达式：- + 4 * 1 - 5 2 / 6 3

后缀表达式：4 1 5 2 - * + 6 3 / -

以上内容来自 https://blog.csdn.net/fireflylane/article/details/83017889