从代数表达式创建二叉树

前缀表达式的树结构

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 <operator> leftVal      else       return node.value

考虑到从前缀表达式构造树的简单性，我建议使用标准堆栈算法将中缀转换为前缀。在实践中，您将使用堆栈算法来计算中缀表达式。