[二叉树] 表达式树

将中缀表达式转换成表达式树

最快捷的方法是先找到表达式树的根元素, 以下面的这个中缀表达式为例

a + b * c - ( d + e / f * ( g + h ) )

为了找到表达式树的根元素, 首先把表达式的所有运算都加上括号, 如下

( a + ( b * c ) ) - ( d + ( ( e / f ) * ( g + h ) ) ) 

括号外的 - 优先级最低, 作为表达式树的根节点, 这样就可以以根节点开始, 画出整个表达式树了

还是上面的例子, - 为根节点, 那么左子树的表达式就是:

a + ( b * c )

再次选择括号外优先级最低的运算符作为子树的根, 因此左子树的根就是 +

依次类推, 往下面递归, 就可以很容易的画出整个表达式树了

表达式树

转化为前缀表达式

画出表达式树之后, 只需要对这个树进行先根遍历就可以得到对应的前缀表达式

转化为后缀表达式

画出表达式树之后, 只需要对这个树进行后根遍历就可以得到对应的后缀表达式