中缀表达式，前缀表达式 ，后缀表达式的相互转换

• 2020 年 11 月 1 日
• 笔记

第一步 构建表达式树

　　11。前缀，后缀表达式构建方法

　　　　1.表达式树是一棵二叉树

　　　　2.每一个数字，运算符都可以填在一个节点上

　　　　3.用运算符填充的节点，自动生成两个子节点。当且仅当这两个子节点被填充，称原节点填充。

　　　　4.数字填写在节点，节点视为填充完成。

　　　　5.扫描顺序  前缀表达式从前向后扫描，后缀表达式从后向前扫描。

　　22.中缀表达式构建方法

　　　　1.运算优先级高的一部分先用运算符做父节点，数字做子节点的方法构建。然后当成一个数的整体重复上述步骤

第二部 解析表达式树

　　11。遍历顺序。

　　　　1.左右节点先遍历哪个没有本质区别。因此默认先遍历左节点，后遍历右节点。

　　　　2.前序，后序，中序。中的前，中，后指代的是根节点访问的先后顺序。

　　　　3.前缀，中缀，后缀对应前序，后序，中序三种遍历方法。

其他知识

　　　　前缀表达式又称波兰式，后缀表达式又称逆波兰式。