Question

怎么把算术表达式画成二叉树，例+—*^ABCD/E/F+GH，求中缀表达式，不要算法，要思路，对付

怎么把算术表达式画成二叉树，例+—*^ABCD/E/F+GH，求中缀表达式，不要算法，要思路，对付选择题！求高手进进进！在线等。

Answer 1

如图。

中缀表达式是

A ^ B * C - D + E / (F / (G + H))

追问

画出来的标准是什么？

追答

怎么根据前缀表达式画出二叉树？你刚才还说不要算法。

建立空二叉树
建立一个迭代器，指向树根
遍历前缀表达式
遇到操作符，放到迭代器指向的节点，把迭代器移到这个节点的左子节点
遇到操作数，放到迭代器指向的节点，如果这个节点是左节点，则把迭代器移到右节点；否则向上回溯直到遇到空的右节点（如果回溯到树根则终止程序）

其实仔细看我画的图，就会发现算法是很显而易见的。

追问

那如果只给中缀或者后缀那怎么画

还有什么时候加括号？

Answer 2

你这个表达式是什么顺序遍历出来的？

追答

基本思路是先把算术表达式转换为二叉树，然后根据遍历方式不同，得出前、中、后缀表达式。

追问

前

前缀排列，这个我也知道，关键得把二叉树画出来呀

追答

先序遍历，从左边开始画，遇到字母则作为叶子结点就行了。

然后画出来如下

画出来后，直接中序遍历就是中缀表达式。

追问

叶子一定从下往上？bcd的顺序

追答

是的，因为是先序遍历，即根—>左—>右的顺序，所以这里一定是这个顺序。

追问

那如果是只给中缀和后缀怎么画

追答

都是这个图

追问

怎么画= =

追答

中缀表达式按顺序从最低级的运算符开始作为根结点，然后把符号两边的数字或者整体作为左、右子结点。

其实你这里的画法，就是算法。

追问

后缀怎么操作？

那啥时候加括号？

追答

后缀表达式的画法麻烦一点，可以从后面开始话，画法也就根据符号作为根结点，字母作为叶子结点。

括号在每一个跟结点结束就可以加括号，完成后删除掉不需要的括号就行了。