二叉树求表达式,请教!
最近碰到二叉树求表达式的问题,一直想不明白,请高手指点!————————————————————————————————————————————————————————————————————————————
1.利用二叉树求表达式,不利用栈可以吗?
利用栈的话,可以在输入的时候直接判断操作数和操作符并分别压入操作数栈和操作符栈;现在想利用二叉树直接求值,感觉此时再借助栈的话,二叉树就变得多余了。我查了一些前辈的代码,好多都要借助栈;现在,我想只用二叉树,真的可以吗?
2.我希望可以输入原始的表达式,而不是转换成后缀式等,并根据输入的字符动态建立二叉树
例如,输入:2.2*(3.1+1.20)-7.5/3
输出:6.96
————————————————————————————————————————————————————————————————————————————
本想建立二叉树,例如a+b*c-d;
建立后:
-
/ \
/ \
+ d
/ \
/ \
a *
/ \
/ \
b c
我想到的是将优先极高的操作符存于比其低的结点的右子树上,可是当我把“a+b*c”存好后,不知道怎么将“—”存在“+”的上一结点。请高手教教我,谢谢了!