从代数表达式创建二叉树
我必须用Java创建一个算术求值器。 为此，我必须解析二叉树中的代数表达式，然后计算并返回结果。 因此，对于第一步，我如何解析二叉树中的表达式？ 我知道这个理论，但我的问题是如何用Java做到这一点。 我阅读了以下post创建递归二叉树
但我错过了基本的技巧或方法。 我知道如何创建一个节点（我有一个类，其中包含returnNodeValue，isLeaf，isDoubleNode，isSingleNode等方法），但我想我需要一个方法在二叉树中插入一个节点来实现我想要的东西。 有任何想法吗？
前缀表达式的树构造
def insert Insert each token in the expression from left to right: (0) If the tree is empty, the first token in the expression (must be an operator) becomes the root (1) Else if the last inserted token is an operator, then insert the token as the left child of the last inserted node. (2) Else if the last inserted token is an operand, backtrack up the tree starting from the last inserted node and find the first node with a NULL right child, insert the token there. **Note**: don't insert into the last inserted node. end def 我们举个例子： + 2 + 1 1
申请（0）。
+
申请（1）。
+ / 2
申请（2）。
+ / \ 2 +
申请（1）。
+ / \ 2 + / 1
最后，申请（2）。
+ / \ 2 + / \ 1 1
该算法已针对- * / 15 - 7 + 1 1 3 + 2 + 1 1
所以Tree.insert实现就是这三个规则。
insert(rootNode, token) //create new node with token if (isLastTokenOperator)//case 1 //insert into last inserted's left child else { //case 2 //backtrack: get node with NULL right child //insert } //maintain state lastInsertedNode = ?, isLastTokenOperator = ?
评估树有点搞笑，因为你必须从树的右下角开始。 执行反向的订单后遍历。 先访问合适的孩子。
evalPostorder(node) if (node == null) then return 0 int rightVal = evalPostorder(node.right) int leftVal = evalPostorder(node.left) if(isOperator(node.value)) return rightVal leftVal else return node.value
鉴于从前缀表达式构造树的简单性，我建议使用标准堆栈算法从中缀转换为前缀。 在实践中，您将使用堆栈算法来评估中缀表达式。
我想你可能会对你应该做的事情感到有点困惑：
…但我想我需要一种方法在二叉树中插入一个节点……
您正在谈论的二叉树实际上是一个解析树，它不是严格意义上的二叉树（因为并非所有树节点都是二进制树）。 （除了“二叉树”具有二叉搜索树的内涵，这根本不是你需要的。）
你已经想出解析表达式，解析树的构造非常简单。 例如：
Tree parseExpression() { // .... // binary expression case: Tree left = parseExpression(); // parse operator Tree right = parseExpression(); // lookahead to next operator if (...) { } else { return new BinaryNode(operator, left, right); } // ... }
注意：这不是正常工作的代码……这是一个帮助您完成作业的提示。