创建递归二叉树？
我有两个堆栈，一个用操作数，另一个用操作符。 我的问题是将这两个堆栈变成二叉树。
例如，表达式(2+3)*(4-3)将被转换为后缀（例如24+43-* ），然后放入两个堆栈3442和*-+将成为堆栈（顶部为分别为3和*）。
现在使用这些堆栈，我需要形成一个像二进制树
* + - 2 3 4 3
有没有办法递归地做到这一点？
现在，我有一个像这样的算法：
-
创建树的根，将根的值分配给operator-stack中的第一个运算符。 将右指针和左指针设置为null。
-
创建正确的节点，如果存在，则分配下一个运算符的值，如果不为其分配操作数。 然后对左节点执行相同操作。
我的问题是使这个递归，或让它来处理许多不同的情况。
谢谢你的帮助。
假设您只有二元运算符
treeNode createNode(operators, operands) { // take first operator and create a new treeNode with it. pop it from the operators stack // if it is the last operator in the list then there should be only two operands left in the operands and you can assign them to the left and right child of the treeNode. return this treeNode. // if it is not the last operator then split the operands in two stacks equally // leftOperands and rightOperands // left child becomes createNode(operators, leftoperands) // right child becomes createNode(operators, rightoperands) // return this treeNode }
递归算法：
- 找到最优先的运营商
- 拆分此运算符周围的表达式
- 递归地应用于两个部分
如果你的表达式总是对称的（运算符每一侧的操作数和运算符数相同），那么你描述的方法工作正常，稍加修改：
- 创建一个节点，在运算符堆栈中分配top运算符的值。
- 如果操作员堆栈上没有操作符，则从操作数堆栈中弹出2个操作数并将它们分配给左右分支，然后退出
- 如果堆栈中有任何操作符，请转到节点的左侧brach并调用算法，然后转到右侧分支并调用算法。
（Jan在他的回答中解释得那么清楚……）
一般来说，没有办法做到这一点。 “1 2 3 4”“* + /”是指“1 2 3 4 * + /”（即“1 /（2 + 3 * 4）”）还是“1 2 * 3 + 4 /”，（即“（1 * 2 + 3）/ 4”）。