中缀表达式转为二叉树
8-(3+5)*(5-6/2)
怎样把中缀表达式转为二叉树?中缀表达式的括号怎样处理?
说说转换方法就好了,不要算法!
知道怎样得到后缀与前缀,可是后缀与前缀中没有中缀的括号了,怎样解决呢?
[解决办法]
快忘干净了,不知道对不对。
转为二叉树以后,括号就去了。父节点是运算符号,子节点是需要运算的变量。
如上述表达式转化成二叉树以后,是这个样子
-
8 *
+ -
3 5 5 /
6 2
[解决办法]
分这样几步就可以:
先按照优先级加上括号,得到:( 8 - ( (3 + 5) * ( 5 - (6 / 2) ) ) )
然后从最外层括号开始,依次转化成二叉树
1、根是-,左子树8,右子树( (3 + 5) * ( 5 - (6 / 2) ) )
2、右子树的根*,右子树的左子树(3 + 5),右子树的右子树( 5 - (6 / 2) )
3、(3 + 5)的根+,左子树3,右子树5
4、( 5 - (6 / 2) )的根-,左子树5,右子树(6 / 2)
5、(6 / 2)的根/,左子树6,右子树2