计算器算法 - 在二叉搜索树上使用迭代而不是递归

Question

我已经看到了如何遍历二叉树并找到所有节点的总和的方法，除了我正在评估计算器的表达式输入。节点按照操作顺序排列，节点为operators或operands。我认为 recursion 比迭代慢所以我想弄清楚如何遍历二叉树并找到没有 recursion.

输入的表达式的结果

树的例子：

      +
  *       /
3   4   4   2

我目前使用的递归方法（我对运算符使用了一个枚举）：

public static float evaluate(BETNode root)
{
    if (root == null)
    {
        throw new IllegalArgumentException("Error: Root is null!");
    }

    if (root.getType() == BETNodeType.OPERAND)
    {
        return root.getOperand();
    }

    float leftValue = evaluate(root.getLeft());
    float rightValue = evaluate(root.getRight());

    switch (root.getOperator())
    {
        case '+':
            return leftValue + rightValue;

        case '-':
            return leftValue - rightValue;

        case '*':
            return leftValue * rightValue;

        case '/':
            return leftValue/rightValue;
    }

    throw new IllegalArgumentException("Error.");
}

Answer 1

正如我在上面的评论中提到的，如果您执行了 iterative post-order traversal，您将获得以下顺序的节点：

3, 4, *, 4, 2, /, +.

据此，您只需要一个堆栈来计算表达式。

Push 3
Push 4
Push (pop() * pop())

Push 4
Push 2
Push (pop() / pop())
Push (pop() + pop())
//Result

同样有趣的是Shunting Yard Algorithm，它根据中缀表达式进行求值。

计算器算法 - 在二叉搜索树上使用迭代而不是递归

Calculator Algorithm - Using Iteration instead of Recursion on Binary Search Tree

java

algorithm

recursion

binary-tree