创建递归二叉树？ [英] Create recursive binary tree?

问题描述

我有两个烟囱，其中一个操作数，其他的与运营商。我的问题是转向这两个堆栈成二进制树。

I have two stacks, one with operands, the other with operators. My problem is turning these two stacks into a binary tree.

例如，前pression （2 + 3）*（4-3）
将被翻译成后缀（这样 24 + 43 - * ），然后放入两个栈
3442 和。* - + 将在堆栈（带顶部分别为3和*）

For example, the expression (2+3)*(4-3) will be translated into postfix ( such that 24+43-*) and then put into two stacks 3442 and *-+ will be the stacks (with the tops being 3 and * respectively).

现在这些书库，我需要形成一个二叉树像

Now with these stacks, i need to form a binary tree like

   *
 +    -
2 3  4 3

有没有办法做到这一点递归？

Is there a way to do this recursively?

现在，我有一个算法，像这样：

Right now, I have an algorithm like so:

• 创建树的根，根的值分配给在操作栈的第一个操作符。设置为NULL左右指针。

• Create the root of the tree, assign the value of the root to the first operator in the operator-stack. Set the right and left pointers to null.

创建合适的节点，如果存在分配下一个运营商的价值，如果不给它分配一个操作数。然后为左节点执行相同

Create the right node, assign the value of the next operator if it exists, if not assign it an operand. Then do the same for the left node.

我的问题是使这个递归，或得到它来处理很多不同的情况。

My problem is making this recursive, or getting it to handle the many different cases.

感谢您的帮助。

推荐答案

假设你只有二元运算

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

}

这篇关于创建递归二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！