创建递归二叉树？
创建递归二叉树？
提问于 2010-11-11 15:20:57
我有两个堆栈，一个有操作数，另一个有运算符。我的问题是把这两个堆栈变成二叉树。
例如，表达式(2+3)*(4-3)将被翻译为后缀(例如24+43-*)，然后放入两个堆栈中-- 3442和*-+将是堆栈(顶部分别为3和*)。
现在使用这些堆栈，我需要形成一棵二叉树，如
*
+ -
2 3 4 3有什么方法可以递归地这样做吗？
现在，我有一个这样的算法：
- 创建树的根，将根的值分配给运算符堆栈中的第一个运算符。将右指针和左指针设置为空。
- 创建正确的节点，如果下一个操作符存在，则分配它的值，如果没有给它分配一个操作数。然后对左侧节点执行相同的操作。
我的问题是使这个递归，或让它来处理许多不同的情况。
谢谢你的帮助。
回答 4
Stack Overflow用户
发布于 2010-11-11 15:35:18
假设您只有二进制运算符
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
}Stack Overflow用户
发布于 2010-11-11 15:26:05
递归算法：
operator
- recursively
- 找到最高优先级运算符
- ，将表达式拆分到此
上。
Stack Overflow用户
发布于 2010-11-11 15:39:00
如果您的表达式总是对称的(操作符两边的操作数和操作符的数目相同)，那么您描述的方法工作得很好，只需稍作修改：
- 创建一个节点，在操作符堆栈中分配顶级操作符的值。如果运算符堆栈上没有运算符，则从操作数堆栈中弹出两个操作数，并将其分配给左和右分支，然后退出
- ，如果堆栈上有任何运算符，则退出
- ，然后到节点的左brach调用算法，然后转到右分支并调用算法。
(简在回答中解释得很清楚.)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4155975
复制相关文章
相似问题
腾讯云开发者
